數據結構之——八大排序演算法
- 2019 年 10 月 24 日
- 筆記
排序演算法小匯總
1、交換排序類
1.1、冒泡排序
1.2、快速排序
2、選擇排序類
2.1、簡單選擇排序
2.2、堆排序
3、插入排序類
3.1、直接插入排序
3.2、希爾排序
4、歸併排序
5、基數排序
交換排序類
冒泡排序（優化）
冒泡排序一般將前面作為有序區（初始無元素），後面作為無序區（初始元素都在無序區里），在遍歷過程中把當前無序區最小的數像泡泡一樣，讓其往上飄，然後在無序區繼續執行此操作，直到無序區不再有元素。
這塊是對老式冒泡排序的一種優化，因為當某次冒泡結束後，可能數組已經變得有序，繼續進行冒泡排序會增加很多無用的比較次數，提高時間複雜度。
所以我們增加了一個標識變數flag，將其初始化為1，外層循環還是和老式的一樣從0到末尾，記憶體循環我們改為從最後面向前面i（外層循環所處的位置）處遍歷找最小的，如果在記憶體沒有出現交換，說明無序區的元素已經變得有序，所以不需要交換，即整個數組已經變得有序。
#include<iostream> using namespace std; void sort(int k[] ,int n) { int flag = 1; int temp; for(int i = 0; i < n-1 && flag; i++) { printf("hellon"); for(int j = n-1; j > i; j--) { flag = 0; /*下面這裡和i沒關係，注意看這塊，從下往上travel，兩兩比較，如果不合適就調換， 如果上來後一次都沒調換，說明下面已經按順序拍好了，上面也是按順序排好的，所以完美！ */ if(k[j-1] > k[j]) { temp = k[j-1]; k[j-1] = k[j]; k[j] = temp; flag = 1; } } } } int main() { int k[3] = {0,9,6}; sort(k,3); for(int i =0; i < 3; i++) printf("%d ",k[i]); }快速排序
快速排序（Quicksort），基於分治演算法思想，是對冒泡排序的一種改進。快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
通俗來說，就是不斷的挖坑和填坑
- 1、其實就是先選擇一個基準數,然後這個基準數我們保存為x，那它所在的位置就是一個空出來的坑。
- 2、我們從右向左迭代，如果遇到比基準數小的數，就將其填到上次挖的坑中，然後它自己在的這個地方就變成了一個新的坑。
- 3、然後再從左向右迭代，找比基準數大的數，將其填到上次挖的坑中，然後它所在的地方就變成了新的坑。
- 4、最後要將基準數填入最後的坑中，然後將基準數所在的位置返回，方便下次調用時候使用
//挖坑填數 int adjustArray(int s[],int l, int r) //傳入數組和左右的下標 { int i = l,j = r; //分別表示左半邊的下標和右半邊的下標 int x = s[l]; //默認最左邊的數就是挖的第一個坑 while(i < j) //要保證數組中元素最少有兩個 { //從右向左迭代，找比基準數小的 while(s[j] >= x && i < j) j--; if(i < j) //找到了比基準數小的 { s[i] = s[j]; //將其填到原來挖的坑的地方上，現在j處又形成了一個新的坑 i++; //i處填入了新的數，所以i++，然後從左往右去找，在左半邊比基準數大的數 } //從左向右迭代去找比基準數大的 while(s[i] < x && i < j) i++; if(i < j) { s[j] = s[i]; j--; } } //退出時，要把坑用基準數填回去 s[i] = x; return i; //返回調整後基準數的位置，方便下一次遞歸調用的時候 } 就這樣將原來的數組以返回的基準數所在的位置為中心，分成了兩個數組（理論上兩個，但在記憶體中還是在一起挨著的），然後分別對新的兩個數組遞歸進行挖坑和填坑的操作，當先前指示數組左右兩邊的下標的變數左邊的大於或等於（一般都是等於）右邊的時候（即數組已經被分的不能被分了），這時候原數組就變成有序的了，因為按照上面的思路，所有左邊的都小於右邊的，那既然數組都被分的變成一個數一個小數組那就是左邊的數比右邊的數小，即有序，排序完成！
void quick_sort(int s[], int l, int r) { if(l < r) { int i = adjustArray(s,l,r); //不能將上次的基準數拉入新的兩個數組中的任何一個，因為其所在的位置已經是最終對的位置了，它左邊的數都比它小，右邊的都比它大 quick_sort(s,l,i-1); quick_sort(s,i+1,r); } }選擇排序類
簡單選擇排序
選擇排序就是每次在無序區循環找出一個極值，將其放入指定位置（即進入有序區）來使數組有序，一般來說是讓數組的左邊作為有序區，右邊是無序區。
- 先從第一個元素到最後一個元素遍歷，找出最小的元素，將其和第一個元素互換位置。
- 再從第二個元素到最後一個元素遍歷，找出最小的，和第二個互換位置。
- 如此循環，右邊無序區只剩一個元素，則排序完成！
#include<iostream> using namespace std; void sort(int k[],int n) { int min,temp; //min用來保存最小的元素的下標 for(int i = 0;i < n-1; i++) { min = i; for(int j = i+1; j < n; j++) //找出無序區中的最小的元素 { if(k[j] < k[min]) min = j; } if(min != i) //如果最小的元素，不是初始的，即有比它更小的就交換位置 { temp = k[min]; k[min] = k[i]; k[i] = temp; } } } int main() { int k[10] = {2,5,4,6,3,8,9,7,1,0}; sort(k,10); for(int i = 0;i < 10;i++) cout<<k[i]<<" "; }堆排序
堆排序採用大頂堆或著小頂堆，我們這裡採用大頂堆來排序。
用一棵完全二叉樹來模擬一個大頂堆，大頂堆的規則如下：每個結點的值都大於它的孩子結點的值，如下圖：
這樣，如果我們每次將大頂堆的根節點依次和數組的最後一個，倒數第二個，倒數第三個……做交換，每次交換完後，需要從根節點到與之交換的那個結點之前的結點之間進行調整大頂堆，保證大頂堆的符合上述規則。
在完全二叉樹中，如果用順序結構來存儲這棵樹，那麼某個結點和它左右孩子結點之間存在以下關係（層序遍歷）：左孩子下標等於雙親結點下標的2倍，右孩子下標等於雙親結點2倍+1。
交換函數
void swap(int k[], int i, int j) { int temp = k[i]; k[i] = k[j]; k[j] = temp; }調整大頂堆的函數
void HeapAdjust(int k[], int s, int n) //從s到n開始調整大頂堆,s表示待調整的結點 { int temp = k[s]; //保存當前需要調整的結點 for(int i = 2*s; i <= n; i*=2) //2*s表示s這個結點的左孩子，i*=2表示當前結點的左孩子結點，也就是下一個檢查的結點，因為移動當前檢查的結點後，可能會對其孩子結點的規則完整性破壞，所以需要往下檢查 { if(i < n && k[i] < k[i+1]) //k[i]表示左孩子，k[i+1]表示右孩子,i<n是為了保證不是最後一個結點 { i++; //永遠讓i指向較大的孩子結點 } if(temp >= k[i]) //如果待調整的雙親大於兩孩子中較大的孩子,則不需要調整 { break; } //下面將較大的更新為雙親結點 k[s] = k[i]; s=i; } k[s] = temp; } /** 對上面for循環做一個解釋，當檢查到較上的結點時候，移動後不能保證樹的規則， 應該繼續檢查其孩子結點，因為做了交換後可能會破壞孩子結點的大頂堆規則 */對堆排序的實現
為了方便起見，數組不用第0號元素，從第一號元素開始。
假設一共n個結點，第n/2個結點剛好是最後一個擁有孩子結點的結點，這個也是完全二叉樹的規律，而初始我們就應該從下往上去檢查，因為上面的結點是根據下面的結點檢查的。
#include <iostream> using namespace std; void HeapSort(int k[], int n) { for(int i = n/2; i > 0; i--)//第n/2個結點剛好是最後一個擁有孩子結點的結點，這個也是完全二叉樹的規律 { HeapAdjust(k,i,n); } for(int i = 1; i < 10; i++) //此處是為了調試，查看交換前第一次構造的大頂堆 cout<<k[i]<<" "; for(int i = n; i > 1; i--) { swap(k,1,i); HeapAdjust(k,1,i-1); } } int main() { int k[10] = {-1,3,2,7,5,8,9,0,1,6}; HeapSort(k,9); system("pause"); //此處是為了做一下調試，查看交換前構造的第一個大頂堆 for(int i = 1; i < 10; i++) cout<<k[i]<<" "; }插入排序類
直接插入排序
（從小到大排列）直接插入排序就是：遍歷這個數組，然後如果發現後一個比前一個小，則將後一個較小的拿出來，記為x，然後與前面的依次作比較，如果比x大，則將其向後退一個位置，直到碰到一個比x小的元素，則將x放到它的後面即可，這樣等到遍歷完這個數組後，它就會變成有序的。
下面是一次外層循環的演示，對整個數組遍歷一遍，作如下操作則可
#include<iostream> using namespace std; void Insert_Sort(int k[],int n) { int temp,j,i; for(i = 1; i < n; i++) { if(k[i] < k[i-1]) { temp = k[i]; for( j = i-1; k[j] > temp && j >= 0; j--) k[j+1] = k[j]; k[j+1] = temp; } } } int main() { int k[10] = {3,5,1,7,2,0,8,9,4,6}; Insert_Sort(k,10); for(int i = 0; i < 10; i++) cout<<k[i]<<endl; return 0; }希爾排序
希爾排序是對插入排序的一種改進，先取一個小於n的整數d1作為第一個增量，把文件的全部記錄分組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然後，取第二個增量d2 < d1重複上述的分組和排序，直至所取的增量 =1( < …< d2< d1)，即所有記錄放在同一組中進行直接插入排序為止。
#include<iostream> using namespace std; void Insert_Sort(int k[],int n) { int temp,j,i; int gap = n; do { gap = gap/3 + 1; for(i = gap; i < n; i++) { if(k[i] < k[i-gap]) { temp = k[i]; for( j = i-gap; k[j] > temp && j >= 0; j-=gap) { k[j+gap] = k[j]; } k[j+gap] = temp; } } }while(gap > 1); } int main() { int k[10] = {3,5,1,7,2,0,8,9,4,6}; Insert_Sort(k,10); for(int i = 0; i < 10; i++) cout<<k[i]<<" "; return 0; }歸併排序
歸併排序，基於分治演算法思想，就比如是比武大賽一樣，先對數據進行分組，兩兩進行比較，並排序，然後將有序的兩個小數組進行歸併，得到一個新數組，再和其他新得到的數組進行兩兩歸併，如此重複，直到歸併為一個大數組，此時，此數組有序！
#include <iostream> using namespace std; void Merge(int array[], int start, int mid, int end) { //start到mid表示第一個數組，mid+1到end表示第二個數組 int newarray[end - start + 1]; //對兩個數組進行歸併 int p = start, q = mid + 1, r = 0; //分別指示第一個數組，第二個數組，和第三個新數組 while(p <= mid && q <= end) { if(array[p] <= array[q]) { newarray[r++] = array[p++]; } else { newarray[r++] = array[q++]; } } //左側小集合還有剩餘，依次歸併到大集合尾部 while(p <= mid) { newarray[r++] = array[p++]; } //右側小集合還有剩餘，依次歸併到大集合尾部 while(q <= end) { newarray[r++] = array[q++]; } //將大集合元素依次複製回原數組 for(int i = 0; i < end - start + 1; i++) //to do array[i+start] = newarray[i]; } void Merge_Sort(int array[], int start, int end) { int mid = (start + end) / 2; if(start < end) { Merge_Sort(array,start,mid); Merge_Sort(array,mid+1,end); //合併 Merge(array,start,mid,end); } } int main() { int k[10] = {3,9,6,1,8,4,0,7,2,5}; Merge_Sort(k,0,9); for (int i = 0; i < 10; ++i) { cout<<k[i]<<" "; } }基數排序
個人理解(最好先了解一下桶排序)：
從待排序數組每個數字的基數開始排序，然後一直到最大數的最高位。準備10個桶，從低位開始分別將其放入對應編號為0-9的桶中。等到低位排完得到一個子序列，再將這個序列按照次低位的大小進入相應的桶中，一直排到最高位為止，數組排序完成。
演算法步驟
- 先找出所有數中的最高位數，即循環次數，要存入桶和出桶這麼多次
- 每次循環用一個count[10]數組記錄每個桶中的數字個數（循環開始之前，要記得將上次循環時count中保存的值初始化為0）
- 遍曆數組中每一個數，將其放入指定的桶中
- 按0-9的順序又將桶中元素存回數組，覆蓋之前的值
先對個位排序
再對十位排序
繼續百位
一直到最高位
此時將桶中數字依次輸出，即有序！
#include <iostream> #include <cmath> using namespace std; //求數據的最大位數，可以作為對內私有的函數，先找數組中的最大數，然後求最大數的位數 int maxbit(int data[], int n) { int max = 0, bit = 0; for (int i = 0; i < n; i++) if (data[i] > max) max = data[i]; while (max != 0) { max /= 10; bit++; } return bit; } void sort(int data[], int n) { int bit = maxbit(data, n); int count[10]; //統計每個桶中數的個數 int* bucket = new int[10 * n]; //二維數組，10個桶，每個桶容量最大是n，即所有元素存到一個桶中 for (int i = 1; i <= bit; i++) //循環最高位數次 { int x = 0; for (int p = 0; p < 10; ++p) //每次將統計桶中個數的數組清零 count[p] = 0; for (int j = 0; j < n; j++) //遍曆數組中每一個數，將其放入指定的桶中 { int b = data[j]; //取一個數的倒數第n位的數字，就是讓它除以10的n-1次方，再取10的餘數 b /= pow(10, i - 1); b %= 10; count[b]++; bucket[b * n + count[b]] = data[j]; //放入桶中 } //將桶中的數據按順序存回數組中 for (int r = 0; r < 10; r++) { for (int t = 1; t <= count[r]; t++) { data[x] = bucket[r * n + t]; x++; } } } } int main() { int data[10] = { 34, 90, 12, 21, 128, 231412, 678, 123, 3, 10 }; sort(data, 10); for (int i = 0; i < 10; ++i) { cout << data[i] << " "; } system("pause"); }
