2022計算機考研408—數據結構—排序
手把手教學考研大綱范圍內的排序
22考研大綱數據結構要求的是C/C++，筆者以前使用的都是Java，對于C++還很欠缺，
如有什么建議或者不足歡迎大佬評論區或者私信指出

Talk is cheap. Show me the code.
理論到處都有，代碼加例題自己練習才能真的學會

排序過程步驟顯示

文末投票：下篇22考研數據結構的博客寫什么（歡迎評論區指出）

排序定義
冒泡排序
直接插入排序
二分插入排序
希爾排序?
快速排序
二路歸并排序?
基數排序（附加計數排序）?
簡單選擇排序
堆排序??

排序

排序的基本概念

顧名思義，給一個無序數組的值進行順序存儲

原數組：2 3 1 5 6 4 8 9 7 排序后：1 2 3 4 5 6 7 8 9

冒泡排序

思路：
從頭到尾每兩個相鄰的元素，進行比較，前面的比后面的大就進行交換
循環一遍后，數組元素最大的就到了最后面，
第二次循環的時候，就可以不循環到最后一個了，最后一個上次循環已經是整個數組最大的值了
然后把這次最大的放到倒數第二個元素，
第三次循環的就可以忽略最后兩個元素
以此類推，全部循環后，即可完成排序

#include <iostream> #include <vector>using namespace std;void bubbleSort(vector<int> &num); int main() {int n; //n為將要輸入的數組長度cin >> n; //輸入n cin方法需要上面使用stdvector<int> num; //定義vector 記得上面導入vectorint temp; //temp為輸入vector時的中間變量for (int i = 0; i < n; i++) {cin >> temp; //輸入num.push_back(temp);}bubbleSort(num); //調用自定義的排序方法cout << "排序后" << "\n";for (int i = 0; i < num.size(); i++) {cout << num[i] << " "; //輸出}return 0; }void bubbleSort(vector<int> &num) {for (int i = 0; i < num.size(); i++) {for (int j = 0; j < num.size() - i; j++) {if (num[j] > num[j + 1]) { // int temp = num[j]; // num[j] = num[j + 1]; // num[j + 1] = temp;num[j] ^= num[j + 1]; //兩兩相鄰交換 上面注釋代碼的功能與此功能相等num[j + 1] ^= num[j];num[j] ^= num[j + 1];}}//每次循環都把數組的變動輸出出來for (int j = 0; j < num.size(); j++) {cout << num[j] << " ";}cout << "\n";} }

//冒泡排序的變種#include <iostream> #include <vector>using namespace std;void bubbleSort(vector<int> &num); int main() {int n; //n為將要輸入的數組長度cin >> n; //輸入n cin方法需要上面使用stdvector<int> num; //定義vector 記得上面導入vectorint temp; //temp為輸入vector時的中間變量for (int i = 0; i < n; i++) {cin >> temp; //輸入num.push_back(temp);}bubbleSort(num); //調用自定義的排序方法for (int i = 0; i < num.size(); i++) {cout << num[i] << " "; //輸出}return 0; }void bubbleSort(vector<int> &num) {int flag = 1; //flag用來判斷，如果本次循環沒有進行交換，該數組為有序數組int arrBoundary = num.size() - 1; //用來記錄上一次循環最后一次交換位置，后面沒有交換的是有序的int largestSwapIndex = 0; //記錄最后一次交換的位置for (int i = 0; i < num.size(); i++) {flag = 1;for (int j = 0; j < arrBoundary ; j++) {if (num[j] > num[j + 1]) {int temp = num[j];num[j] = num[j + 1];num[j + 1] = temp;flag = 0; //發生交換就改為0largestSwapIndex = j; //交換位置就給largestSwapIndex}}arrBoundary = largestSwapIndex; //把當前循環交換的最后一個下標給arrBoundaryif (flag) { //如果本次循環沒有交換任何值，證明當前數組為有序數組break;}}}

直接插入排序

思路：
插入 == 把數插進去
也是兩層循環
數組num

第一層循環從下標為1的值開始，循環變量為i
第二層循環就是把第一層的值拿出來，然后從第i-1個向前循環，找到第一個小于 num[i] 的值，
這個值的下標如果是j-1的話，那么 num[j] 就是第一個大于 num[i] 的值
把 num[i] 用一個變量 temp 保存一下
把下標為j到i-1的值依次向后移動一位，也就是說下標j到i-1的值移動到j+1到i，
然后把 temp(原num[i])放到下標為j的地方（之前的num[j]已經移動到num[j+1]了），

按照這種排序，每次循環的都是i之前的，i之前的元素都是順序存儲的，
文字表述的不清楚的可以看每次循環i更改后數組的元素情況

#include <iostream> #include <vector>using namespace std;void insertSort(vector<int> &num); int main() {int n; //n為將要輸入的數組長度cin >> n; //輸入n cin方法需要上面使用stdvector<int> num; //定義vector 記得上面導入vectorint temp; //temp為輸入vector時的中間變量for (int i = 0; i < n; i++) {cin >> temp; //輸入num.push_back(temp);}insertSort(num); //調用自定義的排序方法cout << "排序后" << "\n";for (int i = 0; i < num.size(); i++) {cout << num[i] << " "; //輸出}return 0; }void insertSort(vector<int> &num) {for (int i = 1; i < num.size(); i++) {int temp = num[i]; //保存一下num[i]int j;//從num[j]向前開始找，一直找到比temp(原num[i])小的數就結束//在循環過程中的數都比temp大的，不斷地把temp大的數往后移動一位//由此可得，等找到num[j]<=temp的時候，循環已經結束了// 但是他的上一個，也就是num[j+1]的值已經移動到num[j+2]了for (j = i - 1; j >= 0 && num[j] > temp; j--) {num[j + 1] = num[j];}//可以直接把temp放到num[j+1]，num[j + 1] = temp;//每次循環都可以把num[i]以及之前的數值排序好//每次循環都把數組的變動輸出出來for(j = 0; j < num.size(); j++) {cout << num[j] << " ";}cout <<"\n";} }

運行截圖：

二分插入排序

思路：
二分插入和簡單插入基本類似
不過是在尋找插入位置的時候不在采用簡單插入的循環查找，而是使用二分查找
減少比較的次數，提升效率

#include <iostream> #include <vector>using namespace std;void binInsertSort(vector<int> &num); int main() {int n; //n為將要輸入的數組長度cin >> n; //輸入n cin方法需要上面使用stdvector<int> num; //定義vector 記得上面導入vectorint temp; //temp為輸入vector時的中間變量for (int i = 0; i < n; i++) {cin >> temp; //輸入num.push_back(temp);}binInsertSort(num); //調用自定義的排序方法cout << "排序后" << "\n";for (int i = 0; i < num.size(); i++) {cout << num[i] << " "; //輸出}return 0; }void binInsertSort(vector<int> &num) {for (int i = 1; i < num.size(); i++) {int temp = num[i]; //保存臨時變量int left = 0; //使用二分法找到插入的位置left 使得num[left]<temp<num[left+1]int right = i - 1;while (left <= right) {int mid = (left + right) / 2;if (num[mid] > temp) {right = mid - 1;} else {left = mid + 1;}}for (int j = i - 1; j >= left; j--) {num[j + 1] = num[j]; //把left右面的值全部右移一位，}num[left] = temp; //把temp放到num[left]的位置//每次循環都把數組的變動輸出出來for (int j = 0; j < num.size(); j++) {cout << num[j] << " ";}cout << "\n";} }

希爾排序

思路：

希爾排序其實可以看做是插入排序的變種
插入排序是循環到某個元素就像前找合適的位置，把當前元素到合適位置的值都要向后移動一遍
插入排序對于有序的數組，比較和移動的次數都比較少
希爾排序就是把插入排序進行分組化

分組是按照長度每次除2分的，這樣最后一次肯定是一個組一個元素，就相當于最原始的插入排序了
而他前面做的按組排序就是為了讓這個數組變成一個有大概順序的數組，使后面的插入排序能減少比較和移動的次數

按下圖為例子，數組長度15 第一次按照7個增量分組，第二次按照3個增量，第三次按照1個增量分組第一次循環的增量為7 第一次是下標 0 與 0+7比較 1與1+7比較 …… 7 與 7+7比較 第一次循環完，這些位置上有了個大概的順序第二次循環的增量為3 第二次是下標 0與3與6與9與12比較 1與4與7與10與13 2與5與8與11與14 第二次循環完，這些位置上有了大概的順序第三次循環的增量為1 就相當于簡單的插入排序

希爾排序的精髓就在于，對于一個大概有序的數組，插入排序的比較和移動次數都比較少

PS：小編作圖能力有限，上圖是當來的

//除main方法外的其他cout輸出都是為了讓讀者更清楚的了解每次循環后進行排序的下標 #include <iostream> #include <vector>using namespace std;void shellSort(vector<int> &num);int main() {int n; //n為將要輸入的數組長度cin >> n; //輸入n cin方法需要上面使用stdvector<int> num; //定義vector 記得上面導入vectorint temp; //temp為輸入vector時的中間變量for (int i = 0; i < n; i++) {cin >> temp; //輸入num.push_back(temp);}shellSort(num); //調用自定義的排序方法cout << "\n\n排序后" << "\n";for (int i = 0; i < num.size(); i++) {cout << num[i] << " "; //輸出}return 0; }void shellSort(vector<int> &num) {int len = num.size();for (int d = len / 2; d > 0; d/=2) { //按照增量分組，增量每次/2cout << "\n\n增量為" << d;for (int i = d; i < len; i++) { //類似插入排序，每次都比較i之前的，cout << "\n此次排序的下標為:" << i;for (int j = i - d; j >=0; j-=d) {cout << " " << j;//這里i-d其實也就是從前面開始，// j每次都是j-=d，因為我們是按照相同增量分為一組的// 對比上圖更容易理解if (num[j] > num[j + d]) { //只要前面的比后面的大，就交換位置int temp = num[j];num[j] = num[j + d];num[j + d] = temp;}}//每次循環都把數組的變動輸出出來cout << "\n";for (int j = 0; j < num.size(); j++) {cout << num[j] << " ";}}} }

快速排序

思路：
從未排序的數組中，一個一個的尋找，尋找當前值應該在排序后數組的位置，
以此類推，把每個值的位置都確定了以后，此數組就變成了排序后的數組
也是分段進行確定某個值最終排序后的下標

先選取第一個值，用一個臨時變量保存這個值，然后雙指針i表示這段范圍的開頭，j這段范圍的結尾 j負責從后向前找小于臨時變量的值，找到以后就把j的值放到i那，此時j位置就空出來了，我們當作把臨時變量的值放到j這里i負責從前向后找大于臨時變量的值，找到后就放到j那里，此時i位置就空出來了，我們同樣當作把臨時變量的值放到i這里不斷循環這兩步的操作，i是從前向后，j是從后向前循環結束的條件就是i==j 也就是臨時變量排序后數組的位置，按照這種排序方式，結束后，比臨時變量小的都在臨時變量左邊（左邊不一定是排好序的），比臨時變量大的都在臨時變量右邊（右邊不一定是排好序的），也就是說臨時變量當前的下標就是排序后的下標 當前臨時變量的位置確定好以后，我們可以分為前半部分和后半部分繼續這種操作 以此類推，當每個值最終排序后的位置都確定的時候，此數組為排序后的數組

下圖為確定好一個值的最終位置的排序圖

臨時變量為50，左指針low，右指針high

右指針找到20比臨時變量小，交換兩個值

左指針找到90比臨時變量大，交換兩個值

右指針找到40比臨時變量小，交換兩個值位置

左指針找到70比臨時變量小，交換兩個值的位置

右指針左移與左指針重合，當前位置為50排序后的最終位置

我們發現，左邊的數都比50小，右邊的數都比50大，
當前數的位置就是排序后當前數的位置 然后在把左邊的數組按照這種方法，右邊的數組按照這種方法
以此類推每個值的最終下標都確定下來了，數組為排序后的數組
PS：圖仍然是某度當來的o(￣▽￣)ブ

#include <iostream> #include <vector>using namespace std;void quickSort(vector<int> &num, int left, int right);int main() {int n; //n為將要輸入的數組長度cin >> n; //輸入n cin方法需要上面使用stdvector<int> num; //定義vector 記得上面導入vectorint temp; //temp為輸入vector時的中間變量for (int i = 0; i < n; i++) {cin >> temp; //輸入num.push_back(temp);}quickSort(num, 0, num.size() - 1); //調用自定義的排序方法cout << "\n\n排序后" << "\n";for (int i = 0; i < num.size(); i++) {cout << num[i] << " "; //輸出}return 0; }void quickSort(vector<int> &num, int left, int right) {if (left >= right) return; //如果左節點>=右節點了，證明排序結束了，返回即可int temp = num[left]; //保存一下當前左節點的值，此次排序就是確定當前左節點的值int l = left; //保存一下原始的左右邊界int r = right;while (left < right) { //循環的結束條件就是左指針 == 右指針，相等時就為temp排序后的最終位置while (left < right && temp < num[right]) { //右指針找比temp小的值，如果沒找到就一直找right--;}if (left < right) { //上面循環結束了就證明找到了，如果left == right，那么最終位置就確定好了，num[left] = num[right]; //然后把比temp小的放到左面left位置那里，然后left指向下一個值left++; //可能這里有些疑問，上面描述的是交換，這里沒有交換，實際上每次都交換，換來換去，每次都重復換temp這個數} //不如直接賦值，然后把這個重復數直接放到最后確定的位置while (left < right && num[left] < temp) { //這里是左指針找比temp大的數，找到就退出循環了，left++;}if (left < right) { //與上面相反的道理，把比temp大的數放到right，right指針左移num[right] = num[left];right--;}}num[left] = temp; //循環結束就是確定了temp最終的位置，左指針==右指針//每次循環都把數組的變動輸出出來cout << "\n左邊界下標:" << l << " 右邊界下標:" << r << " 當前循環確定的下標為:" << left << "\n";for (int j = 0; j < num.size(); j++) {cout << num[j] << " ";}quickSort(num, l, left - 1); //temp確定好了位置，把temp左面的數組和右面的數組分別進行這種方法排序quickSort(num, left + 1, r); //當每個值的下標都確定的時候，該數組以完成排序 }

二路歸并排序

思路：
二路歸并，就是把一個數組，先分開，然后在合并的過程中逐步排序
二路就是分開的時候每次分成兩個，分成兩種路
歸并就是把他分開在合上

二路分割數組，一直把數組分割到一路只有一個數為止
然后再把他們兩路合一路，兩路合一路，在合路的過程中把無序的路合成有序的路，慢慢的合成后的路都為有序的路，大致原理如下圖

分路沒有什么說的，一分為，對半分即可
合路的時候，AB兩個路合成C路，分別兩個指針i，j，k對應著A，B，C數組的下標
循環AB兩個數組，每次都比較A[i]與B[j] 取兩個數組中對應值小的放到C[k]
然后k下標右移，i或者j小的下標右移，完全循環后，C==A+B的有序路

#include <iostream> #include <vector>using namespace std;void mergeSort(vector<int> &num, int left, int right);int main() {int n; //n為將要輸入的數組長度cin >> n; //輸入n cin方法需要上面使用stdvector<int> num; //定義vector 記得上面導入vectorint temp; //temp為輸入vector時的中間變量for (int i = 0; i < n; i++) {cin >> temp; //輸入num.push_back(temp);}mergeSort(num, 0, num.size() - 1); //調用自定義的排序方法cout << "\n\n排序后" << endl;for (int i = 0; i < num.size(); i++) {cout << num[i] << " "; //輸出}return 0; }void mergeSort(vector<int> &num, int left, int right) {if (left == right) return; //如果左節點和右節點相等，說明就分到底了，一路只剩下一個元素int m = (left + right) / 2; //左節點和右節點的中間節點，從中間節點分路，左面一路，右面一路mergeSort(num, left, m); //先分左面->左面進入后還會從上面再來，接著分，一直分到一路只有一個元素mergeSort(num, m + 1, right); //再分右面//走到這里說明已經分完了，接下來就是合并int temp [right - left + 1]; //定義一個數組，用來存兩路合并后的有序數組int l = left; //左路起始點下標int r = m + 1; //右路起始點下標int k = 0; //合路的起始點下標while (l <= m && r <= right) { //每次放到時候比較對應的值，小的值放到前面，l要在左路的范圍內，r要在右路的范圍內if (num[l] <= num[r]) { //誰小把誰放到合路temp[k++] = num[l++];} else {temp[k++] = num[r++];}}//下面兩個while循環處理的是一路全部放進合路了，另一路沒有完全放進，循環的作用就是把兩路上面沒放進去的全部放進去while (l <= m) {temp[k++] = num[l++];}while (r <= right) {temp[k++] = num[r++];}//temp就是我們合路，然后我們把合好的路放回到num原數組中for (int i = left, k = 0; i <= right; i++, k++) {num[i] = temp[k];}//每次循環都把數組的變動輸出出來cout << "此次合并的是下標：" << left << "-" << right << "\n";for (int j = 0; j < num.size(); j++) {cout << num[j] << " ";}cout << "\n"; }

Acwing，這個題就是歸并排序 788. 逆序對的數量給定一個長度為 n 的整數數列，請你計算數列中的逆序對的數量。逆序對的定義如下：對于數列的第 i 個和第 j 個元素，如果滿足 i<j 且 a[i]>a[j]，則其為一個逆序對；否則不是。輸入格式 第一行包含整數 n，表示數列的長度。第二行包含 n 個整數，表示整個數列。輸出格式 輸出一個整數，表示逆序對的個數。數據范圍 1≤n≤100000， 數列中的元素的取值范圍 [1,109]。輸入樣例： 6 2 3 4 5 6 1 輸出樣例： 5#include <iostream> #include <vector>using namespace std;void mergeSort(vector<int> &num, int left, int right);int res = 0; int main() {int n; //n為將要輸入的數組長度cin >> n; //輸入n cin方法需要上面使用stdvector<int> num; //定義vector 記得上面導入vectorint temp; //temp為輸入vector時的中間變量for (int i = 0; i < n; i++) {cin >> temp; //輸入num.push_back(temp);}mergeSort(num, 0, num.size() - 1); //調用自定義的排序方法cout << res;return 0; }void mergeSort(vector<int> &num, int left, int right) {if (left == right) return; //如果左節點和右節點相等，說明就分到底了，一路只剩下一個元素int m = (left + right) / 2; //左節點和右節點的中間節點，從中間節點分路，左面一路，右面一路mergeSort(num, left, m); //先分左面->左面進入后還會從上面再來，接著分，一直分到一路只有一個元素mergeSort(num, m + 1, right); //再分右面//走到這里說明已經分完了，接下來就是合并int temp [right - left + 1]; //定義一個數組，用來存兩路合并后的有序數組int l = left; //左路起始點下標int r = m + 1; //右路起始點下標int k = 0; //合路的起始點下標while (l <= m && r <= right) { //每次放到時候比較對應的值，小的值放到前面，l要在左路的范圍內，r要在右路的范圍內if (num[l] <= num[r]) { //誰小把誰放到合路temp[k++] = num[l++];} else {temp[k++] = num[r++];res += m - l + 1; //當前l大于r證明l到m的數都大于r//歸并就是一段一段的排好序的數組合并起來的}}//下面兩個while循環處理的是一路全部放進合路了，另一路沒有完全放進，循環的作用就是把兩路上面沒放進去的全部放進去while (l <= m) {temp[k++] = num[l++];}while (r <= right) {temp[k++] = num[r++];}//temp就是我們合路，然后我們把合好的路放回到num原數組中for (int i = left, k = 0; i <= right; i++, k++) {num[i] = temp[k];}}

基數排序

說基數排序之前，先大概說一下計數排序

計數排序

計數排序就是把元素的值當作下標使用，數量用那個下標對應的值記錄
例如int num[]={5，2，1，4，3，2，1，2，6，4，1，2，5，2}
這樣的數組我們就用計數排序
count的長度是上面數組的最大值-最小值+1或者最大值-最小值+1
循環上面的數組 count[num[i]]++;
到時候判斷這個值存不存在，直接判斷count[值]是否大于0
顯而易見，計數排序的缺點就是如果數組中最大值很大，那么這個效率會很低

leetcode 計數排序例題 1122. 數組的相對排序 給你兩個數組，arr1 和 arr2，arr2 中的元素各不相同 arr2 中的每個元素都出現在 arr1 中 對 arr1 中的元素進行排序，使 arr1 中項的相對順序和 arr2 中的相對順序相同。未在 arr2 中出現過的元素需要按照升序放在 arr1 的末尾。示例：輸入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] 輸出：[2,2,2,1,4,3,3,9,6,7,19]提示：1 <= arr1.length, arr2.length <= 1000 0 <= arr1[i], arr2[i] <= 1000 arr2 中的元素 arr2[i] 各不相同 arr2 中的每個元素 arr2[i] 都出現在 arr1 中class Solution {//arr2的數在arr1中一定出現//arr1的數不一定在arr2中有//arr2在arr1中出現過的數，按照arr2的相對順序排列，arr1中剩下的數按照升序排在后面 public:vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {int upper = *max_element(arr1.begin(), arr1.end());vector<int> count(upper + 1);//arr1中的數計數放到countfor (int x: arr1) {++count[x];}vector<int> ans;//如果arr1出現的數，arr2也出現了就輸出//這樣就是按照arr2的相對順序輸出for (int x: arr2) {for (int i = 0; i < count[x]; ++i) {ans.push_back(x);}//arr2出現的數字，就添加到ans里面，//添加過就把這個數字清零了，count[x] = 0;}//把剩下的未在arr2中出現的按照升序輸出for (int x = 0; x <= upper; ++x) {for (int i = 0; i < count[x]; ++i) {ans.push_back(x);}}return ans;} };

再回來說基數排序
基數排序也是大概這個意思，不過不是直接把值當作下標，而是把值的每一位當作下標排序
這個也需要保存一下最大值，因為要判斷最高有多少位。
先把個位放進去，排序，再把十位放進去排序，然后……

把個位放進去后，就按照個位排序好了，把數取出，記得按照順序取出， 然后十位放進去排序，把數按順序取出……
思路大概就是這樣
順序放入順序取出，在進行下一位的排序
PS:
如果是Java的話，直接用一個ArrayList[] temp; 這種數組就可以

PS：當來的圖片

#include <iostream> #include <vector>using namespace std;void radixSort(vector<int> &num);int main() {int n; //n為將要輸入的數組長度cin >> n; //輸入n cin方法需要上面使用stdvector<int> num; //定義vector 記得上面導入vectorint temp; //temp為輸入vector時的中間變量for (int i = 0; i < n; i++) {cin >> temp; //輸入num.push_back(temp);}radixSort(num); //調用自定義的排序方法cout << "\n\n排序后" << endl;for (int i = 0; i < num.size(); i++) {cout << num[i] << " "; //輸出}return 0; }void radixSort(vector<int> &num) {int max = -1;for (int i = 0; i < num.size(); i++) {max = max < num[i] ? num[i] : max;}int temp[num.size()];int count[10] = {0};for (int i = 0; i < num.size(); i++) {temp[i] = 0; //初始化temp賦值0}for (int places = 1; places <= max; places *= 10) { //基數排序就是按照位數進行排序，所以循環的次數就是數字位數for (int i = 0; i < num.size(); i++) {count[(num[i] / places) % 10]++; // 記錄一下當前位上，各個數字的個數} //count[3]如果是5 就代表的個位為3的數是5個//當前位置上各個數字的個數確定了，我們就可以確定當前位某個數字的范圍了//count[0] = 3, count[1] = 4, count[2] = 7, count[3] = 2……//當前位上為0的數在此次排序后的位置為數組1-3，當前位為1的數在此次位置為4-7，當前位為2的數的范圍8-14……//也就是前面的和，加起來，得出的count[i] 就是當前位為i的數的范圍的右邊界for (int i = 1; i < 10; i++) {count[i] = count[i - 1] + count[i];}//因為我們上面count[i]得出的是當前位為i的時候的右邊界，所以排序后的數組我們也應該從右面放//如果這里我們從左面開始放就會把放入的順序弄反，我們已知右邊界，然后把數字從右開始放順序是正的//當然我們上一步也可以求每段范圍的左邊界，如果求得是左邊界就可以從左放for (int i = num.size() - 1; i >= 0; i--) {int k = (num[i] / places) % 10; //count[k]就是當前位為k的值的右邊界temp[count[k] - 1] = num[i]; //這里的右邊界我們用的是位置，下標要記得-1count[k]--; //當前位為k的數放進去后，count[k]要-1 因為已經放進去一個數了，右邊界左移一位}//當所有的都循環完以后，count[i]代表的是當前位為i的數字范圍的左邊界for (int i = 0; i < 10; i++) {count[i] = 0;}//把此次排序的數組放到num中for (int i = 0; i < num.size(); i++) {num[i] = temp[i];}//輸出展示此次排序后的數組cout << "\n哪一位是1，此次排序就是排的哪一位 " << places << "\n";for (int i = 0; i < num.size(); i++) {cout << num[i] << " ";}}}

簡單選擇排序

思路：
簡單選擇排序，顧名思義，簡單的選擇一個元素排序
兩層循環，第一層循環就是循環每一位
第二層循環，定義臨時變量保存當前下標，循環后面每一位，
如果找到比當前下標對應的值小的，那么就用這個變量保存這個值小的下標，一直循環到結束
第一層循環結束后，變量保存的就是整個數組最小的值的下標，與第一位交換，第一位就是最小的值
如此往復，第二次循環，就從第二位開始向后找，記錄除第一位最小的值的下標，循環結束后與第二位進行交換
以此類推，循環后即可完成排序。

#include <iostream> #include <vector>using namespace std;void selectSort(vector<int> &num);int main() {int n; //n為將要輸入的數組長度cin >> n; //輸入n cin方法需要上面使用stdvector<int> num; //定義vector 記得上面導入vectorint temp; //temp為輸入vector時的中間變量for (int i = 0; i < n; i++) {cin >> temp; //輸入num.push_back(temp);}selectSort(num); //調用自定義的排序方法cout << "排序后" << "\n";for (int i = 0; i < num.size(); i++) {cout << num[i] << " "; //輸出}return 0; }void selectSort(vector<int> &num) {for (int i = 0; i < num.size(); i++) { //循環每一位int temp = i; //保存當前位的下標for (int j = i + 1; j < num.size(); j++) { //循環后面每一位，找到值比當前小的就保存值小的下標if (num[j] < num[temp]) {temp = j;}}int n = num[i]; //temp保存的是i后面最小值的下標，與下標為i的值交換num[i] = num[temp]; //如此往復，小的值到了前面，次小的到了第二位，……num[temp] = n;//每次循環都把數組的變動輸出出來for (int j = 0; j < num.size(); j++) {cout << num[j] << " ";}cout << "\n";} }

運行結果如下：

堆排序

思路：
首先要強調一下，堆排序并不是要構成一個堆，它本身還是個數組，只不過是我們在排序的時候把他看成一個堆，他實際上還是一個數組
我們這里用到的堆是大根堆和小根堆，他們都是完全二叉樹
完全二叉樹就是他們結點位置和滿二叉樹的位置是一樣的

紅色角標為真實數組的下標

PS：圖片來源
這是大根堆和小根堆

完全二叉樹和滿二叉樹基本相同
每一層的數量都是上一層的二倍
某一層最左邊結點下標*2就是最右邊結點下標

完全二叉樹中子結點和父結點之間還有一些顯著的關系
一個數的下標為x
他的父節點下標為（x - 1）/ 2 這里的除2是計算機除2，不保存余數，整除不成為小數
他的左子結點為 2 * x + 1
他的右子結點為 2 * x + 2

如果還不明白，可以自己帶個結點試一下（看堆分析容易理解）
（左子結點-1）/2就是父節點 （右子結點 - 1）/2也是父節點，它除2的時候會把余數直接省去

大根堆就是 父節點 > 左子結點 并且 父節點 > 右子結點
小根堆就是 父節點 < 左子結點 并且 父節點 < 右子結點

構建大根堆只是思想構建，不是實際構建，實際還是數組
先把數組構建成大根堆，大根堆不一定是有序的，但一定是符合大根堆的規律，父結點一定比子結點大，全部構建好（構建大根堆，一定要從下向上構建，如果無序直接從上向下構建，有的會不符合大根堆定義）

默認葉子結點為排好序的堆（葉子結點沒有子結點，只有一層，符合大跟堆得特征） 先添加非葉子結點，逐步向上添加 如果從上到下結點添加，葉子結點為有序堆，上到下添加會把有序堆打散，無法完成堆排序 完全二叉樹的特點，n個結點，最后一個非葉子結點二叉樹為（n/2）下標為（n/2-1），逐步向上添加

構建好大根堆后，轉換成小根堆

轉換小根堆的步驟，先把大根堆最大的（也就是堆頂）與最后面的結點換位置，這樣能保證最大的在最后面，也就是說，數組第一位與最后一位交換
交換完，小的就到了最上面，把剛交換完最大的固定不動，其他的重新構建大根堆
此時最大的在最后面，其他的仍然是大根堆

第二次的時候，把當前大根堆最大的值（當前堆頂）與倒數第二位交換（倒數第一位是剛才的堆頂，最大的，已經固定了，保持不變），最小的又到了堆頂，繼續重建大根堆
如此往復，大根堆就變成了小根堆，此時的小根堆就是有序的

#include <iostream> #include <vector>using namespace std;void heapSort(vector<int> &num);void heapBuild(vector<int> &num, int fatherIndex, int len);int main() {int n; //n為將要輸入的數組長度cin >> n; //輸入n cin方法需要上面使用stdvector<int> num; //定義vector 記得上面導入vectorint temp; //temp為輸入vector時的中間變量for (int i = 0; i < n; i++) {cin >> temp; //輸入num.push_back(temp);}heapSort(num); //調用自定義的排序方法cout << "\n\n排序后" << endl;for (int i = 0; i < num.size(); i++) {cout << num[i] << " "; //輸出}return 0; }void heapSort(vector<int> &num) {//構建大根堆for (int i = num.size() / 2 - 1; i >= 0; i--) { // 倒數第二排開始, 創建大頂堆，必須從下往上比較heapBuild(num, i, num.size()); // 否則有的不符合大頂堆定義}cout << "構建完大根堆后的數組\n";for (int i = 0; i < num.size(); i++) {cout << num[i] << " ";}int len = num.size();//也算一種選擇排序，因為每次把大根放到最后就少排序一個while (len > 1) {//每次都把大根與最后面的值交換，int temp = num[0];num[0] = num[len - 1];num[len - 1] = temp;len--; //最后一個元素也就是剛才的大根已經確定好了，可以少排序一個元素heapBuild(num, 0, len); //除去確定好的大根，把剩下的元素重新構建cout << "\n下標："<< len << " 值：" << num[len] <<" 確定好位置了\n";for (int i = 0; i < num.size(); i++) {cout << num[i] << " ";}} }void heapBuild(vector<int> &num, int fatherIndex, int len) {//堆（完全二叉樹）左子結點和右子結點與父結點的關系int left = fatherIndex * 2 + 1;int right = fatherIndex * 2 + 2;while (left < len) {int largestIndex; //largestIndex保存的是當前子結點與父結點中最大的索引if (num[left] < num[right] && right < len) {largestIndex = right;} else {largestIndex = left;}if (num[largestIndex] < num[fatherIndex]) { //如果父節點大于子結點，當前符合大根堆,退出即可largestIndex = fatherIndex;break;}//不符合大根堆就交換int temp = num[largestIndex];num[largestIndex] = num[fatherIndex];num[fatherIndex] = temp;//接著去下面構建大根堆fatherIndex = largestIndex;left = fatherIndex * 2 + 1;right = fatherIndex * 2 + 2;} }

總結

以上是生活随笔為你收集整理的22计算机408考研—数据结构—排序（详解加例题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。