编程珠玑 -- 关于排序

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

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

//这份代码中，有两个地方可以改进//首先是(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[]数组来临时存放数组arrayint* 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[]数组来临时存放数组arrayint* 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。