比較型排序算法總結

插入排序算法：該算法的復雜度為O(N^2),需要比對N-1趟，最壞情況下，每一趟比對的元素個(gè)數會(huì )隨著(zhù)i的增加而增加。比如進(jìn)行到了第k+1趟，實(shí)際上就是假設了前k個(gè)元素是有序的，這時(shí)候只需要將a[k+1]與a[k]比較，如果a[k+1]大于a[k]則說(shuō)明a[k+1]是目前最大的數，如果a[k+1] < a[k].這時(shí)說(shuō)明a[k]的位置不對，需要往后移動(dòng)，也就是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)。實(shí)現的基本過(guò)程如下，選擇一個(gè)較大的增量gap，一般選擇為數組長(cháng)度的一般作為起始的增量。然后從當前增量作為起始下標開(kāi)始訪(fǎng)問(wèn)，比較a[i]和a[i-gap],如果a[i] a[0]，這是已經(jīng)處理過(guò)的。如果a[i] > a[i-gap]則不處理。減小gap,一般去gap = gap/2。重新進(jìn)行上面的操作，直到gap = 1，因為這時(shí)候已經(jīng)滿(mǎn)足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 )
{
/*以增量為下標進(jìn)行比較*/
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; /*找到比較數的位置*/
}
}
}

堆排序：堆排序的實(shí)現主要是采用了最小堆或者最大堆的特性，堆中的根元素肯定是最小元素或者最大元素，刪除其中的根元素實(shí)質(zhì)上就找到了最大/最小值。這樣通過(guò)N次刪除就找到了一個(gè)有序序列。我們知道在二叉堆中刪除和插入操作采用了上慮和下慮的方式，每次刪除和插入操作的時(shí)間復雜度為O(logN)。但是堆排序存在一個(gè)堆的創(chuàng )建問(wèn)題，這個(gè)創(chuàng )建是非常的浪費時(shí)間的，時(shí)間復雜度為O(N)，這樣一個(gè)堆排序的操作事件大約為O(NlogN)。相比前面的兩種方式要快速。實(shí)現的過(guò)程如下，分配一個(gè)新的內存空間，遍歷元素N，創(chuàng )建一個(gè)二叉堆數組，然后執行N次刪除操作，刪除的元素添加到原來(lái)的內存空間中，實(shí)現了數組的排序操作，這種方式時(shí)間復雜度上有所減小，但是空間復雜度上卻有了很大的增加，存儲容量增加了近一倍。

聰明的解決方式根據堆的性質(zhì)，刪除一個(gè)元素就會(huì )釋放最后的一個(gè)存儲單元，這時(shí)候將刪除的元素保存到釋放存儲單元中，然后刪除一個(gè)元素就保存到釋放的內存中去，就能避免存儲量增加的問(wèn)題。但是這時(shí)候出現的序列就是一個(gè)反序，但總歸是有序序列。當然也可以通過(guò)創(chuàng )建(Max)堆來(lái)得到min序列，創(chuàng )建(Min)堆來(lái)得到max序列。因此堆排序的基本模型就是創(chuàng )建一個(gè)堆，刪除堆元素的操作過(guò)程。

堆排序是非常穩定的算法，他平均使用的比較只比最壞情形下指出的略少，堆排序總是使用至少NlogN-O(N)次排序，而且存在能夠到達這個(gè)界的輸入數據。

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 ++;

/***************************
* 提升兒子到父結點(diǎn)，
* 兒子結點(diǎn)的位置上存在空穴，
* 需要繼續比較
**************************/
if(a[child] > tmp)
a[index] = a[child];
else/*不需要提升*/
break;
}
/*保存結點(diǎn)的位置找到*/
a[index] = tmp;
}

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

/***************************************
* (size-1)/2實(shí)質(zhì)是找到a[size-1]的父結點(diǎn)，
* 也就是倒數第二層，堆的創(chuàng )建過(guò)程是一個(gè)
* 由低層到高層逐漸創(chuàng )建的過(guò)程
**************************************/
for(step = (size - 1) / 2 ; step >= 0; -- step)
max_heapify(a, step, size);
}

void heapSort(int *a, int size)
{
int i = 0;
/*創(chuàng )建堆*/
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);
}
}

歸并排序：該算法的時(shí)間復雜度為O(NlogN)，使用的比較次數幾乎是最優(yōu)的，是遞歸算法的經(jīng)典例子。

這個(gè)算法的基本操作是合并兩個(gè)已經(jīng)排序的表，因為這兩個(gè)表是已經(jīng)排序的，所以若將輸出放到第三個(gè)表中則該算法可以通過(guò)對輸入數據一趟排序來(lái)完成?；镜暮喜⑺惴ㄊ侨蓚€(gè)輸入數組A和B，一個(gè)輸出數組C以及3個(gè)計數器(Actr、Bctr、Cctr)，他們開(kāi)始于對應數組的開(kāi)始端，A[Actr]和B[Bctr]的較小者復制到C[ctr]中的一下一個(gè)位置，相關(guān)的計數器向前推進(jìn)一步，當兩個(gè)輸入表有一個(gè)用完，則將另一個(gè)表中剩余的部分拷貝到C中。

由于該算法的前提是兩個(gè)已經(jīng)排序的表，但實(shí)際上的輸入肯定不能滿(mǎn)足條件，因此需要采用分治策略，所謂“分”就是將輸入表分成兩個(gè)表進(jìn)行處理，對兩個(gè)表分別采用分治進(jìn)行排序。所謂“治”就是按照上述的算法合并兩個(gè)排序表得到一個(gè)完整的排序表。由上面的分析可以知道，每一次分治都存在分開(kāi)和合并操作，是經(jīng)典的遞歸問(wèn)題。需要注意的是在歸并算法中臨時(shí)數組的處理問(wèn)題，采用動(dòng)態(tài)存儲的方式可能要簡(jiǎn)單好一些，但是需要注意內存的釋放，避免內存泄露。

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;
}

歸并算法的時(shí)間復雜度的推導過(guò)程：

其中時(shí)間復雜度公式滿(mǎn)足如下的等式T(N)=2T(N/2)+N，其中的N為合并操作的時(shí)間，推導過(guò)程如下:

歸并排序存在的問(wèn)題是，它很難應用于主存排序，主要問(wèn)題在于合并兩個(gè)排列的表需要線(xiàn)性附加內存，在整個(gè)算法中還需要花費將數據復制到臨時(shí)數組在復制回來(lái)這樣的一些附加操作，其結果是嚴重減慢了排序的速度。

快速排序：是實(shí)踐中最快的已知排序算法，它的平均運行時(shí)間是O(NlogN)，算法之所以快是因為非常精煉和高度優(yōu)化的內部循環(huán)，但是最壞的性能是O(N^2),將堆排序與快速排序結合，可以在堆排序的O(NlogN)最壞運行時(shí)間下，得到幾乎所有輸入的最快運行時(shí)間。

快速排序也是一種分治的遞歸算法，通常包括4個(gè)步驟：

1、如果數組S中元素個(gè)數為0或者1個(gè)，則直接返回

2、取數組S中的一個(gè)數v作為樞紐元。

3、將數組S-v劃分成兩個(gè)不相交的集合，其中S1:x <= v, S2: x > v.這一步需要注意不要寫(xiě)成是S1:x<=v,S2:x>=v，能減少很多的麻煩。

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

上面的四步就完成了數組的快速排序，可見(jiàn)快速排序也是一個(gè)遞歸的過(guò)程，需要將多個(gè)子集進(jìn)行。

快速排序的實(shí)現主要是第三步的實(shí)現，如何實(shí)現將數據分成兩個(gè)集合的操作。實(shí)現的方式如下：

假設選擇的樞紐元pivot是數組的開(kāi)始值a[0]，那么將兩個(gè)下標i,j分別表示數組的第1個(gè)數a[1](i = 1)和最后一個(gè)數a[N](j = N)，如果i < j，也就是數組長(cháng)度大于2個(gè)時(shí)，將指向第一個(gè)數a[1]和樞紐元pivot進(jìn)行比較，如果小于等于樞紐元則說(shuō)明當前值是S1集合的，因此不需要移動(dòng)，增加i指向下一個(gè)數a[2]，直到找到大于樞紐元的數a[i]，則i暫停增加，這時(shí)操作另一個(gè)下標j，比較j表征的數a[j]是否大于樞紐元pivot，如果大于則說(shuō)明當前的數屬于S2，不需要移動(dòng)，減小j，直到找到小于等于樞紐元的數a[j]，如果i < j，則說(shuō)明這兩個(gè)數是需要改變位置的，因此調整兩個(gè)數的位置swap(a[p],a[q])，然后接著(zhù)上面的方法移動(dòng)兩個(gè)下標，并完成相應的交換操作，當兩個(gè)下標表征相同的位置(j == i，這種情況是pivot = a[i])或者j < i(這種情況是不存在相同元素pivot != a[i])以后，說(shuō)明集合分類(lèi)操作已經(jīng)完成，后一個(gè)j指向的位置就是當前樞紐元的位置，這時(shí)候小于j的下標的數據就是S1,而大于j的下標的數據就是S2。因此還需要將樞紐元a[0]與a[j]交換，得到樞紐元的位置。對于這種數組元素較大的情況，此時(shí)的j一般認為都是滿(mǎn)足a[j] <= pivot。（等于的情況也是可能存在的）。