排序是算法中最基礎的問題之一，經典的排序算法是前人不斷總結得到的，基于比較的方法是比較直觀的方式，主要存在插入法排序、堆排序、增量排序（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[i-gap]則交換兩個值，并令i = i - gap，交換完成以后接著比較a[i] < a[i-gap]，直到 i < gap，因為a[gap] > a[0]，這是已經處理過的。如果a[i] > a[i-gap]則不處理。減小gap,一般去gap = gap/2。重新進行上面的操作，直到gap = 1，因為這時候已經滿足a[i]<a[i+1],實現了基本的排序操作。依據的基本關系式為a[i] < a[i + gap]，這個關系式說明了a[i], a[i+gap], a[i+2gap],a[i+3gap],…是一個有序的序列。
void shellSort(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。（等于的情況也是可能存在的）。
但是存在一個特殊情況，如果操作的數組只存在兩個數據時，這種劃分方法就存在一些問題，因為一開始兩個下標i,j就指向了相同的位置，這時候如果a[0]大于a[1] ，那么經過上面的操作以后j = 0, i = 1，這時候的pivot應該是放在a[1]處，但是根據上面的條件可知，集合劃分至少需要三個元素，但是我們可以比較樞紐元與當前a[j]的值，對于兩種情況下都滿足交換的條件就是a[j] < pivot,因此只要當這個條件滿足是就交換a[j]和a[0]。上述的操作我們稱之為集合劃分操作。
int Partition(int *a, int left, int right)
{
/*采用第一個元素作為樞紐元*/
int pivot = a[left];
int i = left + 1;
int j = right;
/*只有一個元素，實際上不用進行任何操作，直接返回*/
if(i > j)
return j;
/*實際上存在一個問題就是i== j，這時候數組有兩個值*/
while(1)
{
/*跳過所有小于等于pivot的值，同時設置邊界條件*/
while(a[i] <= pivot && i < right)
++ i ;
/*跳過所有大于pivot的值，同時設置邊界條件*/
while(pivot < a[j] && j > left)
-- j ;
/*******************************************
*如果 i < j，則說明數組之間存在間隔
*上面的條件全部不滿足則說明找到S1，S2需要交換的數
*一般當存在相同的數時，會存在i == j，這時實際上
*a[left] = a[j]
*一般都會產生i > j,這種情況發生在i+1=j時的交換操作
*交換操作完成以后i++,j--，使得i < j.
*******************************************/
if(i < j)
swap(&a[i ],&a[j]);
else
break;
}
/******************************************************
根據上面的分析實際上j下標指向的數數都是小于或者等于pivot的
等于pivot時就不需要交換a[left]和a[j],只需要返回樞紐元應該的位置即可，
同時也解決了只有兩個數值的數組問題。
*******************************************************/
if(pivot > a[j])
swap(&a[left],&a[j]);
/*返回樞紐元應該存在的位置*/
return j;
}
/*傳統的快速排序算法*/
void t_quickSort(int *a, int left, int right)
{
int i = 0;
/*如果left小于right*/
if(left < right)
{
/*找到樞紐元的位置，并劃分了兩個集合S1,S2*/
i = Partition(a,left,right);
/*S1集合排序*/
t_quickSort(a, left , i - 1);
/*S2集合排序*/
t_quickSort(a, i + 1, right);
}
}
但是這種方法存在一個比較嚴重的問題，就是如果當數組是一個已經完成排序的情況，采用快速排序的時間復雜度將是災難性的。此時的時間復雜度為O(N^2),也就是最壞的情況，為了解決這種問題，采用了其他的解決方案，改變樞紐元的選擇決策，采用隨機選取或者三值的中值作為樞紐元。樞紐元的選擇能避免有序數組的快速排序問題。還有就是當數組的長度較小時，采用插入法等常規方法的速度更快，而且如上面分析所示，劃分集合的問題至少需要三個元素，雖然上面的方法能夠解決只有兩個元素的情況，但是如果考慮不周全就很難解決。可以根據長度來選擇具體的排序排序方法，也就是當長度小于10時采用插入法排序，而當大于10時就直接采用快速排序，這時候的注意事項就比較少，不用考慮數組長度是否為2等。采用改良型的快速排序算法如下所示。
/*快速排序*/
void insertionSort(int *a, int left, int right)
{
int i = 0, j = 0;
int tmp = 0;
if(left >= right)
return;
for( i = left + 1; i <= right; ++ i)
{
tmp = a[i];
for(j = i; j > left && tmp < a[j - 1]; -- j)
a[j] = a[j - 1];
a[j] = tmp;
}
}
/*數據交換*/
void swap(int *a, int *b)
{
if(a != b)
{
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
}
/*選擇合適的樞紐元函數*/
int median(int *a, int left, int right)
{
int mid = (right + left) / 2;
if(a[mid] < a[left])
swap(&a[mid], &a[left]);
if(a[right] < a[left])
swap(&a[right], &a[left]);
if(a[right] < a[mid])
swap(&a[right], &a[mid]);
swap(&a[mid],&a[right - 1]);
return a[right - 1];
}
/*實現快速排序的實際函數*/
void quickSort(int *a, int left, int right)
{
int i = left, j = right - 1;
int pivot = 0;
if(left + 10 <= right)
{
/*選擇樞紐元*/
pivot = median(a,left,right);
while(1)
{
/*找到大于pivot的下標*/
while(a[++ i] <= pivot){}
/*找到不大于pivot的下標*/
while(a[--j] > pivot){}
if(i < j)
swap(&a[i],&a[j]);
else
break;
}
/*確定樞紐元的位置*/
swap(&a[i],&a[right - 1]);
quickSort(a,left,i - 1);
quickSort(a,i + 1,right);
}
else/*小長度的數組采用插入法排序*/
insertionSort(a, left,right);
}
void QuickSort(int *a, int size)
{
quickSort(a,0,size - 1);
}
時間復雜度的測試，首先測試有序數組的排序操作，測試代碼和算法效果如下所示：
#define LEN 100000
int main()
{
int i = 0;
int a[LEN];
int b[LEN];
int c[LEN];
int d[LEN];
int e[LEN];
clock_t _start, _end;
double times = 0;
srand((int)time(0));
for(i = 0; i < LEN; ++ i)
{
a[i] = i;
b[i] = a[i];
c[i] = a[i];
d[i] = a[i];
e[i] = a[i];
}
_start = clock();
TQuickSort(a,LEN);
_end = clock();
times = (double)(_end - _start)/CLOCKS_PER_SEC;
printf("The QuickSort took %fs\n",times);
_start = clock();
QuickSort(b,LEN);
_end = clock();
times = (double)(_end - _start)/CLOCKS_PER_SEC;
printf("The Changed QuickSort took %fs\n",times);
#if 10
_start = clock();
MergeSort(c,LEN);
_end = clock();
times = (double)(_end - _start)/CLOCKS_PER_SEC;
printf("The MergeSort took %fs\n",times);
_start = clock();
InsertionSort(d,LEN);
_end = clock();
times = (double)(_end - _start)/CLOCKS_PER_SEC;
printf("The InsertionSort took %fs\n",times);
_start = clock();
heapSort(e,LEN);
_end = clock();
times = (double)(_end - _start)/CLOCKS_PER_SEC;
printf("The heapSort took %fs\n",times);
#endif
return 0;
}
結果如下：
[gong@Gong-Computer sort]$ ./quickSort
The QuickSort took 12.850000s
The Changed QuickSort took 0.000000s
The MergeSort took 0.030000s
The InsertionSort took 0.000000s
The heapSort took 0.020000s
從上面的實驗結果可知，當為有序數組時，快速排序的速度并不快，甚至是最慢的。插入排序反而是最快的方式。同時我們可以發現采用上面的改進的快速排序算法排序速度很快，并不像傳統的算法那么費時間。
測試采用隨機數產生的數組進行排序時的實驗效果：
[gong@Gong-Computer sort]$ ./quickSort
The QuickSort took 0.020000s
The Changed QuickSort took 0.010000s
The MergeSort took 0.030000s
The InsertionSort took 15.240000s
The heapSort took 0.020000s
從上面的結果可知，對于非有序的數組，快速排序的效果是非常好的，但是插入排序就非常的差勁啦。