排序算法总结<二>

　　<一>中涉及到的几个算法，复杂度都是平方阶的。在本部分里，我们将要介绍几种线性对数阶（O(nlgn)）的排序算法。

线性对数阶排序算法

（1）快速排序
　　算法思想：快速排序用到了分治的思想，就是把原来的问题分解为若干个规模更小的问题，但是结构与原来的问题必须相似，因为这样才能递归的解决这些问题，最后再合成为原来问题的解。我们对待其中相似的问题的一般思想是：若有一个无序区域R[low…high]，任选一个作为基准，然后将无序区域分为左、右两个较小的区间，左边区间中所有记录都小于基准值，右边区间中所有记录都大于基准值，则此时该基准值就应该在它该在的位置了。然后，再对两侧较小的区间分别使用类似的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
template <class T>
void Exchange(T* a, T* b){
	T temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
template <class T>
int Partition(T *list, int low, int high){
	T mid_value = list[high];
	i = low -1;
	for(int j = low; j < high; j++){
		if(list[j] < mid_value){
			i++;
			Exchange<T>(&list[i], &list[j]);
		}
	}
	Exchange<T>(&list[i+1], &list[high]);
}
template <class T>
void QuickSort(T *list, int low, int high){
	if(low < high){
		mid = Partition(list, low, high);
		QuickSort(list, low, mid-1);
		QuickSort(list, mid+1, high);
	}
}

　　从上面的程序可以看出，核心算法其实是Partition()函数。它的主要思想是：选取最后一个数作为我们的基准，然后从左向右依次和这个基准数比较，把小于基准数的不断交换到前段的区域中，循环结束后，将基准数从最后换到所有小于基准数的数据块的后面，此时，基准左侧的数将小于基准，右侧将大于基准，完成了对数据域的分块。
　　而主要的排序函数，我们写在了QuickSort()函数中，其用了递归的方式。递归函数首先要思考函数如何终止，很显然应该是序列的尾序号小于等于头序号，如果尾序号大于头序号那么我们就需要分成两部分，继续在两边调用快排函数。
　　我们从上面的算法分析可以看出，快速排序的运行时间依赖于划分的时候是否平衡，而是否平衡又依赖于用于划分的基准元素。如果每次划分都有一部分是空的，也就是用于划分的元素是该部分的最大值或者最小值，那么这样下去最后会接近于插入排序，就提现不出快速排序的优势了。那我们如何尽量使该算法划分的平衡呢？我们只有随机的选择基准才行，这样才能达到平均时间复杂度O(nlgn)。注意，其实只要partition的划分比例是常数，其时间复杂度就是O(nlgn)，比如当partition的划分比例为10000:1时（足够不平衡了），其时间复杂度还是O(nlgn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class T>
int RandomPartition(T *list, int low, int high){
	int mid = rand() % (high - low + 1) + low;
	Exchange<T>(&list[mid], &list[high]);
	T mid_value = list[high];
	i = low -1;
	for(int j = low; j < high; j++){
		if(list[j] < mid_value){
			i++;
			Exchange<T>(&list[i], &list[j]);
		}
	}
	Exchange<T>(&list[i+1], &list[high]);
}

　　我们对Partition函数进行了改进，让其随机选择期间任意一个数作为基准，然后将其移到最后，随后就可以使用和上面相同的方式进行排序了。

（2）归并排序
　　算法思想：归并排序也用到了分治的思想。我们这样来拆分问题：有一个无序区域R[low...high]，我们取mid=(high+low)/2，然后再对R[low...mid]和R[mid...high]使用相同的办法，我们可以想象，最后将会使每个区域只有一个元素，此时可以认为已经有序了。下面就只剩下合并每个小问题了，两个有序的序列，我们只需要分别从左往右遍历，每次比较取出最小值放入新序列就可以完成合并了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
template <class T>
void MergeSort(T* list, int low, int mid,int high){
	int a = mid - low +1;
	int b = high - mid;
	T l[a+1];
	for(int i = 0; i < a; i++){
		l[i] = list[low+i];
	}
	T r[b+1];
	for(int i = 0; i < b; i++){
		r[i] = list[mid+1+i];
	}
	l[a] = r[b] = INT_MAX;
	int i = 0;
	int j = 0;
	for(int k = low; k <= high; k++){
		if(l[i] < r[j]){
			list[k] = l[i++];
		}
		else{
			list[k] = l[j++];
		}
	}
}
template <class T>
void MergeSort(T* list, int low, int high){
	int mid = (low + high)/2;
	if(high > low){
		MergeSort(list, low, mid);
		MergeSort(list, mid, high);
		Merge(list, low, mid, high);
	}
}

　　我们从上述的代码可以看到，归并排序需要大量额外存储空间。对比于快速排序，虽然他们的渐进时间复杂度都是O(nlgn)，但是归并排序的系数要比快速排序要大。归并排序的优势在于其最差、最优和平均的时间复杂度都是O(nlgn)。

（3）堆排序
　　算法思想：运用了最小堆、最大堆这个数据结构。其利用数组来存储数据，可以被看成一个近似的完全二叉树，意味着树的填充顺序是从上到下，从左到右，所以我们如果从1开始标记这些树的元素，那么左子应该是父亲的两倍，右子是父亲的2倍加一。在最大堆中，孩子节点的大小不能超过父亲，最小堆类似。有了这个性质，我们每次只需要移动根节点到有序区，然后重新恢复最大堆的性质，直到所有元素都有序，因此我们需要一个数据记录堆内还有几个元素需要排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
MAX_HEAPIFY(A,i)
 	l = Left(i)
 	r = Right(i)
 	if l < A.heap_size && A(l) > A(i)
     	largest = l
 	else largest = i
 	if r < A.heap_size && A(r) > A(largest)
     	largest = r
 	if largest != i
     	swap(A(largest),A(i))
      	MAX_HEAPIFY(A,largest)
BUILD-MAX_HEAP(A)
 	A.heapsize= A.length
 	for i in n/2.....1
    	MAX_HEAPIFY(A,i)
HEAP_SORT(A)
   	BUILD-MAX_HEAP(A)
 	for i in A.length ...2
   		swap(A[i],A[1])
   		A.heapsize -= 1
  		MAX_HEAPIFY(A,1)

　　上面的程序是伪代码，截取自算法导论，我稍微解释一下。MAX_HEAPIFY()用于使i位置及其以后的位置符合最大堆性质；BUILD-MAX_HEAP()使得传入的数组整个都成为一个最大堆；HEAP_SORT()就是堆排序的核心算法，它首先把整个数组变成一个最大堆，然后把第一个元素，也就是最大的元素换到最后一个，成为有序区的一员，然后，再对无序区建立最大堆，再把第一个元素换到无序区末尾，成为有序区的一员，如此循环往复n-1次（假设数组原长度为n），则所有的元素将变为有序数组。