编程珠玑 -- 关于排序

《编程珠玑》主要提到的排序方法是快排，并通过对基本算法思想的微调，以提高效率及保证最坏情况下的性能。我又回过头去看了Clifford A. Shaffer的《数据结构与算法分析》，总结了几种内排序(internal sorting)算法。（所谓的内排序，就是把所有的数据都加载到内存中后再进行排序）

 首先是插入排序。插入排序就跟我们平时在排放扑克牌的算法一样。每进来一张排，就从尾到前找，为它找到一个合适的位置，然后插入为止。把手里的牌看成一个已排序的子数组X，新插入的牌序号为i，数组X[0,i-1]是手里的牌，且是已经排好序的了，因此，对于新进来的牌，首先是从位置i-1起为它找到一个合适的位置，也就是找到第一个比他小的牌j（我们讨论升序排序），然后把牌 i 插入到牌 j 后面，这时在数组上就表现为X[j+1,i-1]都要往后面移一位。

//基本的插入排序算法思想
void insertSort( int* array, int n ){
	int t;
	for( int i=0; i<n; i++ )
		for( int j=i; j>0 && array[j-1]>array[j]; j-- ){
			t = array[j-1];
			array[j-1] = array[j];
			array[j] = t;
		}
	}
//对insertSort的一点小改进，减少不必要的交换			
void insertSort2( int* array, int n ){
	int t, j;
	for( int i=1; i<n; i++ ){
		t = array[i];		//把刚进来的牌拿在手上
		j = i;
		//从已经排好序的牌的后面开始，一直找到最后一张比它大的牌
		//这个过程中，比它大的牌都在向后移
		while( j>0 && array[j-1]>t ){	
			array[j] = array[j-1];
			j--;
		}
		array[j]=t;		//把这张牌放在这张牌的前面
	}
}

接下来是冒泡排序。冒泡排序的基本思想就是从数组的最后一个元素开始，比较相邻的两个数组元素，如果前面的元素大于后面的元素，那么就交换一下两个元素的位置。这样的话，第一次循环将使最小的元素冒泡到第一个元素，第二次将使第二小的元素冒泡。。。最后整个数组就完成了排序。

void bubbleSort( int*array, int n ){
	int t;
	for( int i=0; i<n; i++ ){	//循环i的最后第i小的元素就冒泡了
		for( int j=n-1; j>i; j-- ){ 
			if( array[j]<array[j-1] ){
				t = array[j];
				array[j] = array[j-1];
				array[j-1] =t;
			}
		}
	}
}

然后是选择排序。在冒泡排序中，其实第i个循环就是为了找到第i大的值，然而却因此而交换了很多次元素，无疑是一种浪费。选择排序是这样一种思想，他也在第i次循环的时候找第i小的元素，但是他通过使用一个临时变量来存放这个第i小的值，从而减少了一些不必要的交换。所以说它是对冒泡排序的一种改进，改进的思想就像对插入排序的改进思想一样。

void selectionSort( int* array, int n ){
	int small;
	for( int i=0; i<n; i++ ){
		small = i;
		for( int j=i+1; j<n; j++ ){
			if( array[j] < array[small] )
				small = j;
			}
		int t = array[small];
		array[small] = array[i];
		array[i] = t;
	}
}

 但是无论如何改进，这三种算法的算法复杂度都是O(n^2)，他们的主要瓶颈都是在于，他们本质上就是通过相邻元素的比较和交换来达到排序的结果。这种算法可以称为“交换排序”。

 
快排的基本思想是，首先挑一个元素k，然后把剩下的元素按照分成两边，一边所有的元素都小于或等于元素k，另一个边所有的元素都大于元素k，这样，元素k的位置就确定了；接下来只需要对数组X[0...k-1]和X[k+1,u]做同样的工作就行了。因此快排的可以分成两个步骤：首先挑选某一特定元素k，并为k找到它排序后的位置，然后就是对X[0...k-1]和X[k+1,u]递归地做同样的事情，直到要处理的数组只有一个或根本没有元素了。

void qsort1( int* array, int l, int u ){
	//如果数组只有一个元素或者为空，就直接返回
	if( l>=u )
		return;
	int m = l;	
	int t;

//array[l...m]<=array[l], array[m+1,i-1]>array[l], array[i,u]未排序
	for( int i=l+1; i<=u; i++ ){
		if( array[i]<=array[l] ){
			m++;
			if( i != m ){
				t = array[m];
				array[m] = array[i];
				array[i] = t;
			}
		}
	}
	t = array[l];
	array[l] = array[m];
	array[m] = t;
	qsort1( array, l, m-1 );
	qsort1( array, m+1, u );
}
	

//qsort2从左到右找到第一个大于array[l]的元素
//然后再从右到左找到第一个小于array[l]的元素
//然后再做交换，直到[i,j]的数组为空
//这样就省了很多次不必要的交换
void qsort2( int* array, int l, int u, int thresh ){
	if( u-l < thresh )
		return;
	int i=l+1, j=u;
	int t;
	while( i<=j ){
		while( array[i]<=array[l] && i<=j )
			i++;
		while( array[j]>array[l] )
			j--;
		if( i > j )
			break;
		else{
			t = array[i];
			array[i] = array[j];
			array[j] = t;
			i++;
			j--;
		}
	}
	if( j>l ){
		t = array[j];
		array[j] = array[l];
		array[l] = t;
	}
	
	qsort2( array, l, j-1, thresh );
	qsort2( array, j+1, u, thresh );
}

 影响快排的效率的有两个方面，一个是元素k的选择，如果不幸元素k是数组中的最大或最小元素，那么一次分组就将得到一个n-1元素的子串和一个只有一个元素的子串，而为了让这个元素k到达它的正确的位置，我们比较了n次元素，如果每次对子串分组都这样，那么其复杂度也将到达O(n^2)，而由于快排使用递归，因此开销可能比前面讲到的三种算法还要大，为了避免这种情况的出现，一般不拿第一个元素做中间元素，而是在数组中随机找一个元素。

第二个问题是递归，当数组很大时，将会递归很多次，我们知道每次递归都会在栈里保存信息，如果递归太多次了，可能会超出栈的最大范围；另一方面，随着数组的不断分组，会出现很多小的子数组，快排在这些小的子数组上花费了太多时间了。为了减少这方面的开销，当子数组很小时，我们停止使用快排，也就是说，快排的最后结果只是接近排序，但还有一些子序列没有排好，这个时候使用排入排序对整个数组再做一次排序，反而性能会更好。一般情况下，快排的期望复杂度为O(nlogn)。

ShellSort也是利用这个原理来提高排序的效率的。他先通过子串的排序来使整个数组接近排序状态，最后再用排入排序来对整个数组进行一次排序。不过ShellSort所谓的子串并不是相邻的元素，而是相邻x个元素元素组成的子数组。换个说法，在插入排序里面，一个数组的元素之间的距离为1，而在Shell排序里，一个数组的元素之间的数组由某个值x按比例地缩小到1.书中建议这个序列的比例最好为3（2是最差的情况）。如果以3为倍数递减的话，最后其平均复杂度为O(n^1.5).顺便说一下，ShellSort的名字的来源是发明这个算法的人叫D.L.Shell，跟壳什么的没有关系,我一直在想着它着壳排序有什么形象上的联系呢。

//首先修改一下insertSort，使它支持对隔x个元素的子数组进行排序
void insertNSort( int* array, int n, int x ){
	int t, j;
	for( int i=x; i<n; i=i+x ){
		t = array[i];
		j = i;
		while( j>=x && array[j-x]>t ){
			array[j] = array[j-x];
			j = j-x;
		}
		array[j] = t;
	}
}

void shellSort( int* array, int n ){
	for( int i=n/3; i>3; i=i/3 ){
		for( int j=0; j<i; j++ )
			insertNSort( &array[j], n-j, i );
		}
	insertNSort( array, n, 1 );
}

 MergeSort也是通过将数组分成几个小数组进行排序，然后再总体排序的，不过这一次他的子数组就是连在一起的了。首先把数组分成两份，对这两份子数组进行排序，然后再把他们merge合在一起。对子数组递归地进行相同的操作，直到子数组只有一个或根本没能元素。一般情况下，需要另一个数组来盛放待合并的数组。

void mergeSort1( int* array, int* temp, int l, int r ){
	if( l>=r )
		return;
	int m=(l+r)/2;
	mergeSort1( array, temp, l, m );
	mergeSort1( array, temp, m+1, r );
	for( int i=l; i<=r; i++ )	//把暂时排好的两个子数组复制到临时数组，
		temp[i] = array[i];
	//接下来进行合并
	int i=l, j=m+1;	//两个子数组的首部
	for( int cur=l; cur<=r; cur++ ){
		if( i > m )
			array[cur] = temp[j++];
		else if( j > r )
			array[cur] = temp[i++];
		else if( temp[i]<temp[j] )
			array[cur] = temp[i++];
		else
			array[cur] = temp[j++];
		}
	}
	
//mergeSort1为了判断两个子序列到达尾部而做了很多次if判断
//下面这种算法通过转变一下复制的顺序，减少了这些判断
//另外，跟quickSort一样，为了减少对小数组的递归，添加了thresh
//小于thresh长度的子数组将使用插入排序
void mergeSort2( int* array, int*temp, int l, int r, int thresh ){
	if( r-l < thresh ){
		insertSort( &array[l], r-l+1 );
		return;
	}
	int m=(l+r)/2;
	mergeSort2( array, temp, l, m, thresh );
	mergeSort2( array, temp, m+1, r, thresh );
	int i, j;
	for( i=l; i<=m; i++ )	temp[i]=array[i];	//正向拷贝
	for( j=r; j>m; j-- ) temp[j]=array[i++];	//逆向拷贝
	i=l; j=r;
	for( int k=l; k<=r; k++ ){
		if( temp[i]<temp[j] ) 
			array[k]=temp[i++];
		else
			array[k]=temp[j--];
		}
	}

考虑这样一种情况，假设一个数组有x个[0,n-1]范围内的元素，下面的语句将使数组在O(n)时间内排序：

for( int i=0; i<x; i++ )
    B[A[i]]=A[i];

相当于我有n个标了号的桶，每个桶可以放一个球，标号为x的球只能放在标号为x的桶里。那样的话，当把所有的球都放到相应的桶里面后，就实现了这个数组的排序了。就像我们前面用过的bitSort一样，只不过这次用的是一个数组元素的位置来表示这个数字是否存在，而在bitSort中只用了一个bit。如果我们把桶弄大一些，比方说，每个桶可以盛放一定标号范围内的球，比方说[0,10]，[11,20]...。当把所有的球都放到相应的桶里面去后，如果数据是随机的，那么每个桶里面应该有差不多数量的球，而且数量也不多，这样对每个桶分别使用一次插入排序之类的，再按顺序从不同范围内的桶里面把球收集回来，就得到了排序好了的数组了。这就是桶排序。桶排序的性能很大程度上依赖于数据的分布，每个桶可以盛放的数据的数量应该怎么确定？还是说用链表而不是数组来盛放这些数据？每个桶可盛放的数据的范围如何确定？总共需要多少个桶？

RadixSort用一个基数做为桶的数量。比方说我们设基数为10，第一轮的时候把数组根据个位数从0到9排放，第二轮的时候把数组根据十位数从0到9排放，假设排序的数据范围为[0,99]，那么经过两轮就能够把数据从小到大排序了。这个过程可以用下图来表达（很难用语言表达）：

//这份代码中，有两个地方可以改进
//首先是(array[j]/rtok)%radix这个运算很耗时，可以通过把radix设为2的指数如16
//然后用与或操作来获得下标
//其次是每一轮做完后都要从temp向array赋值，其实交换使用temp，
//最后通过k的奇偶来确定是否需要从temp向A赋值。
//算法的复杂度是O(n*k+radix*k)
void radixSort( int* array, int n, int radix ){
	//用cnt[i]来保存桶bin[i]中的数据的个数
	int* cnt = new int[radix];
	//用temp[]数组来临时存放数组array
	int* temp = new int[n];
	//首先求得数组的最大值，从而确定要循环多少轮
	int large = array[0];
	for( int i=1; i<n; i++ ){
		if( large < array[i] )
			large = array[i];
		}
	int k=0;
	while( large>0 ){
		k++;
		large = large/radix;
	}
	for( int i=0, rtok=1; i<k; i++, rtok *=radix ){
		for( int j=0; j<radix; j++ )	cnt[j] = 0;
		for( int j=0; j<n; j++ )	cnt[(array[j]/rtok)%radix]++;
		for( int j=1; j<radix; j++ )	cnt[j]=cnt[j]+cnt[j-1];
		for( int j=n-1; j>=0; j-- )	temp[--cnt[(array[j]/rtok)%radix]]=array[j];
		for( int j=0; j<n; j++ )	array[j] = temp[j];
	}

	delete []cnt;
	delete []temp;
}

void radixSort2( int* array, int n, int shift ){
	//用cnt[i]来保存桶bin[i]中的数据的个数
	int bins = 1<<shift;
	int* cnt = new int[bins];
	int mask=0x1;
	for( int i=0; i<shift; i++ )
		mask |= (1<<i);
	//用temp[]数组来临时存放数组array
	int* temp = new int[n];
	//首先求得数组的最大值，从而确定要循环多少轮
	int large = array[0];
	for( int i=1; i<n; i++ ){
		if( large < array[i] )
			large = array[i];
		}
	int k=0;
	while( large>0 ){
		k++;
		large = large>>shift;
	}
	int *A=array, *B=temp, *C;
	for( int i=0, rtok=0; i<k; i++, rtok +=shift ){
		for( int j=0; j<bins; j++ )	cnt[j] = 0;
		for( int j=0; j<n; j++ )	cnt[(A[j]>>rtok)&mask]++;
		for( int j=1; j<bins; j++ )	cnt[j]=cnt[j]+cnt[j-1];
		for( int j=n-1; j>=0; j-- )	B[--cnt[(A[j]>>rtok)&mask]]=A[j];
		C = A; A = B; B = C;
	}
	if( A!=array ){
		for( int j=0; j<n; j++ )
			array[j] = temp[j];
		}
	delete []cnt;
	delete []temp;
}

最后一种排序算法是堆排序，我打算在下一篇文章总结堆的时候再提HeapSort。