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)選擇不同的方法依次對未排序的部分進行排序。
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ù)組各自進行比較，比較好后，每個子數(shù)組都有順序，進入下一輪，步長(間隔)減少，再根據(jù)步長(間隔)分組進行比較;
3) 重復(fù)以上操作，最后就有序了。
圖解：
代碼：
#include <iostream>
#include <vector>
using namespace std;
//希爾排序
void shellSort(vector<int> &vec){
int len = vec.size();
if (len <= 1) return;
//以h為步長劃分數(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ù)組中的某個指針到達邊界，然后將未到達邊界的數(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++];
}
//將未到達邊界的數(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é)點。將其與末尾元素進行交換，此時末尾就為最大值。然后將剩余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ū)點，借助這個圖也可以理解將隨機選取的數(shù)作為分區(qū)點）：
與歸并排序一樣，理解了原理之后，還有一個問題沒有解決：如何根據(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ù)進行排序（例如，插入排序）；
- 拼接不為空的桶中數(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]);
}
// 對各桶中元素進行選擇排序
int index = 0;
for (vector<int> bucket : buckets)
{
if (!bucket.empty())
{
// 使用選擇排序算法對桶內(nèi)元素進行排序
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ù)組進行排序；重復(fù)上一步驟，依次根據(jù)更高位數(shù)值進行排序，直至到達最高位；
穩(wěn)定性解釋： 穩(wěn)定算法；適用于正整數(shù)數(shù)據(jù)（若包含負數(shù)，那么需要額外分開處理)；對于實數(shù)，需指定精度，才可使用此算法。
代碼：
// 基數(shù)排序，對array的left到right區(qū)段，按照curDigit位進行排序
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)元素按照更低位來進行排序
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)文章
OpenCV邊緣提取算法流程的實現(xiàn)(附DEMO)
本文主要介紹了OpenCV邊緣提取算法流程的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-08-08
這篇文章主要介紹了一些語言的按行讀取文件的代碼實現(xiàn)小結(jié),這里羅列了Java和C語言和C++以及PHP的實現(xiàn)需要的朋友可以參考下2015-08-08
Capstone的編譯非常簡單只需要一步即可輕松得到對應(yīng)的Lib庫文件，如下將介紹該引擎如何被編譯，以及簡單的測試編譯，這篇文章主要介紹了C/C++?Capstone?引擎源碼編譯,需要的朋友可以參考下2022-09-09
這篇文章主要介紹了C語言文件復(fù)制實例詳解的相關(guān)資料,需要的朋友可以參考下2017-06-06
VS2010+Opencv+MFC讀取圖像和視頻顯示在Picture控件
這篇文章主要為大家詳細介紹了VS2010+Opencv+MFC讀取圖像和視頻顯示在Picture控件，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-08-08
這篇文章主要為大家詳細介紹了C語言編寫一個鏈表，文中安裝步驟介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-05-05
這篇文章介紹了C++ Prim算法、優(yōu)先隊列，文中通過示例代碼介紹的非常詳細。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-06-06
c語言的經(jīng)典程序，學(xué)習(xí)c語言的初學(xué)者可以參考下2013-01-01
本文主要介紹了C語言實現(xiàn)可排序通訊錄的示例代碼，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
本篇文章是對c語言中printf函數(shù)的使用進行了詳細的分析介紹，需要的朋友參考下2013-05-05