C++實現(xiàn)十大排序算法及排序算法常見問題
前言
本文為C++實現(xiàn)的十大排序算法及基于排序算法解決的一些常見問題,每一種算法均實際運行,確保正確無誤。文中內(nèi)容為自己的一些理解,如有錯誤,請大家指正。
0 概述
在十種排序算法中,前七種是比較類排序,后三種是非比較類排序,每種算法的最好、最壞、平均時間復(fù)雜度,空間復(fù)雜度以及穩(wěn)定性如下表所示。穩(wěn)定性是指排序前后相等的元素相對位置保持不變。
排序算法 | 平均時間復(fù)雜度 | 最好情況 | 最壞情況 | 空間復(fù)雜度 | 穩(wěn)定性 |
冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 穩(wěn)定 |
選擇排序 | O(n²) | O(n²) | O(n²) | O(1) | 不穩(wěn)定 |
插入排序 | O(n²) | O(n) | O(n²) | O(1) | 穩(wěn)定 |
希爾排序 | O(nlogn) | O( |
O(n²) | O(1) | 不穩(wěn)定 |
歸并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n + logn) | 穩(wěn)定 |
堆排序 | O(nlogn) | O(nlogn) | O(n²) | O(logn) | 不穩(wěn)定 |
快速排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩(wěn)定 |
計數(shù)排序 | O(n + k) | O(n + k) | O(n²) | O(n + k) | 穩(wěn)定 |
桶排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | 穩(wěn)定 |
基數(shù)排序 | O(n × k) | O(n × k) | O(n × k) | O(n + k) | 穩(wěn)定 |
具體思路和代碼均為升序排序。
前三種排序比較類似,都是將數(shù)組劃分成已排序部分和未排序部分,因此有兩層循環(huán),一層循環(huán)劃分已排序和未排序部分的邊界,一層循環(huán)選擇不同的方法依次對未排序的部分進(jìn)行排序。
1 冒泡排序
顧名思義,冒泡排序(bubble sort)是將最大的數(shù)依次 “上浮” 到數(shù)組的末尾,實現(xiàn)數(shù)組有序。
具體的算法實現(xiàn)原理:
兩層循環(huán),第一層劃分邊界,從后向前,后面部分為已排序部分。第二層循環(huán)從最前往后(截止到邊界)依次兩兩比較,如果前面的數(shù)比后面的數(shù)大,則交換兩個數(shù),如果前面的數(shù)比后面的數(shù)小,則保持不變。當(dāng)邊界移動到第一個數(shù),數(shù)組實現(xiàn)有序。
動態(tài)圖解:
代碼:
#include <iostream> #include <vector> using namespace std; //冒泡排序 void bubbleSort(vector<int> &vec){ int len = vec.size(); if (len <= 1){ return; } for (int i = len -1; i > 0; i--){ bool flag = false; //使用flag判斷j前面的子序列是否已經(jīng)有序 for (int j = 0; j < i; j++){ if (vec[j] > vec[j + 1]){ swap(vec[j], vec[j + 1]); flag = true; } } if (!flag){ break; } } } //打印數(shù)組 void printVec(vector<int> vec){ for (auto c : vec){ cout << c << " "; } cout << endl; } //test int main(){ vector<int> test_vec = {1, 2, 5, 7, 3, 5, 9, 33, 44, 99, 55}; printVec(test_vec); bubbleSort(test_vec); printVec(test_vec); system("pause"); return 0; }
2 選擇排序
具體的算法實現(xiàn)原理:
選擇排序(selection sort)已排序部分為數(shù)組的前部,然后選擇數(shù)組后部未排序中的最小的數(shù)依次與未排序的第一個數(shù)交換(交換會造成排序不穩(wěn)定),然后邊界后移,繼續(xù)選擇、交換,直到數(shù)組有序。
兩層循環(huán),第一層劃分邊界,第二層循環(huán)查找未排序部分最小的數(shù),并與未排序部分的第一個數(shù)交換。
動態(tài)圖解:
代碼:
#include <iostream> #include <vector> using namespace std; //選擇排序 void selectSort(vector<int> &vec){ int len = vec.size(); if (len <= 1){ return; } for (int i = 0; i < len; i++){ int min = i; for (int j = i; j < len; j++){ if (vec[j] < vec[min]){ min = j; } } swap(vec[i], vec[min]); } } //打印數(shù)組 void printVec(vector<int> vec){ for (auto c : vec){ cout << c << " "; } cout << endl; } //test int main(){ vector<int> test_vec = {1, 5, 2, 7, 3, 5, 9, 33, 44, 99, 55}; printVec(test_vec); selectSort(test_vec); printVec(test_vec); system("pause"); return 0; }
3 插入排序
具體的算法實現(xiàn)原理:
插入排序(insertion sort)已排序部分也為數(shù)組的前部,然后將未排序部分的第一個數(shù)插入到已排序部分的合適的位置。
兩層循環(huán),第一層劃分邊界,第二層循環(huán)將已排序部分的數(shù)從后向前依次與未排序部分的第一個數(shù)比較,若已排序部分的數(shù)比未排序部分的第一個數(shù)大則交換,這樣未排序部分的第一個數(shù)就插入到已排序部分的合適的位置,然后向后移動邊界,重復(fù)此過程,直到有序。
動態(tài)圖解:
代碼:
#include <iostream> #include <vector> using namespace std; //插入排序 void insertSort(vector<int> &vec){ int length = vec.size(); if (length <= 1){ return; } for (int i = 1; i < length - 1; i++){ //int temp = vec[i]; for (int j = i - 1; j >= 0; j--){ if (vec[j] > vec[j + 1]){ swap(vec[j+1], vec[j]); } } } } //打印數(shù)組 void printVec(vector<int> vec){ for (auto c : vec){ cout << c << " "; } cout << endl; } //test int main(){ vector<int> test_vec = {1, 5, 2, 7, 3, 5, 9}; printVec(test_vec); insertSort(test_vec); printVec(test_vec); system("pause"); return 0; }
4 希爾排序
希爾排序是插入排序的升級,算法原理如下:
1) 首先,從數(shù)組的首元素開始每隔“步長(間隔)”個元素就挑選一個元素出來作為子數(shù)組元素;
2) 然后每個子數(shù)組各自進(jìn)行比較,比較好后,每個子數(shù)組都有順序,進(jìn)入下一輪,步長(間隔)減少,再根據(jù)步長(間隔)分組進(jìn)行比較;
3) 重復(fù)以上操作,最后就有序了。
圖解:
代碼:
#include <iostream> #include <vector> using namespace std; //希爾排序 void shellSort(vector<int> &vec){ int len = vec.size(); if (len <= 1) return; //以h為步長劃分?jǐn)?shù)組,h /= 2為縮小的增量,數(shù)字2可自己根據(jù)數(shù)據(jù)選擇 for (int h = len / 2; h > 0; h /= 2){ //以下為插入排序 for (int j = h; j < len; j++){ int temp = vec[j]; for (int k = j - h; k >= 0; k -= h){ if (vec[k] > temp){ swap(vec[k], vec[k + h]); } } } } } //打印數(shù)組 void printVec(vector<int> vec){ for (auto c : vec){ cout << c << " "; } cout << endl; } //test int main(){ vector<int> test_vec = {1, 5, 2, 7, 3, 5, 9, 33, 44, 99, 55}; printVec(test_vec); shellSort(test_vec); printVec(test_vec); system("pause"); return 0; }
5 歸并排序
歸并排序(Merge Sort)是分治思想的一個典型應(yīng)用,如果要排序一個數(shù)組,我們先把數(shù)組從中間分成前后兩部分,然后對前后兩部分分別排序,再將排好序的兩部分合并在一起,這樣整個數(shù)組就都有序了(前后兩部分也采用相同的方法排序,即將前后兩部分分別再從中間分成兩部分排序后合并,以此類推,直到數(shù)組不可再分)。因此,歸并排序是一個先分再合的過程,用到的思想為分治,具體實現(xiàn)方式為遞歸。
下面的圖解很清晰的說明了歸并排序的原理。
現(xiàn)在弄清楚原理了,但還有一個問題沒有解決:如何合并兩個排好序的前后數(shù)組?答案很簡單,雙指針 + 臨時數(shù)組。指針P1指向前面數(shù)組的首元素,指針P2指向后面數(shù)組的首元素,比較大小,將較小的元素放在臨時數(shù)組helper中,然后將指向較小元素的指針后移,再次比較,將較小的元素放入臨時數(shù)組。如此反復(fù),直到前后兩個數(shù)組中的某個指針到達(dá)邊界,然后將未到達(dá)邊界的數(shù)組剩余的元素放入臨時數(shù)組尾部,合并完成。最后將合并好的元素拷貝到原數(shù)組。
具體代碼如下:
#include <iostream> #include <vector> using namespace std; void mergeSort(vector<int> &vec, int left, int right); void merge(vector<int> &vec, int left, int mid, int right); void printVec(vector<int> vec); //test int main(){ vector<int> test_vec = {1, 5, 2, 7, 23, 5, 9, 33, 44, 99, 55}; printVec(test_vec); mergeSort(test_vec, 0, test_vec.size() - 1); printVec(test_vec); system("pause"); return 0; } //歸并排序,先分再合 void mergeSort(vector<int> &vec, int left, int right){ if (left >= right){ return; } //int mid = left + (right - left) / 2; int mid = left + ((right - left) >> 1); mergeSort(vec, left, mid); mergeSort(vec, mid + 1, right); merge(vec, left, mid, right); //合并 } //合并,雙指針 + 臨時數(shù)組 void merge(vector<int> &vec, int left, int mid, int right){ int n = right - left + 1; vector<int> helper(n, 0); //臨時數(shù)組 int i = 0; int p1 = left; //第一個指針 int p2 = mid + 1; //第二個指針 //在兩個指針都沒有越過邊界的情況下,將兩個數(shù)組中較小的數(shù)放入臨時數(shù)組,并將指針后移 while (p1 <= mid && p2 <= right){ helper[i++] = vec[p2] < vec[p1] ? vec[p2++] : vec[p1++]; } //將未到達(dá)邊界的數(shù)組的剩余元素拷貝到臨時數(shù)組尾部 while (p1 <= mid){ helper[i++] = vec[p1++]; } while (p2 <= right){ helper[i++] = vec[p2++]; } //將臨時數(shù)組的元素拷貝到原數(shù)組 for (int j = 0; j < n; j++){ vec[left + j] = helper[j]; } } //打印數(shù)組 void printVec(vector<int> vec){ for (auto c : vec){ cout << c << " "; } cout << endl; }
6 堆排序
堆排序(Heap Sort)的思路步驟為(假設(shè)數(shù)組共有n個元素):將待排序數(shù)組構(gòu)造成一個大頂堆,此時,整個數(shù)組的最大值就是堆頂?shù)母?jié)點。將其與末尾元素進(jìn)行交換,此時末尾就為最大值。然后將剩余n-1個元素重新構(gòu)造成一個大頂堆,這樣會得到n個元素的次小值,再次交換堆頂元素和第n-1個元素,這樣倒數(shù)后兩個數(shù)為最大的兩個數(shù)且有序。如此反復(fù)執(zhí)行,便能得到一個有序數(shù)組了。
動態(tài)圖解:
簡化一下:①構(gòu)建大頂堆 → ②交換元素 → ③重構(gòu)大頂堆 → ④交換元素 → 循環(huán)③④ 步
具體代碼如下:
#include <iostream> #include <vector> using namespace std; void heapSort(vector<int> &vec); void heapInsert(vector<int> &vec, int index); void heapify(vector<int> &vec, int index, int len); void print_vec(vector<int> vec); int main(){ vector<int> test_vec = {3, 1, 4, 6, 2, 7, 5, 8, 2, 12}; int len = test_vec.size(); print_vec(test_vec); heapSort(test_vec); print_vec(test_vec); system("pause"); return 0; } //堆排序 void heapSort(vector<int> &vec){ int len = vec.size(); if (len <= 1){ return; } //構(gòu)建大頂堆 for (int i = 0; i < len; i++){ heapInsert(vec, i); } //交換堆頂元素和末尾元素 swap(vec[0], vec[--len]); //循環(huán),重構(gòu)大頂堆,交換元素 while (len > 0){ heapify(vec, 0, len); swap(vec[0], vec[--len]); } } //index的父節(jié)點為(index - 1) / 2 void heapInsert(vector<int> &vec, int index){ while (vec[index] > vec[(index - 1) / 2]){ swap(vec[index], vec[(index - 1) / 2]); index = (index - 1) / 2; } } //重構(gòu)[index, len)的區(qū)間為大頂堆 void heapify(vector<int> &vec, int index, int len){ int leftson = index * 2 + 1; //index的左子節(jié)點,leftson + 1為右子節(jié)點 while(leftson < len){ int largest = (leftson + 1 < len && vec[leftson+ 1] > vec[leftson]) ? leftson + 1 : leftson; largest = vec[largest] > vec[index] ? largest : index; if (largest == index){ break; } swap(vec[index], vec[largest]); index = largest; leftson = index * 2 + 1; } } //打印數(shù)組 void print_vec(vector<int> vec){ for (auto c : vec){ cout << c <<" "; } cout << endl; }
7 快速排序
快速排序(Quick Sort)也用到了分治思想,如果要排列下標(biāo)從 left 到 right 的數(shù)組,我們可以選擇從 left 到 right 之間的任意一個元素作為分區(qū)點P,然后遍歷從 left 到 right 的元素,將小于等于分區(qū)點P的數(shù)放在左邊,大于分區(qū)點P的數(shù)放在右邊,將分區(qū)點P放在中間。然后使用相同的方法將小于等于分區(qū)點P的數(shù)劃分成三部分,將大于分區(qū)點P的數(shù)分成三部分。依次類推,直到數(shù)組不可再分,則整個數(shù)組實現(xiàn)有序。因此,快速排序用到的思想為分治,具體實現(xiàn)方式為遞歸。
動態(tài)圖解(該圖解是將最后一個數(shù)最為分區(qū)點,借助這個圖也可以理解將隨機(jī)選取的數(shù)作為分區(qū)點):
與歸并排序一樣,理解了原理之后,還有一個問題沒有解決:如何根據(jù)隨機(jī)選取的數(shù)來分區(qū)(partition)?答案是借助指針來分界。我們設(shè)置兩個指針,指針small為小于等于分區(qū)點P的數(shù)邊界,指針P為
8 計數(shù)排序
思路:
- 遍歷待排序數(shù)組A,找出其最小值min和最大值max;
- 創(chuàng)建一個長度為max-min+1的數(shù)組B,其所有元素初始化為0,數(shù)組首位對應(yīng)數(shù)組A的min元素,索引為i位置對應(yīng)A中值為min+i的元素;
- 遍歷數(shù)組A,在B中對應(yīng)位置記錄A中各元素出現(xiàn)的次數(shù);
- 遍歷數(shù)組B,按照之前記錄的出現(xiàn)次數(shù),輸出幾次對應(yīng)元素;
穩(wěn)定性解釋: 穩(wěn)定排序算法;
代碼:
// 計數(shù)排序 void count_Sort(vector<int>& array) { if (array.empty()){ return; } //找出最大最小值 int min = array.front(),max = array.front(); for (int i = 1; i < array.size(); i++) { if (min > array[i]) { min = array[i]; } else if (max < array[i]) { max = array[i]; } } // 記錄各元素出現(xiàn)次數(shù) vector<int> counts(max - min + 1); for (int i = 0; i < array.size(); i++) { counts[array[i] - min]++; } // 根據(jù)記錄的次數(shù)輸出對應(yīng)元素 int index = 0; for (int j = 0; j < counts.size(); j++) { int n = counts[j]; while (n--){ array[index] = j + min; index++; } } }
9 桶排序
思路:
- 設(shè)置固定數(shù)量的空桶;
- 找出待排序數(shù)組的最大值和最小值;
- 根據(jù)最大最小值平均劃分各桶對應(yīng)的范圍,并將待排序數(shù)組放入對應(yīng)桶中;
- 為每個不為空的桶中數(shù)據(jù)進(jìn)行排序(例如,插入排序);
- 拼接不為空的桶中數(shù)據(jù),得到排序后的結(jié)果。
穩(wěn)定性解釋: 常見排序算法中最快的一種穩(wěn)定算法;可以計算大批量數(shù)據(jù),符合線性期望時間;外部排序方式,需額外耗費n個空間;
代碼:
// 桶排序 void bucketSort (vector<int>& array, int bucketCount) { if (array.empty()) { return; } // 找出最大最小值 int max = array.front(), min = array.front(); for (int i = 1; i < array.size(); i++) { if (min > array[i]) { min = array[i]; } else if (max < array[i]) { max = array[i]; } } // 將待排序的各元素分入對應(yīng)桶中 vector<vector<int>> buckets(bucketCount); int bucketSize = ceil((double)(max - min + 1) / bucketCount); for (int i = 0; i < array.size(); i++) { int bucketIndex = (array[i] - min) / bucketSize; buckets[bucketIndex].push_back(array[i]); } // 對各桶中元素進(jìn)行選擇排序 int index = 0; for (vector<int> bucket : buckets) { if (!bucket.empty()) { // 使用選擇排序算法對桶內(nèi)元素進(jìn)行排序 selectSort(bucket); for (int value : bucket) { array[index] = value; index++; } } } } // 桶排序 void bucketSort (vector<int>& array) { bucketSort (array, array.size() / 2); }
10 基數(shù)排序
思路: 將各待比較元素數(shù)值統(tǒng)一數(shù)位長度,即對數(shù)位短者在前補零;根據(jù)個位數(shù)值大小,對數(shù)組進(jìn)行排序;重復(fù)上一步驟,依次根據(jù)更高位數(shù)值進(jìn)行排序,直至到達(dá)最高位;
穩(wěn)定性解釋: 穩(wěn)定算法;適用于正整數(shù)數(shù)據(jù)(若包含負(fù)數(shù),那么需要額外分開處理);對于實數(shù),需指定精度,才可使用此算法。
代碼:
// 基數(shù)排序,對array的left到right區(qū)段,按照curDigit位進(jìn)行排序 void radixSortImprove(vector<int>& array, int left, int right, int curDigit) { if (left >= right || curDigit < 10) { return; } // 將各元素按當(dāng)前位數(shù)值大小分入各桶 vector<vector<int>> buckets(10); for (int i = left; i <= right; i++) { int bucketIndex = (array[i] % curDigit - array[i] % (curDigit / 10)) / (curDigit / 10); buckets[bucketIndex].push_back(array[i]); } // 按照桶的順序,將桶中元素拼接 // 對于元素個數(shù)大于1的桶,桶內(nèi)元素按照更低位來進(jìn)行排序 int index = 0; for (vector<int> bucket : buckets) { int newLeft = index, newRight = index; for (int value : bucket) { array[index] = value; index++; } newRight = index - 1; radixSortImprove(array, newLeft, newRight, curDigit / 10); } } // 基數(shù)排序(從高位開始) void radix_Sort(vector<int>& v) { // 計算當(dāng)前數(shù)組最大數(shù)位數(shù) int curDigit = 10; for (autovalue : v) { if (value / curDigit) { curDigit *= 10; } } radixSortImprove(array, 0, array.size() - 1, curDigit); }
總結(jié)
到此這篇關(guān)于C++實現(xiàn)十大排序算法及排序算法常見問題的文章就介紹到這了,更多相關(guān)C++十大排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
有關(guān)C++中隨機(jī)函數(shù)rand() 和srand() 的用法詳解
下面小編就為大家?guī)硪黄嘘P(guān)C++中隨機(jī)函數(shù)rand() 和srand() 的用法詳解。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-01-01C語言數(shù)據(jù)結(jié)構(gòu)之單向鏈表詳解分析
鏈表可以說是一種最為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)了,而單向鏈表更是基礎(chǔ)中的基礎(chǔ)。鏈表是由一組元素以特定的順序組合或鏈接在一起的,不同元素之間在邏輯上相鄰,但是在物理上并不一定相鄰。在維護(hù)一組數(shù)據(jù)集合時,就可以使用鏈表,這一點和數(shù)組很相似2021-11-11Opencv3.4.0實現(xiàn)視頻中的幀保存為圖片功能
這篇文章主要為大家詳細(xì)介紹了Opencv3.4.0實現(xiàn)視頻中的幀保存為圖片功能,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2019-05-05C數(shù)據(jù)結(jié)構(gòu)之雙鏈表詳細(xì)示例分析
以下是對c語言中的雙鏈表進(jìn)行了詳細(xì)的分析介紹,需要的朋友可以過來參考下2013-08-08馬爾可夫鏈算法(markov算法)的awk、C++、C語言實現(xiàn)代碼
這篇文章主要介紹了馬爾可夫鏈算法(markov算法)的awk、C++、C語言實現(xiàn)代碼,需要的朋友可以參考下2014-08-08