原文位址為： 【每日算法】C語言8大經典排序算法（1）
算法一直是程式設計的基礎，而排序算法是學習算法的開始，排序也是資料處理的重要内容。所謂排序是指将一個無序列整理成按非遞減順序排列的有序序列。排列的方法有很多，根據待排序序列的規模以及對資料的處理的要求，可以采用不同的排序方法。那麼就整理下網上搜尋的資料，按自己的了解，把C語言的8大排序算法列出來。
普通意義上，排序算法可以分為三大類：
1 交換類排序法
2 插入類排序法
3 選擇類排序法
一.交換類排序法
所謂交換排序法是指借助資料元素之間互相交換進行排序的方法。冒泡排序與快速排序法都屬于交換類排序方法。
1、冒泡排序（BubbleSort）
冒泡排序的基本概念：
依次比較相鄰的兩個數，将小數放在前面，大數放在後面。即在第一趟：首先比較第1個和第2個數，将小數放前，大數放後。然後比較第2個數和第3個數，将小數放前，大數放後，如此繼續，直至比較最後兩個數，将小數放前，大數放後。至此第一趟結束，将最大的數放到了最後。在第二趟：仍從第一對數開始比較（因為可能由于第2個數和第3個數的交換，使得第1個數不再小于第2個數），将小數放前，大數放後，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到一個新的最大數（其實在整個數列中是第二大的數）。如此下去，重複以上過程，直至最終完成排序。由于在排序過程中總是小數往前放，大數往後放，相當于氣泡往上升，是以稱作冒泡排序。
實作：
外循環變量設為i，内循環變量設為j。假如有10個數需要進行排序，則外循環重複9次，内循環依次重複9，8，...，1次。每次進行比較的兩個元素都是與内循環j有關的，它們可以分别用a[j]和a[j+1]辨別，i的值依次為1,2,...,9，對于每一個i,j的值依次為1,2,...10-i。
圖示：
C語言實作：
1 void Bublesort(int a[],int n)
2 {
3 int i,j,k;
4 for(j=0;j<n;j++) /* 氣泡法要排序n次*/
5 {
6 for(i=0;i<n-j;i++) /* 值比較大的元素沉下去後，隻把剩下的元素中的最大值再沉下去就可以啦 */
7 {
8 if(a[i]>a[i+1]) /* 把值比較大的元素沉到底 */
9 {
10 k=a[i];
11 a[i]=a[i+1];
12 a[i+1]=k;
13 }
14 }
15 }
16 } 性能分析：
若記錄序列的初始狀态為"正序"，則冒泡排序過程隻需進行一趟排序，在排序過程中隻需進行n-1次比較，且不移動記錄；反之，若記錄序列的初始狀态為"逆序"，則需進行n(n-1）/2次比較和記錄移動。是以冒泡排序總的時間複雜度為O(n*n)。
部落格園中，有一篇博文是關于冒泡算法的優化，可以看下，兩種優化：
白話經典算法系列之一 冒泡排序的三種實作
2、快速排序（Quicksort）
基本思想：
快速排序是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。
實作： 設要排序的數組是A[0]……A[N-1]，首先任意選取一個資料（通常選用第一個資料）作為關鍵資料，然後将所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結束時産生變動。 一趟快速排序的算法是： 1）設定兩個變量i、j，排序開始的時候：i=0，j=N-1； 2）以第一個數組元素作為關鍵資料，指派給 key，即 key=A[0]； 3）從j開始向前搜尋，即由後開始向前搜尋（j -- ），找到第一個小于 key的值A[j]，A[i]與A[j]交換； 4）從i開始向後搜尋，即由前開始向後搜尋（i ++ ），找到第一個大于 key的A[i]，A[i]與A[j]交換； 5）重複第3、4、5步，直到 I=J； (3,4步是在程式中沒找到時候j=j-1，i=i+1，直至找到為止。找到并交換的時候i， j指針位置不變。另外當i=j這過程一定正好是i+或j-完成的最後令循環結束。） 圖示：
舉例說明：
如無序數組[6 2 4 1 5 9]
a),先把第一項[6]取出來,
用[6]依次與其餘項進行比較,
如果比[6]小就放[6]前邊,2 4 1 5都比[6]小,是以全部放到[6]前邊
如果比[6]大就放[6]後邊,9比[6]大,放到[6]後邊,//6出列後大喝一聲,比我小的站前邊,比我大的站後邊,行動吧!霸氣十足~
一趟排完後變成下邊這樣:
排序前 6 2 4 1 5 9
排序後 2 4 1 5 6 9
b),對前半拉[2 4 1 5]繼續進行快速排序
重複步驟a)後變成下邊這樣:
排序前 2 4 1 5
排序後 1 2 4 5
前半拉排序完成,總的排序也完成:
排序前:[6 2 4 1 5 9]
排序後:[1 2 4 5 6 9]
C語言實作：
1 int partition(int *data,int low,int high)
2
3 {
4 int t = 0;
5
6 t = data[low];
7
8 while(low < high)
9
10 { while(low < high && data[high] >= t)
11
12 high--;
13
14 data[low] = data[high];
15
16 while(low < high && data[low] <= t)
17
18 low++;
19
20 data[high] = data[low];
21
22 }
23
24 data[low] = t;
25
26 return low;
27
28 }
29
30 void sort(int *data,int low,int high) //快排每趟進行時的樞軸要重新确定，由此進 //一步确定每個待排小記錄的low及high的值
31
32 { if(low >= high)
33
34 return ;
35
36 int pivotloc = 0;
37
38 pivotloc = partition(data,low,high);
39
40 sort(data,low,pivotloc-1);
41
42 sort(data,pivotloc+1,high);
43
44 } 性能分析
快速排序的時間主要耗費在劃分操作上，對長度為k的區間進行劃分，共需k-1次關鍵字的比較。
最壞情況是每次劃分選取的基準都是目前無序區中關鍵字最小(或最大)的記錄，劃分的結果是基準左邊的子區間為空(或右邊的子區間為空)，而劃分所得的另一個非空的子區間中記錄數目，僅僅比劃分前的無序區中記錄個數減少一個。時間複雜度為O(n*n)
在最好情況下，每次劃分所取的基準都是目前無序區的"中值"記錄，劃分的結果是基準的左、右兩個無序子區間的長度大緻相等。總的關鍵字比較次數：O(nlgn)
盡管快速排序的最壞時間為O(n2)，但就平均性能而言，它是基于關鍵字比較的内部排序算法中速度最快者，快速排序亦是以而得名。它的平均時間複雜度為O(nlgn)。
這裡有一個視訊比較形象地說明了這兩個有趣的排序算法：http://www.tudou.com/programs/view/htKY1-Rj9ZE/?resourceId=0_06_02_99
轉載請注明本文位址： 【每日算法】C語言8大經典排序算法（1）