比较型排序算法总结

增量排序(shell 排序)：该算法的复杂度要略小于插入排序算法，但是也基本上认为是亚O(N^2)。实现的基本过程如下，选择一个较大的增量gap，一般选择为数组长度的一般作为起始的增量。然后从当前增量作为起始下标开始访问，比较a[i]和a[i-gap],如果a[i] a[0]，这是已经处理过的。如果a[i] >

void heapSort(int *a, int size)
{
int i = 0;
/*创建堆*/
Build_Maxheap(a,size);

for(i = size - 1; i > 0; --i)
{
/*swap(a[i],a[0])*/
a[i] = a[i] + a[0];
a[0] = a[i] - a[0];
a[i] = a[i] - a[0];
/*更新堆的结构*/
max_heapify(a,0,i);
}
}

归并排序：该算法的时间复杂度为O(NlogN)，使用的比较次数几乎是最优的，是递归算法的经典例子。

这个算法的基本操作是合并两个已经排序的表，因为这两个表是已经排序的，所以若将输出放到第三个表中则该算法可以通过对输入数据一趟排序来完成。基本的合并算法是取两个输入数组A和B，一个输出数组C以及3个计数器(Actr、Bctr、Cctr)，他们开始于对应数组的开始端，A[Actr]和B[Bctr]的较小者复制到C[ctr]中的一下一个位置，相关的计数器向前推进一步，当两个输入表有一个用完，则将另一个表中剩余的部分拷贝到C中。

由于该算法的前提是两个已经排序的表，但实际上的输入肯定不能满足条件，因此需要采用分治策略，所谓“分”就是将输入表分成两个表进行处理，对两个表分别采用分治进行排序。所谓“治”就是按照上述的算法合并两个排序表得到一个完整的排序表。由上面的分析可以知道，每一次分治都存在分开和合并操作，是经典的递归问题。需要注意的是在归并算法中临时数组的处理问题，采用动态存储的方式可能要简单好一些，但是需要注意内存的释放，避免内存泄露。

void mergeSort(int * a, int left, int right)
{
int i = 0;
int *atmp = NULL;
int *Actr = NULL, *Bctr = NULL, *Cctr = NULL;

/*递归退出条件*/
if(left >= right)
return;

atmp = (int *)calloc((right - left + 1) / 2,sizeof(int));
if(NULL == atmp)
return;

for(i = 0; i < (right - left + 1) / 2 ; ++ i)
atmp[i] = a[left + i];

mergeSort(atmp,0,i - 1);
mergeSort(a, left + i, right);

Actr = atmp;
Bctr = a + left + i;
Cctr = a + left;

while(Actr != atmp + i && Bctr != a + right + 1)
{
if(*Actr <= *Bctr)
*Cctr++ = *Actr++;
else
*Cctr++ = *Bctr++;
}
while(Actr != atmp + i)
*Cctr ++ = *Actr++;
while(Bctr != a + right + 1)
*Cctr ++ = *Bctr ++;

free(atmp);
atmp = NULL;
}

归并算法的时间复杂度的推导过程：

其中时间复杂度公式满足如下的等式T(N)=2T(N/2)+N，其中的N为合并操作的时间，推导过程如下:

归并排序存在的问题是，它很难应用于主存排序，主要问题在于合并两个排列的表需要线性附加内存，在整个算法中还需要花费将数据复制到临时数组在复制回来这样的一些附加操作，其结果是严重减慢了排序的速度。

快速排序：是实践中最快的已知排序算法，它的平均运行时间是O(NlogN)，算法之所以快是因为非常精炼和高度优化的内部循环，但是最坏的性能是O(N^2),将堆排序与快速排序结合，可以在堆排序的O(NlogN)最坏运行时间下，得到几乎所有输入的最快运行时间。

快速排序也是一种分治的递归算法，通常包括4个步骤：

1、如果数组S中元素个数为0或者1个，则直接返回

2、取数组S中的一个数v作为枢纽元。

3、将数组S-v划分成两个不相交的集合，其中S1:x <= v, S2: x > v.这一步需要注意不要写成是S1:x<=v,S2:x>=v，能减少很多的麻烦。

4、返回{quickSort(S1) , v, quickSort(S2)}。

上面的四步就完成了数组的快速排序，可见快速排序也是一个递归的过程，需要将多个子集进行。

快速排序的实现主要是第三步的实现，如何实现将数据分成两个集合的操作。实现的方式如下：

假设选择的枢纽元pivot是数组的开始值a[0]，那么将两个下标i,j分别表示数组的第1个数a[1](i = 1)和最后一个数a[N](j = N)，如果i < j，也就是数组长度大于2个时，将指向第一个数a[1]和枢纽元pivot进行比较，如果小于等于枢纽元则说明当前值是S1集合的，因此不需要移动，增加i指向下一个数a[2]，直到找到大于枢纽元的数a[i]，则i暂停增加，这时操作另一个下标j，比较j表征的数a[j]是否大于枢纽元pivot，如果大于则说明当前的数属于S2，不需要移动，减小j，直到找到小于等于枢纽元的数a[j]，如果i < j，则说明这两个数是需要改变位置的，因此调整两个数的位置swap(a[p],a[q])，然后接着上面的方法移动两个下标，并完成相应的交换操作，当两个下标表征相同的位置(j == i，这种情况是pivot = a[i])或者j < i(这种情况是不存在相同元素pivot != a[i])以后，说明集合分类操作已经完成，后一个j指向的位置就是当前枢纽元的位置，这时候小于j的下标的数据就是S1,而大于j的下标的数据就是S2。因此还需要将枢纽元a[0]与a[j]交换，得到枢纽元的位置。对于这种数组元素较大的情况，此时的j一般认为都是满足a[j] <= pivot。（等于的情况也是可能存在的）。