算法篇——插入排序和归并排序

12 October 2013

今天在github上开了一个新项目，专门记录自己学习算法的经历，《算法导论》这个大部头在我书桌上躺的时间够长了，也该活动活动筋骨了。

算法一直以来被我看做是高智商人群的玩具，那是一种追求更高的速度，更美的结构的心理所驱动，这无疑也为算法宝盒增加了不少的解谜难度。

闲话少说，来看看今天完成的两个排序算法——插入排序和归并排序。

插入排序在我看来，其主要的思想就是，每到来一个新的元素，前面的元素是已经排好序的，只需把这个新元素与前面元素依次比较，在合适的位置插入即可。

for (j = 1; j < MAXNUM; j++) {
		key = randomNum[j];
		i = j - 1;
		while ((i >= 0) && (randomNum[i] > key)) {
			swap = randomNum[i + 1];
			randomNum[i + 1] = randomNum[i];
			randomNum[i] = swap;
			i--;
		}
		randomNum[i + 1] = key;
	}

不算很难，那么我们用python画个图看一看到底是什么情况。

我们可以看到，基本是指数增长，复杂度是n^2。

这里我还用scheme实现了插入排序的一个版本：

(define (sort lst key)
  (if (null? lst)
	(list key)
	(if (> key (car lst))
	  (cons (car lst) (sort (cdr lst) key))
	  (cons key lst))))


(define (insertSort new_lst old_lst)
  (if (null? old_lst)
	new_lst
	(insertSort (sort new_lst (car old_lst))
				(cdr old_lst))))

(define lst (list 6 5 4 7 10 2 11))
(define new (list (car lst)))
(define old (cdr lst))

;;testing
;;(insertSort new old)

函数式编程语言实现这类算法还不是很容易，因为表结构这类线性结构，很难从中间某处开始查找（也可能是自己学的还不够），归并算法还没想到该如何实现。

再来看看归并排序，其实就是分而治之的思想，一部分一部分的排序，最后合为一体。

void merge(int data[], int p, int q, int r)
{
	int n1, n2;
	n1 = q - p + 1;
	n2 = r - q;

	int L[n1 + 1], R[n2 + 1];
	int i, j, k;
	for (i = 0; i < n1; i++)
		L[i] = data[p + i];
	for (j = 0; j < n2; j++)
		R[j] = data[q + j + 1];
	
	L[n1] = MAXNUM;
	R[n2] = MAXNUM;
	i = j = 0;
	for (k = p; k < r + 1; k++)
		if (L[i] <= R[j]) {
			data[k] = L[i];
			i++;
		} else {
			data[k] = R[j];
			j++;
		}
}

void mergeSort(int data[], int p, int r)
{
	int q;

	if (p < r) {
		q = (p + r) / 2;
		mergeSort(data, p, q);
		mergeSort(data, q + 1, r);
		merge(data, p, q, r);
	}
}

int main()
{	
	mergeSort(randomNum, 0, MAXNUM - 1);
	/*	
	int i;
	for (i = 0; i < MAXNUM; i++)
		printf("%d ", randomNum[i]);
	*/
	return 0;
}

看起来要比插入排序复杂一些，可别小看归并排序，那简直是so damn fast! 我们知道归并排序是nlogn的复杂度，试想一下，这种排序在数据规模为100000的情况下，要比插入排序快上100000/6那么多，使得我很难找数据测试。数据太小了秒排，数据太大了，编译的时间远远超过运行时间，而且又没有明显走势。我们还是找些10的次方来测试吧。

恩，还是很快就排完了。归并排序真的很快！

排序的方法有很多，我会在后面一点点实现，不过就单单排序这一类算法而言，确实体现了人类的智慧和算法美，ok，今天先写到这里，后续再接再厉！

algorithm 5

algorithm 5