排序是算法中最根底的问题之一，经典的排序算法是前人不断总结得到的，依据比较的办法是比较直观的办法，首要存在刺进法排序、堆排序、增量排序（shell排序）、归并排序、快速排序，每一种排序算法都有自己的优缺点，比方刺进法排序适用于那些长度短的排序，关于长的表，有些无能为力啊，堆排序首要是依据了二叉堆的特性，可是创立堆的进程也是一个杂乱的问题，增量排序的进程是一个不断准确的进程，可是现在也仅仅一个经历办法。归并排序是一个递归的问题，选用分治的思维完结，可是这种算法需求额定的存储空间，快速排序虽然是实践中比较常用的算法，可是关于有序的数组选用快速排序便是灾祸。比较型算法的时刻杂乱度最优也只能抵达O(NlogN)。
刺进排序算法：该算法的杂乱度为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。（等于的状况也是或许存在的）。
