转载请注明出处
http://blog.csdn.net/pony_maggie/article/details/36706131
作者:小马
一希尔排序
上一篇讲到的直接插入排序，时间复杂度O(n^2). 请在脑海里想一下它的过程。假设一个序列本来就是有序的，对它排序的时间复杂度是O(n)。
所以当序列基本有序时，插入排序排序的效率大大提高，由于降低了移动的动作。
另外，直接插入排序另一个特点，当n比較小时，它的效率比較高。
希尔排序正是基于上面两个思想做的一种改进算法。它先将整个序列分成若干个小序列。对每一个小序列做直接插入排序，这样整个序列变得“基本有序”，然后对整个序列做一次直接插入排序，得到终于结果。只是希尔排序并非简单地逐段切割，而用相隔某个增量的记录组成一个序列。例如以下图所看到的:
一開始增量为3, 有三组，{9，8。4}， {1。 3。 6}。{5，7，2}，分别直接插入排序得到2图,然后添加变为2，继续上面的过程，最后当增量为1时，数组就有序了。三趟排序用的增量构造一个增量序列{3,2,1}。这个不是固定的。可是一个好的增量序列，应该没有除1以外的公因子，而且最后一个增量必须等于1。思路非常清晰了，上代码吧。
//一趟插入排序, dk是单次的增量static void shellInsert(int nArray[], int nLength, int dk){ int i = 0; int j = 0; int nSerity = 0; for (i = dk; i < nLength; i++) { if (nArray[i] < nArray[i-dk]) { nSerity = nArray[i]; for (j = i-dk; (j >= 0)&&(nSerity < nArray[j]); j-=dk) { nArray[j+dk] = nArray[j]; } nArray[j+dk] = nSerity; } }}int shellSort(int nArray[], int nLength){ int k = 0; int dkArray[] = {3, 2, 1}; //默认使用的增量序列 int dkLength = 3; for (k = 0; k < dkLength; k++) { shellInsert(nArray, nLength, dkArray[k]); } return 0;} 它的复杂度计算涉及到一些数学难题，你仅仅要知道它的效率比較直接插入排序要高一些即可了。
二高速排序
有些地方会提到高速排序是对冒泡排序的一种改进，我倒是认为不要这么联想，会误导你学习高速排序。
高速排序思想先选取一个“枢纽元素”，一般就是序列的第一个元素。
把比这个枢纽小的数据放一边，比它大的放还有一边。这样一趟之后序列变为, 一部分中的全部元素都比还有一部分中的全部元素小，可是部分之间的记录可能是无序的。
然后对每一部分再用样的思想继续分，最后就变为有序序列。例如以下图所看到的:
通过上面的步骤，自然想到用递归来实现高速排序，没错，上代码。
static int partition(int nArray[], int nLow, int nHigh){ int nPivot = nArray[nLow]; while (nLow < nHigh) { while ((nLow < nHigh) && (nArray[nHigh] >= nPivot)) nHigh--; nArray[nLow] = nArray[nHigh]; while ((nLow < nHigh) && (nArray[nLow] <= nPivot)) nLow++; nArray[nHigh] = nArray[nLow]; } nArray[nLow] = nPivot; return nLow;}static void sortProcess(int nArray[], int nLow, int nHigh){ int nPartition = 0; if (nLow < nHigh) { nPartition = partition(nArray, nLow, nHigh); sortProcess(nArray, nLow, nPartition-1); sortProcess(nArray, nPartition+1, nHigh); }}int quickSort(int nArray[], int nLength){ sortProcess(nArray, 0, nLength-1); return 0;} 高速排序时间复杂度是O(nlogn),是眼下公认的效率比較高的排序算法。
三归并排序
归并排序算是一种比較特殊的排序算法，它将两个有序表(长度各自是m,n)合并成还有一个有序表。这个动作可在O(m+n)的时间复杂度实现。对于个有n个元素的无序序列，能够看成n个有序的子序列，然后两两归并。得到一个n/2长度为2或1(想想为什么有1)的有序子序列，继续两两归并，直接得到一个长度为n的有序序列为止。
例如以下图所看到的:
这里我们用递归的方法来实现，好理解一些，非递归的方法稍复杂一些。
代码例如以下:
//将有序的srcArray[i..m]和srcArray[m+1..n],归并到destArray[i..n]static void Merge(int srcArray[], int destArray[], int i, int m, int n){ int j = 0; int k = 0; for (j = m+1,k=i; (i<=m)&&(j<=n); ++k) { if (srcArray[i] < srcArray[j]) { destArray[k] = srcArray[i++]; } else { destArray[k] = srcArray[j++]; } } //剩下的直接拷过来 while (i <= m) { destArray[k++] = srcArray[i++]; } while (j <= n) { destArray[k++] = srcArray[j++]; }}static void MSort(int srcArray[], int destArray[], int s,int t){ int m = 0; int destArray2[256] = {0}; //辅助数组,空间依据实际情况分配. if (s == t) { destArray[s] = srcArray[s]; } else { m = (s + t)/2; MSort(srcArray, destArray2, s, m); MSort(srcArray, destArray2, m+1, t); Merge(destArray2, destArray, s, m, t); }}//递归方法实现归并排序int MergeSort(int nArray[], int nLength){ int nDestArray[256] = {0}; int i = 0; MSort(nArray, nDestArray, 0, nLength-1); while (i 它的时间复杂度是O(nlog2n)。
代码下载地址:
http://download.csdn.net/detail/pony_maggie/7568971
或
https://github.com/pony-maggie/SortDemo