針對排序演算法，網上有比較好的講解，參考自：程式員內功：八大排序演算法和 程式員的內功——資料結構和演算法系列 這里主要是學習程序中的重新記錄，記錄典型的排序演算法實作模板；
排序演算法穩定性講解：
https://www.cnblogs.com/codingmylife/archive/2012/10/21/2732980.html
https://blog.csdn.net/qq_43152052/article/details/100078825
排序的穩定性：首先，排序演算法的穩定性大家應該都知道，通俗地講就是能保證排序前2個相等的數其在序列的前后位置順序和排序后它們兩個的前后位置順序相同，在簡單形式化一下，如果Ai = Aj，Ai原來在位置前，排序后Ai還是要在Aj位置前，演算法有的可以穩定，也可以不穩定(冒泡排序)，穩定否要看演算法是否符合穩定的定義；
冒泡排序：簡單交換，從左端開始從大到小開始冒泡；每次冒泡后，最大值歸位；減治思想，縮小問題規模；
#include <iostream> #include <cstdio> #include <vector> using namespace std; vector<int> inarray; int main(){ freopen("in.txt", "r", stdin); // 重定向到輸入 int i = 0; int tmp; // 方法1 while (cin >> tmp) { inarray.push_back(tmp); // cout << inarray[i] << endl; i++; } int num = i; cout << "輸入資料：" << endl; for(i = 0; i < num; i++){ cout << inarray[i] << " "; } cout << endl << endl; cout << "排序程序：" << endl; for(i=1; i < num; i++){ for (int j = 0; j < num-i;j++){ if(inarray[j] >= inarray[j+1]){ int tmp = inarray[j]; inarray[j] = inarray[j+1]; inarray[j+1] = tmp; } } for(int k = 0; k < num; k++){ cout << inarray[k] << " "; } cout << endl; } for(i = 0; i < num; i++){ cout << inarray[i] << " "; } cout << endl; return 0; }冒泡排序實作模板
輸入資料： 9 8 7 6 5 4 3 2 1 0 排序程序： 8 7 6 5 4 3 2 1 0 9 7 6 5 4 3 2 1 0 8 9 6 5 4 3 2 1 0 7 8 9 5 4 3 2 1 0 6 7 8 9 4 3 2 1 0 5 6 7 8 9 3 2 1 0 4 5 6 7 8 9 2 1 0 3 4 5 6 7 8 9 1 0 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9冒泡排序輸出樣例
快速排序：通過一趟排序將排序的資料分割成獨立的兩部分，分割點左邊都是比它小的資料，右邊都是比它大的數; 使用分治方法，縮小問題規模，遞回求解；
實作方法：
#define DEBUG 1 #include <iostream> #include <cstdio> #include <vector> using namespace std; void printarray(vector<int> &arr, int left, int right); // 分解 第一版本； int divide_1(vector<int> &arr, int left, int right){ int base = arr[left]; // 選取第一個元素為left; if(DEBUG){ cout << endl << "base:" << base << " " << "left:" << left << " " << "right:" << right << endl; } while (true) { while (arr[right] >= base && right > left) { right --; } if (right == left){ printarray(arr, left, right); break; } arr[left] = arr[right]; arr[right] = base; left ++; printarray(arr, left, right); while (arr[left] <= base && left < right) { left ++; } if (left == right){ printarray(arr, left, right); break; } arr[right] = arr[left]; arr[left] = base; right --; printarray(arr, left, right); } return left; // 回傳當前 base 所在的索引 } // 分解第二版本 int divide_2(vector<int> &arr, int left, int right){ int base = arr[left]; while (left < right) { while (left < right && base <= arr[right]) { right --; } arr[left] = arr[right]; while (left < right && arr[left] <= base) { left ++; } arr[right] = arr[left]; } arr[left] = base; return left; // 回傳當前base的索引； } // 快速排序演算法 void quicksort(vector<int> &arr, int left, int right){ // 設定遞回出口 if (left >= right){ return; } int baseindex = divide_1(arr, left, right); quicksort(arr, left, baseindex-1); quicksort(arr, baseindex+1, right); // 快速排序演算法，強調對問題原有資料的分解； // 每分解一次，一個元素歸位；為減治； // 每分解一次，轉化為兩個獨立的子問題；為分治； } // 列印函式； void printarray(vector<int> &arr, int left, int right){ if((left == -1 && right== -1)|| DEBUG){ for(int i = 0; i < arr.size(); i++){ cout << arr[i] << " "; } cout << endl; } if((left != -1&&right != -1)&& DEBUG){ cout << "left:" << left << " " << "right:" << right << endl; } } int main(){ vector<int> arr; freopen("in.txt", "r", stdin); // 重定向到輸入 int i = 0; int tmp; while (cin >> tmp) { arr.push_back(tmp); // cout << inarray[i] << endl; i++; } int num = i; cout << "輸入資料：" << endl; printarray(arr, -1, -1); cout << endl; if (DEBUG){ cout << "排序程序：" << endl; } // 快速排序演算法呼叫；其他代碼為除錯輸出代碼； quicksort(arr, 0, num-1); if (DEBUG){ cout << endl; } cout << "排序結果：" << endl; printarray(arr, -1, -1); return 0; }快速排序代碼模板
bash-3.2$ c++ 快速排序.cc; ./a.out 輸入資料： 7 8 9 6 5 4 3 2 1 排序程序： base:7 left:0 right:8 1 8 9 6 5 4 3 2 7 left:1 right:8 1 7 9 6 5 4 3 2 8 left:1 right:7 1 2 9 6 5 4 3 7 8 left:2 right:7 1 2 7 6 5 4 3 9 8 left:2 right:6 1 2 3 6 5 4 7 9 8 left:3 right:6 1 2 3 6 5 4 7 9 8 left:6 right:6 base:1 left:0 right:5 1 2 3 6 5 4 7 9 8 left:0 right:0 base:2 left:1 right:5 1 2 3 6 5 4 7 9 8 left:1 right:1 base:3 left:2 right:5 1 2 3 6 5 4 7 9 8 left:2 right:2 base:6 left:3 right:5 1 2 3 4 5 6 7 9 8 left:4 right:5 1 2 3 4 5 6 7 9 8 left:5 right:5 base:4 left:3 right:4 1 2 3 4 5 6 7 9 8 left:3 right:3 base:9 left:7 right:8 1 2 3 4 5 6 7 8 9 left:8 right:8 1 2 3 4 5 6 7 8 9 left:8 right:8 排序結果： 1 2 3 4 5 6 7 8 9快速排序輸出樣例
排序型別：交換排序；
排序方法：快速排序；
時間復雜度：
資料基本有序的時候，以第一個元素為基準，二分后；第一個子序列為空；此時效率較差；
當隨機分布的時候，兩個子序列的元素個數相接近的時候，此時效率最好；
最好時間復雜度：nlogn;
最壞時間復雜度：n2;
空間復雜度：因為每次排序，都需要1個空間，存盤base;所以空間復雜度為 logn;最壞的時候為n;
演算法穩定性：因為排序程序中，相等的元素可能會因為磁區而交換順序；所以不是穩定的演算法；
快速排序為什么比冒泡排序快：因為快速排序利用分治的演算法，把當前資料分為大于base的陣列和小于base的陣列；這樣可以減少兩個陣列間的元素比較，而分治成兩個獨立的子問題；所以能夠減少比較次數，從而加快了排序的速度；
直接插入排序：直接插入排序每一趟，將一個等待排序的記錄，按照關鍵字的大小插入到前面有序佇列中；直到掃描所有的數字后，每次都有一個數字歸位排序完成；減治，縮小問題規模；
#define DEBUG 1 #include <iostream> #include <cstdio> #include <vector> using namespace std; void printarray(vector<int> &arr); //直接插入排序 void insertsort(vector<int> &arr){ int toins; for(int i =1; i < arr.size(); i++){ toins = arr[i]; cout << "toins: " << toins << endl; int j; // 進行回圈挪動左側有序陣列，找到待插入位置 for (j = i-1; j >=0; j--) { if(arr[j]>= toins){ arr[j+1] = arr[j]; }else{ break; } } arr[j+1] = toins; // 進行插入陣列 printarray(arr); } } // 列印函式； void printarray(vector<int> &arr){ for(int i = 0; i < arr.size(); i++){ cout << arr[i] << " "; } cout << endl; if(DEBUG){ //cout << "left:" << left << " " << "right:" << right << endl; } } int main(){ vector<int> arr; freopen("in.txt", "r", stdin); // 重定向到輸入 int i = 0; int tmp; while (cin >> tmp) { arr.push_back(tmp); // cout << inarray[i] << endl; i++; } int num = i; cout << "輸入資料：" << endl; printarray(arr); cout << endl; if (DEBUG){ cout << "排序程序：" << endl; } // 插入排序演算法呼叫；其他代碼為除錯輸出代碼； insertsort(arr); if (DEBUG){ cout << endl; } cout << "排序結果：" << endl; printarray(arr); return 0; }直接插入排序代碼模板
bash-3.2$ c++ 直接插入排序.cc ; ./a.out 輸入資料： 7 6 5 3 4 2 1 排序程序： toins: 6 6 7 5 3 4 2 1 toins: 5 5 6 7 3 4 2 1 toins: 3 3 5 6 7 4 2 1 toins: 4 3 4 5 6 7 2 1 toins: 2 2 3 4 5 6 7 1 toins: 1 1 2 3 4 5 6 7 排序結果： 1 2 3 4 5 6 7直接插入排序輸出樣例
排序型別：插入排序；
關鍵操作：元素比較次數；
時間復雜度：
最好時間復雜度：當資料在正序的時候，執行效率最好；時間復雜度為n;
最壞時間復雜度：當資料為逆序的時候，執行效率最差；時間復雜度為n2;
空間復雜度：不過使用交換還是插入，都需要使用一個空間存盤要插入的值，復雜度為1；
演算法穩定性：主要還是看實作方式，基本上是穩定的演算法；當然也能實作為不穩定的；
優化方法：尋找插入位置的時候，可以使用二分查找來進行優化；
希爾排序：希爾排序是把記錄按照一定增量（gap）分組，對每個組進行直接插入排序演算法進行排序；當增量逐漸減小，每個組的關鍵詞越來越多，當增量減少為1的時候，整個資料只要進行少量微調便可有序；希爾排序是直接插入排序的優化；總體目標是減少比較和交換次數；實作程序中，可以使用陣列交換，也可以使用移動插入的方式來進行排序；
#define DEBUG 1 #include <iostream> #include <cstdio> #include <vector> using namespace std; void printarray(vector<int> &arr); //希爾插入排序_移動插入方式實作； void shellsort(vector<int> &arr){ int size = arr.size(); for (int gap = size/2; gap >0; gap /=2) { cout << "gap: " << gap << endl; for (int i = 0; i < gap; i++) // 希爾排序的每次gap; { for (int j = i+gap; j < size; j += gap) // 類比于插入排序；使用j 抽象出一組序列； { int toins = arr[j]; int k; cout << toins << endl; for (k = j-gap; k >= i; k -= gap) { if (arr[k] >= toins) { arr[k+gap] = arr[k]; }else { break; } } arr[k+gap] = toins; // 使用移動插入的方式進行實作； printarray(arr); } } } } //希爾排序，使用交換方式實作； 類似于冒泡排序 void shellsort_2(vector<int> &arr){ int size = arr.size(); for (int gap = size/2; gap >0; gap /=2) { cout << "gap: " << gap << endl; for (int i = 0; i < gap; i++) // 希爾排序的每次gap; { for (int j = i+gap; j < size; j += gap) // 類比于插入排序；使用j 抽象出一組序列； { int k; cout << "toins: " << arr[j] << endl; for (k = j-gap; k >= i; k -= gap) { if (arr[k] >= arr[k+gap]) { int tmp = arr[k+gap]; arr[k+gap] = arr[k]; arr[k] = tmp; } else { break; } } printarray(arr); } } } } // 列印函式； void printarray(vector<int> &arr){ for(int i = 0; i < arr.size(); i++){ cout << arr[i] << " "; } cout << endl; if(DEBUG){ //cout << "left:" << left << " " << "right:" << right << endl; } } int main(){ vector<int> arr; freopen("in.txt", "r", stdin); // 重定向到輸入 int i = 0; int tmp; while (cin >> tmp) { arr.push_back(tmp); i++; } int num = i; cout << "輸入資料：" << endl; printarray(arr); cout << endl; if (DEBUG){ cout << "排序程序：" << endl; } // 希爾排序演算法呼叫；其他代碼為除錯輸出代碼； shellsort(arr); if (DEBUG){ cout << endl; } cout << "排序結果：" << endl; printarray(arr); return 0; }希爾排序模板
bash-3.2$ c++ 希爾排序.cc; ./a.out 輸入資料： 7 6 5 3 4 2 1 排序程序： gap: 3 3 3 6 5 7 4 2 1 1 1 6 5 3 4 2 7 4 1 4 5 3 6 2 7 2 1 4 2 3 6 5 7 gap: 1 4 1 4 2 3 6 5 7 2 1 2 4 3 6 5 7 3 1 2 3 4 6 5 7 6 1 2 3 4 6 5 7 5 1 2 3 4 5 6 7 7 1 2 3 4 5 6 7 排序結果： 1 2 3 4 5 6 7希爾排序輸出樣例
排序種類：插入排序； 時間復雜度： 最壞時間復雜度：n2 平均時間復雜度：nlogn 空間復雜度為：1，每次插入排序的時候，需要一個輔助的空間； 穩定性：因為 gap 資料交換的時候，會交換相同元素的順序，所以該演算法不是穩定排序演算法； 與直接插入排序對比： 直接插入排序也適用于鏈式存盤結構，希爾排序對鏈式存盤結構不友好； 希爾排序的比較次數和移動次數都要比直接插入排序少，當N越大時，效果越明顯；
簡單選擇排序：每次從待排序佇列中，找到最小的關鍵字記錄，順序放在已經排序記錄的末尾，從左到右掃描；直到第一層回圈掃描結束；思想比較簡單；
#define DEBUG 1 #include <iostream> #include <cstdio> #include <vector> using namespace std; void printarray(vector<int> &arr); //直接插入排序 void selectsort(vector<int> &arr){ int size = arr.size(); for (int i = 0; i < size-1; i++){ // 此處size-1是為了j = i+1到達末尾時，不會越界； int min = arr[i]; int index = i; for (int j = i+1; j < size; j++){ if(arr[j] < min){ min = arr[j]; index = j; } } arr[index] = arr[i]; arr[i] = min; printarray(arr); } } // 列印函式； void printarray(vector<int> &arr){ for(int i = 0; i < arr.size(); i++){ cout << arr[i] << " "; } cout << endl; if(DEBUG){ //cout << "left:" << left << " " << "right:" << right << endl; } } int main(){ vector<int> arr; freopen("in.txt", "r", stdin); // 重定向到輸入 int i = 0; int tmp; while (cin >> tmp) { arr.push_back(tmp); // cout << inarray[i] << endl; i++; } int num = i; cout << "輸入資料：" << endl; printarray(arr); cout << endl; if (DEBUG){ cout << "排序程序：" << endl; } // 插入排序演算法呼叫；其他代碼為除錯輸出代碼； selectsort(arr); if (DEBUG){ cout << endl; } cout << "排序結果：" << endl; printarray(arr); return 0; }簡單選擇排序模板
bash-3.2$ c++ 簡單選擇排序.cc; ./a.out 輸入資料： 7 6 5 3 4 2 1 排序程序： 1 6 5 3 4 2 7 1 2 5 3 4 6 7 1 2 3 5 4 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 排序結果： 1 2 3 4 5 6 7簡單選擇排序輸出樣例
排序型別：選擇排序； 時間復雜度：n2; 選擇排序比較次數和序列的初始排序無關；假設待排序的序列有N個元素，次數總為n(n-1)/2次；排序程序中隨著序列情況不同，順序情況也不同； 空間復雜度：簡單選擇排序，需要占用1個臨時空間，用于保存最小值索引；交換時也需要一個臨時空間；所以需要兩個臨時空間； 穩定性：穩定性與否與實作方式有關；可認為是不穩定的；
堆排序：堆排序使用順序存盤的完全二叉樹建造堆結構；分為小頂堆(每個節點的關鍵字都不大于其孩子節點的關鍵字)和大頂堆（每個節點的關鍵字都不小于其孩子節點的關鍵字）；使用大頂堆來進行順序排序；排序分為三個流程：建造堆（最后一個非葉子節點開始n/2），交換堆頂與最后一個元素并輸出堆頂，重新堆化(heapify)；直到交換tree[0]和tree[1]為止；針對于陣列中的每個節點tree[i]來說，其父節點為tree[(i-1)/2], 其左孩子節點為tree[2i+1]，其右孩子節點為tree[2i+2];
堆(heap): 堆是計算機科學中一類特殊的資料結構的統稱；堆可通常是一個可以看做一顆完全二叉樹的陣列物件；
#define DEBUG 1 #include <iostream> #include <cstdio> #include <vector> using namespace std; void printarray(vector<int> &arr); // 交換陣列中 i j 兩個數字的位置； void swapij(vector<int> &arr, int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } void heapify(vector<int> &arr, int n, int index){ int max = index; int c1 = 2*index+1; int c2 = 2*index+2; if(c1 < n && arr[c1] > arr[max]){ // c1 >= arr.size()，該節點沒有左孩子； max = c1; } if(c2 < n && arr[c2] > arr[max]){ // c2 >= arr.size()，該節點沒有右孩子； max = c2; } if(max != index){ // 遞回出口，改節點最大值不是index本身； swapij(arr, index, max); heapify(arr, n, max); } } void build_heap(vector<int> &arr){ // 從最后一個非葉子節點開始； int n = arr.size(); for(int i = n/2; i>=0; i--){ heapify(arr, n, i); if (DEBUG){ printarray(arr); } } } // 使用堆排序進行堆化； void heapsort(vector<int> &arr){ if(DEBUG){ cout << "創建堆：" << endl; } build_heap(arr); // 第一步創建堆 // 交換輸出堆頂，重新堆化 if(DEBUG){ cout << "交換輸出堆頂，重新堆化：" << endl; } int n = arr.size(); for(int i = n-1; i>0; i--){ swapij(arr, 0, i); // 交換堆尾和堆頂元素； heapify(arr, i, 0); // 重新對堆頂進行堆化； if (DEBUG){ printarray(arr); } } } // 列印函式； void printarray(vector<int> &arr){ for(int i = 0; i < arr.size(); i++){ cout << arr[i] << " "; } cout << endl; } int main(){ vector<int> arr; freopen("in.txt", "r", stdin); // 重定向到輸入 int i = 0; int tmp; while (cin >> tmp) { arr.push_back(tmp); // cout << inarray[i] << endl; i++; } int num = i; cout << "輸入資料：" << endl; printarray(arr); cout << endl; if (DEBUG){ cout << "排序程序：" << endl; } // 堆排序； heapsort(arr); if (DEBUG){ cout << endl; } cout << "排序結果：" << endl; printarray(arr); return 0; }堆排序模板
bash-3.2$ c++ 堆排序.cc; ./a.out 輸入資料： 1 5 4 3 10 排序程序： 創建堆： 1 5 4 3 10 1 10 4 3 5 10 5 4 3 1 交換輸出堆頂，重新堆化： 5 3 4 1 10 4 3 1 5 10 3 1 4 5 10 1 3 4 5 10 排序結果： 1 3 4 5 10堆排序輸出樣例
排序類別：選擇排序 時間復雜度：建立堆的時間為O(n)時間；每次調整堆的時間為logn的時間，總共調整n次；所以，時間復雜度為O(nlogn); log認為是以2為底； 空間復雜度：在交換程序中，需要1個輔助陣列；為O(1) 演算法穩定性：堆排序演算法是不穩定的演算法，因為在堆調整程序中，關鍵字比較和交換時節點到葉子節點的一條路徑；因此就可能排在后面的節點交換到前面來；例如 1，2，1，2，3，進行排序；你自己可以在圖紙上演繹一下，
歸并排序：歸并排序 采用分治的思想，將排序問題，分為一些小的問題；然后進行遞回求解；最后進行合并；求得最后的解；
分階段就是把陣列細分，治階段就是把兩個有序的陣列合并成一個有序的陣列；
#define DEBUG 1 #include <iostream> #include <cstdio> #include <vector> using namespace std; void printarray(vector<int> &arr); void printij(vector<int> &arr, int i, int j){ for (;i <= j; i++){ cout << arr[i] << " "; } cout << endl; } void merge(vector<int> &arr, int start, int mid, int end){ if(DEBUG){ cout << "合并前：" << endl; printij(arr, start, mid); printij(arr, mid+1, end); } // 歸并階段 vector<int> tmp; // 創建一個資料，用于保存歸并排序的中間變數； int i = start; int s = start; int j = mid+1; while (i<= mid && j <=end) { if(arr[i]>=arr[j]){ tmp.push_back(arr[j]); j++; }else{ tmp.push_back(arr[i]); i++; } } if (i>mid){ while (j<=end) { tmp.push_back(arr[j]); j++; } } if (j > end){ while (i<=mid) { tmp.push_back(arr[i]); i++; } } for (int k = 0; k < tmp.size(); k++) { arr[start] = tmp[k]; // 注意此處的陣列起點為 start; start++; } if (DEBUG) { cout << "合并后：" << endl; printij(arr, s, end); cout << endl; } } void mergesort(vector<int> &arr, int start, int end){ if (DEBUG) { cout << "分解階段: " << start << " " << end << endl; } if (start == end) return; // 遞回出口 int mid = (end+start)/2; mergesort(arr, start, mid); mergesort(arr, mid+1, end); // 不同于快速排序，歸并排序更強調于merge // merge if (DEBUG) { cout << "合并階段: " << start << " " << mid << " " << end << endl; } merge(arr, start, mid, end); } // 列印函式； void printarray(vector<int> &arr){ for(int i = 0; i < arr.size(); i++){ cout << arr[i] << " "; } cout << endl; } int main(){ vector<int> arr; freopen("in.txt", "r", stdin); // 重定向到輸入 int i = 0; int tmp; while (cin >> tmp) { arr.push_back(tmp); // cout << inarray[i] << endl; i++; } int num = i; cout << "輸入資料：" << endl; printarray(arr); cout << endl; if (DEBUG){ cout << "排序程序：" << endl; } // 歸并排序 mergesort(arr, 0, arr.size()-1); if (DEBUG){ cout << endl; } cout << "排序結果：" << endl; printarray(arr); return 0; }歸并排序代碼模板
bash-3.2$ c++ 歸并排序.cc; ./a.out 輸入資料： 1 5 10 3 4 排序程序： 分解階段: 0 4 分解階段: 0 2 分解階段: 0 1 分解階段: 0 0 分解階段: 1 1 合并階段: 0 0 1 合并前： 1 5 合并后： 1 5 分解階段: 2 2 合并階段: 0 1 2 合并前： 1 5 10 合并后： 1 5 10 分解階段: 3 4 分解階段: 3 3 分解階段: 4 4 合并階段: 3 3 4 合并前： 3 4 合并后： 3 4 合并階段: 0 2 4 合并前： 1 5 10 3 4 合并后： 1 3 4 5 10 排序結果： 1 3 4 5 10歸并排序輸出樣例
排序種類：歸并排序；
時間復雜度：歸并排序就是一個二叉樹；遍歷的深度為logn;每層的合并數為n;總體時間為nlogn;
空間復雜度：合并程序中需要，大小為n的臨時空間存盤中間變數；復雜度為n;
演算法穩定性：合并程序中相等元素的順序不會改變；為穩定演算法；
與其他演算法比較：空間復雜度角度，首先選擇堆排序，其次快速排序，最后是歸并排序；時間復穩定角度來看，應該選擇歸并排序，因為堆排序和快速排序是不穩定的排序；
平均排序速度情況下考慮：應該選擇快速排序；
基數排序：基數排序，也稱為桶排序和箱排序，比較適合有限范圍的關鍵字進行排序；由整數舉例，其原理是將整數按位數切割成不同的數字，然后按每位分別進行比較；先由個位開始然后分配到10個桶中，然后依次收集；再按照十位進行排序，然后百位，直至最高位；
#define DEBUG 1 #include <iostream> #include <cstdio> #include <vector> using namespace std; void printarray(vector<int> &arr); // 針對于整數的桶排序 void bucketsort(vector<int> &arr, int base){ int n = arr.size(); // 確定待排序數字的總數； //建立10個桶 vector<int> bucket[10]; for(int i = 0; i < n; i++){ bucket[(arr[i]/base)%10].push_back(arr[i]); } if(bucket[0].size()==n){ return; //遞回出口 } int index = 0; for(int i = 0; i < 10; i++){ for (int j = 0; j < bucket[i].size(); j++) { arr[index] = bucket[i][j]; index++; } } if(DEBUG){ printarray(arr); } bucketsort(arr, base*10); } // 列印函式； void printarray(vector<int> &arr){ for(int i = 0; i < arr.size(); i++){ cout << arr[i] << " "; } cout << endl; } int main(){ vector<int> arr; freopen("in.txt", "r", stdin); // 重定向到輸入 int i = 0; int tmp; while (cin >> tmp) { arr.push_back(tmp); // cout << inarray[i] << endl; i++; } int num = i; cout << "輸入資料：" << endl; printarray(arr); cout << endl; if (DEBUG){ cout << "排序程序：" << endl; } // 基數排序 bucketsort(arr, 1); // 桶排序演算法； if (DEBUG){ cout << endl; } cout << "排序結果：" << endl; printarray(arr); return 0; }基數排序代碼實作
bash-3.2$ c++ 基數排序.cc; ./a.out 輸入資料： 614 738 921 485 637 101 215 530 790 306 排序程序： 530 790 921 101 614 485 215 306 637 738 101 306 614 215 921 530 637 738 485 790 101 215 306 485 530 614 637 738 790 921 排序結果： 101 215 306 485 530 614 637 738 790 921基數排序輸出樣例
排序類別：基數排序； 時間復雜度：O(k*(n+m)); k為關鍵字種類；n為關鍵字的個數；m為每種關鍵字（桶的個數）的取值范圍； 空間復雜度：O(n) 需要m個桶的空間來存盤值；但是桶的總容量為n;如果使用鏈表來實作的話，桶空間可以進行復用； 演算法穩定性：每次都是從左到右，按照關鍵詞，裝入對應桶中，在裝入的程序中沒有交換元素位置，所以基數排序演算法是穩定的；
保持更新，轉載請注明出處；更多內容請關注cnblogs.com/xuyaowen；如果對您有幫助，歡迎點擊推薦~！
本文章所有排序代碼實作位于：https://github.com/yaowenxu/codes/tree/master/排序演算法
注：本題圖整理自參考博客；
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/71890.html
標籤：其他
上一篇：vs2019。hello，world無法運行，總是顯示錯誤，無法找到找到源檔案studio.h，無法打開包括檔案
下一篇：Dr.VAE