比较型排序算法总结

插入排序算法：该算法的复杂度为O(N^2),需要比对N-1趟，最坏情况下，每一趟比对的元素个数会随着i的增加而增加。比如进行到了第k+1趟，实际上就是假设了前k个元素是有序的，这时候只需要将a[k+1]与a[k]比较，如果a[k+1]大于a[k]则说明a[k+1]是目前最大的数，如果a[k+1] < a[k].这时说明a[k]的位置不对，需要往后移动，也就是a[k+1]中保存a[k]的值，可以将a[k+1]的值与a[k]交换。然后比较a[k]与a[k-1]，直到找到该元素的合适位置。

void insertSort(int *a, int size)
{
int i = 0, j = 0, tmp = 0;
for(i = 1; i < size; ++ i)
{
tmp = a[i];
for(j = i; j > 0 && tmp < a[j-1]; --j)
a[j] = a[j - 1];
a[j] = tmp;
}
}

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

voidshellSort(int *a, int size)
{
int i = 0, j = 0, gap = 0.
int tmp = 0;

/*选择合适的增量*/
for(gap = size / 2; gap > 0; gap /= 2 )
{
/*以增量为下标进行比较*/
for( i = gap ; i < size ; ++ i)
{
/*找到比较数的位置*/
tmp = a[i];
for(j = i; j >= gap && tmp < a[j - gap]; j -= gap)
a[j] = a[j - gap];/*更新a[j-gap]的位置*/
a[j] = tmp; /*找到比较数的位置*/
}
}
}

堆排序：堆排序的实现主要是采用了最小堆或者最大堆的特性，堆中的根元素肯定是最小元素或者最大元素，删除其中的根元素实质上就找到了最大/最小值。这样通过N次删除就找到了一个有序序列。我们知道在二叉堆中删除和插入操作采用了上虑和下虑的方式，每次删除和插入操作的时间复杂度为O(logN)。但是堆排序存在一个堆的创建问题，这个创建是非常的浪费时间的，时间复杂度为O(N)，这样一个堆排序的操作事件大约为O(NlogN)。相比前面的两种方式要快速。实现的过程如下，分配一个新的内存空间，遍历元素N，创建一个二叉堆数组，然后执行N次删除操作，删除的元素添加到原来的内存空间中，实现了数组的排序操作，这种方式时间复杂度上有所减小，但是空间复杂度上却有了很大的增加，存储容量增加了近一倍。

聪明的解决方式根据堆的性质，删除一个元素就会释放最后的一个存储单元，这时候将删除的元素保存到释放存储单元中，然后删除一个元素就保存到释放的内存中去，就能避免存储量增加的问题。但是这时候出现的序列就是一个反序，但总归是有序序列。当然也可以通过创建(Max)堆来得到min序列，创建(Min)堆来得到max序列。因此堆排序的基本模型就是创建一个堆，删除堆元素的操作过程。

堆排序是非常稳定的算法，他平均使用的比较只比最坏情形下指出的略少，堆排序总是使用至少NlogN-O(N)次排序，而且存在能够到达这个界的输入数据。

void max_heapify(int *a,int index, int size)
{
int child = LEFTSON(index);

int tmp = a[index];

for(; LEFTSON(index) < size ; index = child)
{
child = LEFTSON(index);
if(child != size - 1 && a[child] < a[child + 1])
child ++;

/***************************
* 提升儿子到父结点，
* 儿子结点的位置上存在空穴，
* 需要继续比较
**************************/
if(a[child] > tmp)
a[index] = a[child];
else/*不需要提升*/
break;
}
/*保存结点的位置找到*/
a[index] = tmp;
}

void Build_Maxheap(int *a, int size)
{
int step = 0;

/***************************************
* (size-1)/2实质是找到a[size-1]的父结点，
* 也就是倒数第二层，堆的创建过程是一个
* 由低层到高层逐渐创建的过程
**************************************/
for(step = (size - 1) / 2 ; step >= 0; -- step)
max_heapify(a, step, size);
}

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。（等于的情况也是可能存在的）。