转载请注明出处
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<nLength)nArray[i] = nDestArray[i++];
return 0;
}
~~~
它的时间复杂度是O(nlog2n)。
代码下载地址:
http://download.csdn.net/detail/pony_maggie/7568971
或
https://github.com/pony-maggie/SortDemo
