一、前言
如果說各種編程語言是程式員的招式，那么資料結構和演算法就相當于程式員的內功，
想寫出精煉、優秀的代碼，不通過不斷的錘煉，是很難做到的，
二、八大排序演算法
排序演算法作為資料結構的重要部分，系統地學習一下是很有必要的，
1、排序的概念
排序是計算機內經常進行的一種操作，其目的是將一組“無序”的記錄序列調整為“有序”的記錄序列，
排序分為內部排序和外部排序，
若整個排序程序不需要訪問外存便能完成，則稱此類排序問題為內部排序，
反之，若參加排序的記錄數量很大，整個序列的排序程序不可能在記憶體中完成，則稱此類排序問題為外部排序，
2、排序分類
八大排序演算法均屬于內部排序，如果按照策略來分類，大致可分為：交換排序、插入排序、選擇排序、歸并排序和基數排序，如下圖所示：
3、演算法分析
1.插入排序：
● 直接插入排序
● 希爾排序
2.選擇排序
● 簡單選擇排序
● 堆排序
3.交換排序
● 冒泡排序
● 快速排序
4.歸并排序
5.基數排序
不穩定排序：簡單選擇排序，快速排序，希爾排序，堆排序
穩定排序：冒泡排序，直接插入排序，歸并排序，奇數排序
三、具體排序講解
下面針對不同排序進行一一講解，
一、直接插入排序（Insertion Sort)
演算法思想：
直接插入排序的核心思想就是：將陣列中的所有元素依次跟前面已經排好的元素相比較，如果選擇的元素比已排序的元素小，則交換，直到全部元素都比較過 因此，從上面的描述中我們可以發現，直接插入排序可以用兩個回圈完成：
? 第一層回圈：遍歷待比較的所有陣列元素
? 第二層回圈：將本輪選擇的元素(selected)與已經排好序的元素(ordered)相比較，如果：selected > ordered，那么將二者交換，
演算法代碼：
void print(int a[], int n ,int i){ cout<<i <<":"; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl; } void InsertSort(int a[], int n) { for(int i= 1; i<n; i++){ if(a[i] < a[i-1]){ //若第i個元素大于i-1元素，直接插入，小于的話，移動有序表后插入 int j= i-1; int x = a[i]; //復制為哨兵，即存盤待排序元素 a[i] = a[i-1]; //先后移一個元素 while(x < a[j]){ //查找在有序表的插入位置 a[j+1] = a[j]; j--; //元素后移 } a[j+1] = x; //插入到正確位置 } print(a,n,i); //列印每趟排序的結果 } } int main(){ int a[8] = {3,1,5,7,2,4,9,6}; InsertSort(a,8); print(a,8,8); }
————————
二、希爾排序（Shell' s Sort）
演算法思想:
希爾排序也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本，但希爾排序是非穩定排序演算法，
希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序，
演算法步驟：
1.選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2.按增量序列個數k，對序列進行k 趟排序；
3.每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序，僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度，
演算法代碼:
void print(int a[], int n ,int i){ cout<<i <<":"; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl; } /** * 直接插入排序的一般形式 * * @param int dk 縮小增量，如果是直接插入排序，dk=1 * */ void ShellInsertSort(int a[], int n, int dk) { for(int i= dk; i<n; ++i){ if(a[i] < a[i-dk]){ //若第i個元素大于i-1元素，直接插入，小于的話，移動有序表后插入 int j = i-dk; int x = a[i]; //復制為哨兵，即存盤待排序元素 a[i] = a[i-dk]; //首先后移一個元素 while(x < a[j]){ //查找在有序表的插入位置 a[j+dk] = a[j]; j -= dk; //元素后移 } a[j+dk] = x; //插入到正確位置 } print(a, n,i ); } } // 先按增量d（n/2,n為要排序數的個數進行希爾排序 void shellSort(int a[], int n){ int dk = n/2; while( dk >= 1 ){ ShellInsertSort(a, n, dk); dk = dk/2; } } int main(){ int a[8] = {3,1,5,7,2,4,9,6}; //ShellInsertSort(a,8,1); //直接插入排序 shellSort(a,8); //希爾插入排序 print(a,8,8); }
————————
三、簡單選擇排序（Selection Sort）
演算法思想：
簡單選擇排序的實作思想：比較+交換
? 從待排序序列中，找到關鍵字最小的元素；
? 如果最小元素不是待排序序列的第一個元素，將其和第一個元素互換；
? 從余下的 N - 1 個元素中，找出關鍵字最小的元素，重復(1)、(2)步，直到排序結束，因此我們可以發現，簡單選擇排序也是通過兩層回圈實作，
第一層回圈：依次遍歷序列當中的每一個元素
第二層回圈：將遍歷得到的當前元素依次與余下的元素進行比較，符合最小元素的條件，則交換，
演算法代碼：
void print(int a[], int n ,int i){ cout<<"第"<<i+1 <<"趟 : "; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl; } /** * 陣列的最小值 * * @return int 陣列的鍵值 */ int SelectMinKey(int a[], int n, int i) { int k = i; for(int j=i+1 ;j< n; ++j) { if(a[k] > a[j]) k = j; } return k; } /** * 選擇排序 * */ void selectSort(int a[], int n){ int key, tmp; for(int i = 0; i< n; ++i) { key = SelectMinKey(a, n,i); //選擇最小的元素 if(key != i){ tmp = a[i]; a[i] = a[key]; a[key] = tmp; //最小元素與第i位置元素互換 } print(a, n , i); } } int main(){ int a[8] = {3,1,5,7,2,4,9,6}; cout<<"初始值："; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl<<endl; selectSort(a, 8); print(a,8,8); }
————————
四、堆排序（Heap Sort）
演算法思想：
堆：本質是一種陣列物件，特別重要的一點性質：任意的葉子節點小于（或大于）它所有的父節點，對此，又分為大頂堆和小頂堆：
? 大頂堆要求節點的元素都要大于其孩子，
? 小頂堆要求節點元素都小于其左右孩子，
? 兩者對左右孩子的大小關系不做任何要求，
利用堆排序，就是基于大頂堆或者小頂堆的一種排序方法，下面，我們通過大頂堆來實作，
基本思想：堆排序可以按照以下步驟來完成：
1.首先將序列構建稱為大頂堆；（這樣滿足了大頂堆那條性質：位于根節點的元素一定是當前序列的最大值）
2. 取出當前大頂堆的根節點，將其與序列末尾元素進行交換；（此時：序列末尾的元素為已排序的最大值；由于交換了元素，當前位于根節點的堆并不一定滿足大頂堆的性質）
3. 對交換后的n-1個序列元素進行調整，使其滿足大頂堆的性質；
4. 重復2.3步驟，直至堆中只有1個元素為止
下面是基于大頂堆的堆排序演算法代碼：
void print(int a[], int n){ for(int j= 0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl; } /** * 已知H[s…m]除了H[s] 外均滿足堆的定義 * 調整H[s],使其成為大頂堆.即將對第s個結點為根的子樹篩選, * * @param H是待調整的堆陣列 * @param s是待調整的陣列元素的位置 * @param length是陣列的長度 */ void HeapAdjust(int H[],int s, int length) { int tmp = H[s]; int child = 2*s+1; //左孩子結點的位置，(i+1 為當前調整結點的右孩子結點的位置) while (child < length) { if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比當前待調整結點大的孩子結點) ++child ; } if(H[s]<H[child]) { // 如果較大的子結點大于父結點 H[s] = H[child]; // 那么把較大的子結點往上移動，替換它的父結點 s = child; // 重新設定s ,即待調整的下一個結點的位置 child = 2*s+1; } else { // 如果當前待調整結點大于它的左右孩子，則不需要調整，直接退出 break; } H[s] = tmp; // 當前待調整的結點放到比其大的孩子結點位置上 } print(H,length); } /** * 初始堆進行調整 * 將H[0..length-1]建成堆 * 調整完之后第一個元素是序列的最小的元素 */ void BuildingHeap(int H[], int length) { //最后一個有孩子的節點的位置 i= (length -1) / 2 for (int i = (length -1) / 2 ; i >= 0; --i) HeapAdjust(H,i,length); } /** * 堆排序演算法 */ void HeapSort(int H[],int length) { //初始堆 BuildingHeap(H, length); //從最后一個元素開始對序列進行調整 for (int i = length - 1; i > 0; --i) { //交換堆頂元素H[0]和堆中最后一個元素 int temp = H[i]; H[i] = H[0]; H[0] = temp; //每次交換堆頂元素和堆中最后一個元素之后，都要對堆進行調整 HeapAdjust(H,0,i); } } int main(){ int H[10] = {3,1,5,7,2,4,9,6,10,8}; cout<<"初始值："; print(H,10); HeapSort(H,10); //selectSort(a, 8); cout<<"結果："; print(H,10); }
————————
五、冒泡排序（Bubble Sort）
演算法思想：
冒泡遍歷所有的資料，每次對相鄰元素進行兩兩比較，如果順序和預先規定的順序不一致，則進行位置交換；
這樣一次遍歷會將最大或最小的資料上浮到頂端，之后再重復同樣的操作，直到所有的資料有序，
這個演算法的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端，
演算法代碼：
void bubbleSort(int a[], int n){ for(int i =0 ; i< n-1; ++i) { for(int j = 0; j < n-i-1; ++j) { if(a[j] > a[j+1]) { int tmp = a[j] ; a[j] = a[j+1] ; a[j+1] = tmp; } } } }View Code
————————
六、快速排序（Quick Sort）
演算法思想：
快速排序是由東尼·霍爾所發展的一種排序演算法，在平均狀況下，排序n個專案要Ο(nlogn)次比較，在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見，事實上，快速排序通常明顯比其他Ο(nlogn) 演算法更快，因為它的內部回圈（inner loop）可以在大部分的架構上很有效率地被實作出來
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists），
演算法步驟：
? 從數列中挑出一個元素，稱為 “基準”（pivot），
? 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊），在這個磁區退出之后，該基準就處于數列的中間位置，這個稱為磁區（partition）操作，
? 遞回地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序，
遞回的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了，雖然一直遞回下去，但是這個演算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去，
演算法代碼：
void print(int a[], int n){ for(int j= 0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl; } void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } int partition(int a[], int low, int high) { int privotKey = a[low]; //基準元素 while(low < high){ //從表的兩端交替地向中間掃描 while(low < high && a[high] >= privotKey) --high; //從high 所指位置向前搜索，至多到low+1 位置，將比基準元素小的交換到低端 swap(&a[low], &a[high]); while(low < high && a[low] <= privotKey ) ++low; swap(&a[low], &a[high]); } print(a,10); return low; } void quickSort(int a[], int low, int high){ if(low < high){ int privotLoc = partition(a, low, high); //將表一分為二 quickSort(a, low, privotLoc -1); //遞回對低子表遞回排序 quickSort(a, privotLoc + 1, high); //遞回對高子表遞回排序 } } int main(){ int a[10] = {3,1,5,7,2,4,9,6,10,8}; cout<<"初始值："; print(a,10); quickSort(a,0,9); cout<<"結果："; print(a,10); }View Code
————————
七、歸并排序（Merge Sort）
演算法思想：
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序演算法，該演算法是采用分治法（Divide and Conquer）的一個非常典型的應用，
演算法步驟：
? 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列；
? 設定兩個指標，最初位置分別為兩個已經排序序列的起始位置；
? 比較兩個指標所指向的元素，選擇相對小的元素放入到合并空間，并移動指標到下一位置；
? 重復步驟3直到某一指標達到序列尾；
? 將另一序列剩下的所有元素直接復制到合并序列尾，
演算法代碼：
void print(int a[], int n){ for(int j= 0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl; } //將r[i…m]和r[m +1 …n]歸并到輔助陣列rf[i…n] void Merge(ElemType *r,ElemType *rf, int i, int m, int n) { int j,k; for(j=m+1,k=i; i<=m && j <=n ; ++k){ if(r[j] < r[i]) rf[k] = r[j++]; else rf[k] = r[i++]; } while(i <= m) rf[k++] = r[i++]; while(j <= n) rf[k++] = r[j++]; print(rf,n+1); } void MergeSort(ElemType *r, ElemType *rf, int lenght) { int len = 1; ElemType *q = r ; ElemType *tmp ; while(len < lenght) { int s = len; len = 2 * s ; int i = 0; while(i+ len <lenght){ Merge(q, rf, i, i+ s-1, i+ len-1 ); //對等長的兩個子表合并 i = i+ len; } if(i + s < lenght){ Merge(q, rf, i, i+ s -1, lenght -1); //對不等長的兩個子表合并 } tmp = q; q = rf; rf = tmp; //交換q,rf，以保證下一趟歸并時，仍從q 歸并到rf } } int main(){ int a[10] = {3,1,5,7,2,4,9,6,10,8}; int b[10]; MergeSort(a, b, 10); print(b,10); cout<<"結果："; print(a,10); }View Code
————————
八、基數排序(Radix Sort)
演算法思想：
基數排序：通過序列中各個元素的值，對排序的N個元素進行若干趟的“分配”與“收集”來實作排序，
分配：我們將L[i]中的元素取出，首先確定其個位上的數字，根據該數字分配到與之序號相同的桶中 ，
收集：當序列中所有的元素都分配到對應的桶中，再按照順序依次將桶中的元素收集形成新的一個待排序列L[ ] ，
對新形成的序列L[]重復執行分配和收集元素中的十位、百位...直到分配完該序列中的最高位，則排序結束，
演算法代碼：
Void RadixSort(Node L[],length,maxradix) { int m,n,k,lsp; k=1;m=1; int temp[10][length-1]; Empty(temp); //清空臨時空間 while(k<maxradix) //遍歷所有關鍵字 { for(int i=0;i<length;i++) //分配程序 { if(L[i]<m) Temp[0][n]=L[i]; else Lsp=(L[i]/m)%10; //確定關鍵字 Temp[lsp][n]=L[i]; n++; } CollectElement(L,Temp); //收集 n=0; m=m*10; k++; } }View Code
————————
看到這里，你對“C語言八大排序演算法”了解了多少？
如果你想更深入的學習C語言，小編推薦一個C語言編程學習俱樂部【點擊進入】！
涉及到：C語言、C++、windows編程、網路編程、QT界面開發、Linux編程、游戲編程、黑客等等......
編程入門資料：
?推薦學習書籍：
一個活躍、高逼格、高層次的編程學習殿堂；編程入門只是順帶，思維的提高才有價值！
四、總結
各種排序的穩定性，時間復雜度和空間復雜度總結：
我們比較時間復雜度函式的情況：
時間復雜度函式O(n)的增長情況
所以對n較大的排序記錄，一般的選擇都是時間復雜度為O(nlog2n)的排序方法，
時間復雜度來說：
(1)平方階(O(n2))排序
各類簡單排序：直接插入、直接選擇和冒泡排序；
(2)線性對數階(O(nlog2n))排序
快速排序、堆排序和歸并排序；
(3)O(n1+§))排序,§是介于0和1之間的常數，
希爾排序
(4)線性階(O(n))排序
基數排序，此外還有桶、箱排序，
總結
以上所述是小編給大家介紹的必須知道的C語言 八大排序演算法(值得收藏)，希望對大家有所幫助！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/187609.html
標籤：C
上一篇：QT父類信號呼叫子類槽函式