一.前言
在計(jì)算機(jī)科學(xué)中，排序算法是最重要的算法之一。排序算法可以將一組無(wú)序的數(shù)據(jù)按照一定的規(guī)則重新排列，使其變?yōu)橛行虻臄?shù)據(jù)集合。排序算法的應(yīng)用十分廣泛，它們?cè)谟?jì)算機(jī)科學(xué)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫(kù)、人工智能、機(jī)器學(xué)習(xí)等領(lǐng)域都扮演著重要的角色。
本文將介紹C++/C語(yǔ)言中的八大排序算法，包括冒泡排序、選擇排序、插入排序、希爾排序、歸并排序、快速排序、堆排序、計(jì)數(shù)排序。這些排序算法各有優(yōu)缺點(diǎn)，選擇合適的算法可以?xún)?yōu)化程序效率，提升算法的性能。本文將對(duì)這些算法進(jìn)行詳細(xì)的介紹，希望讀者可以通過(guò)閱讀本文對(duì)排序算法有更深入的理解，同時(shí)對(duì)C++語(yǔ)言的使用也會(huì)有更加熟練的掌握。
二、排序的分類(lèi)
插入排序：直接插入排序，希爾排序
選擇排序：選擇排序，堆排序
交換排序：冒泡排序，堆排序
歸并排序，計(jì)數(shù)排序
三、排序?qū)崿F(xiàn)
1.直接插入排序
（1）基本思想
將數(shù)據(jù)分為兩部分，前部分為已排好數(shù)據(jù)，后一部分是待排數(shù)據(jù)，將后部分的數(shù)據(jù)逐個(gè)與前面比較大小并進(jìn)行插入，直到所有的數(shù)據(jù)插入完 為止，以此得到一個(gè)有序序列。
（2）基于上述，可以設(shè)置一個(gè)end下標(biāo)，以此分割兩部分，[0，end]為有序序列，將end+1與[0，end]逐個(gè)進(jìn)行比較，將大于end+1的數(shù)據(jù)依次往后挪動(dòng)，當(dāng)end+1小于某個(gè)數(shù)據(jù)或比下標(biāo)0的位置的小時(shí)，就插入在該數(shù)據(jù)或下標(biāo)0的位置上。
代碼部分實(shí)現(xiàn)
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; ++i)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
2.希爾排序
(1)基本思想
希爾排序是基于直接插入排序的優(yōu)化版,相比于前者，此算法多了一個(gè)gap用來(lái)分組，用來(lái)進(jìn)行的一次排序稱(chēng)為預(yù)排序，使之接近有序，以下圖片便是分組示例
1.gap越大，大的數(shù)可以越快到后面，小的數(shù)可以越快到前面， 但是gap越大,預(yù)排越不接近有序
2.gap越小，越接近有序，當(dāng)gap為1時(shí)就是直接插入排序
通常，希爾排序的間隔首先取數(shù)組長(zhǎng)度的一半，然后逐步減半，直到間隔為1。
這種選擇間隔的方式是為了在排序過(guò)程中盡可能地減少逆序?qū)Φ臄?shù)量。逆序?qū)κ侵冈跀?shù)組中，如果一個(gè)元素比它后面的元素大，那么它們就構(gòu)成一個(gè)逆序?qū)?。通過(guò)選擇較大的間隔，可以使得元素可以跳過(guò)一些位置直接交換，從而更快地消除逆序?qū)Α?br> （2）代碼實(shí)現(xiàn)
gap可以取gap/2，也可以取gap/3+1，總之要使之能到1
void ShellSort(int* a, int n)//希爾排序
{
int gap=n;
while(gap>1)
{
gap = gap / 3+1;
for (int i = 0; i <n - gap; ++i)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
3.直接選擇排序
（1）基本思想
1.首先，從待排序的序列中選擇最?。ɑ蜃畲螅┑脑?，將其與序列的第一個(gè)元素進(jìn)行交換。
2.然后，在剩余的未排序序列中選擇最小（或最大）的元素，將其與序列的第二個(gè)元素進(jìn)行交換。
重復(fù)上述步驟，直到所有元素都排序完成。
（2）代碼實(shí)現(xiàn)
void SelectSort(int* a, int n)
{
for (int i = 0; i < n- 1; i++)
{
for (int j = i + 1; j < n; j++)
{
if (a[i] > a[j])
swap(a[i],a[j]);
}
}
}
（3）代碼優(yōu)化
上述代碼是在一次循環(huán)中只找出一個(gè)，但是可以在一次循環(huán)中找出一個(gè)最大和一個(gè)最小，放入到開(kāi)頭和末尾，所以就定義兩個(gè)指針begin和end
（4）代碼實(shí)現(xiàn)
特別注意要考慮到begin和mini交換時(shí)會(huì)影響到max的位置
void SelectSort2(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin; i <= end; ++i)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
swap(a[begin], a[mini]);
if (maxi == begin)//注意
{
maxi = mini;
}
swap(a[end], a[maxi]);
++begin;
--end;
}
}
4.堆排序
（1）相關(guān)概念
在了解堆排序之前應(yīng)先了解如下知識(shí)點(diǎn)
1.堆是二叉樹(shù)按層序用數(shù)組表示，堆的邏輯結(jié)構(gòu)是一個(gè)完全二叉樹(shù)，物理結(jié)構(gòu)是一個(gè)數(shù)組
2.下標(biāo)父子節(jié)點(diǎn)
leftchild=parent2+1；
rightchild=parent2+2；
parent=(child-1)/2；
3.大堆要求：所有父親大于等于孩子，堆頂元素最大
小堆要求：父親小于等于孩子 ，堆頂元素最小
（2）基本思想
構(gòu)建最大堆（或最小堆）：將待排序的序列構(gòu)建成一個(gè)最大堆（或最小堆）。最大堆的性質(zhì)是父節(jié)點(diǎn)的值大于等于其子節(jié)點(diǎn)的值，最小堆的性質(zhì)是父節(jié)點(diǎn)的值小于等于其子節(jié)點(diǎn)的值。
排序：將堆頂元素與最后一個(gè)元素交換位置，然后對(duì)剩余的 n-1 個(gè)元素重新構(gòu)建最大堆（或最小堆）。重復(fù)這個(gè)過(guò)程，直到所有元素都被排序。
首先先建堆
（3）建（大）堆代碼實(shí)現(xiàn)
（注意要更新父子節(jié)點(diǎn)）
void AdjustDownbig(int* a, int n, int root)//左右都是大堆
{
int parent = root;
int child = parent * 2 + 1;//默認(rèn)左孩子
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
++child;
}
if (a[child] >a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
（4）最后代碼實(shí)現(xiàn)
要從最后一個(gè)父節(jié)點(diǎn)開(kāi)始建大堆
void HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDownbig(a, n, i);//建立堆
}
//排升序是建大堆，不是建小堆（沒(méi)有效率優(yōu)勢(shì)，結(jié)構(gòu)會(huì)全部被打亂）
//最大的數(shù)換到最后
int end = n - 1;
while (end > 0)
{
swap(a[0], a[end]);
AdjustDownbig(a, end, 0);
end--;
}
}
5.冒泡排序
（1）基本思想
1.從序列的第一個(gè)元素開(kāi)始，依次比較相鄰的兩個(gè)元素的大小。
2.如果前一個(gè)元素大于后一個(gè)元素，就進(jìn)行交換，使得較大的元素向后移動(dòng)。
3.繼續(xù)從第一個(gè)元素開(kāi)始，重復(fù)上述比較和交換操作，直到末尾元素。
重復(fù)以上步驟，直到所有的元素都按照從小到大的順序排列好。
（2）代碼實(shí)現(xiàn)
void BubbleSort(int* a, int n)
{
for (int j =1; j < n; ++j)
{
int exchange = 0;
for (int i = 0; i < n-j; ++i)
{
if (a[i +1] < a[i])
{
swap(a[i +1], a[i]);
exchange = 1;
}
}
if (exchange == 0)
{
break;
}
}
}
6.快速排序
1.挖坑法
（1）基本思路
1.選擇一個(gè)key（一般選擇第一個(gè)或者隨機(jī)選擇）作為參考。
2.從序列的右端開(kāi)始，定義兩個(gè)指針：begin指向左端，end指向右端。
3.不斷移動(dòng)指針end，直到找到一個(gè)比樞軸元素小的元素，停下來(lái)。
4.不斷移動(dòng)指針begin，直到找到一個(gè)比樞軸元素大的元素，停下來(lái)。
當(dāng)end和begin相遇時(shí)就停止
這樣比key小的就在其左邊，比其大的就在其右邊
（2）代碼實(shí)現(xiàn)（完整代碼在后面）
注：因?yàn)榇嬖谂既恍?，所以挖坑的?shù)采用三數(shù)取中法
三數(shù)取中法代碼如下
int GetMid(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
int PartSort1(int* a, int left, int right)
{
int begin = left, end = right;
int index = GetMid(a, left, right);
swap(a[begin], a[index]);
int pivot = begin;
int key = a[begin];
while (begin < end)
{
//右邊找小的放到左邊填坑
while (begin < end && a[end] >= key)
{
end--;
}
a[pivot] = a[end];
pivot = end;
//左邊找大的放到右邊填坑
while (begin < end && a[begin] <= key)
{
begin++;
}
a[pivot] = a[begin];
pivot = begin;
}
pivot = begin;
a[pivot] = key;
return pivot;
}
2.前后指針?lè)?/h4>
（1）基本思路
1.選擇一個(gè)keyi（一般選擇第一個(gè)或者隨機(jī)選擇）作為參考。
2.定義兩個(gè)指針，一個(gè)指向序列的頭部，稱(chēng)為前指針begin，另一個(gè)指向序列的尾部，稱(chēng)為后指針end。
3.通過(guò)移動(dòng)前指針和后指針，尋找兩個(gè)元素，使得前指針?biāo)傅脑卮笥跇休S元素，后指針?biāo)傅脑匦∮趉eyi所在的元素。
4.如果前指針?biāo)傅脑卮笥趉eyi所在的元素，并且后指針?biāo)傅脑匦∮趉eyi所在的元素，則交換這兩個(gè)元素的位置。
重復(fù)步驟3和4，直到前指針和后指針相遇
（2）代碼實(shí)現(xiàn)
nt PartSort2(int* a, int left, int right)
{
int index = GetMid(a, left, right);
swap(a[left], a[index]);
int begin = left;
int end = right;
int keyi = begin;
while (begin < end)
{
while (begin < end && a[end] >= a[keyi])
{
end--;
}
while (begin < end && a[begin] <= a[keyi])
{
begin++;
}
swap(a[begin], a[end]);
}
swap(a[begin], a[keyi]);
return begin;
}
最終代碼
把樞軸元素的左右分成兩個(gè)區(qū)間，再采用分治遞歸的方法得到最終結(jié)果
注：在分出來(lái)的區(qū)間值小于10時(shí)，可采用插入排序來(lái)提高效率
void QuickSort(int* a, int left,int right)
{
if (left >= right)
{
return;
}
int keyIndex = PartSort1(a, left, right);//可替PartSort2或PartSort3
//[left,right]
//[left,pivot-1],pivot,[pivot+1,right],分治遞歸
if (keyIndex - 1 - left > 10)
{
QuickSort(a, left, keyIndex - 1);
}
else
{
InsertSort(a + left, keyIndex - 1 - left + 1);
}
if (right-1- keyIndex > 10)
{
QuickSort(a, keyIndex + 1, right);
}
else
{
InsertSort(a+ keyIndex +1, right- keyIndex);
}
}
3.左右指針?lè)?/h4>
（1）基本思路
1.選擇一個(gè)樞軸元素（一般選擇第一個(gè)或者隨機(jī)選擇）作為參考。
2.定義一個(gè)左指針（prev），指向序列的最左端，定義一個(gè)右指針（cur），指向他的下一個(gè)
3.從右指針開(kāi)始，向右遍歷，找到比樞軸元素小的值就存到左指針?biāo)诘奈恢?，并將兩指針都往下移一?br> 4.最后prev所在的位置就是樞軸元素應(yīng)該在的下標(biāo)
（2）代碼實(shí)現(xiàn)
int PartSort3(int* a, int left, int right)
{
int index = GetMid(a, left, right);
swap(a[left], a[index]);
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi]&&++prev!=cur)
{
swap(a[prev], a[cur]);
}
cur++;
}
swap(a[keyi], a[prev]);
return prev;
}
4.非遞歸實(shí)現(xiàn)
(1)基本思路
1.首先，因?yàn)檫f歸調(diào)用的空間太多，導(dǎo)致棧溢出，內(nèi)存空間分配不夠的問(wèn)題，所以采用模擬棧的方法
2.先用partsort先確定keyi（入棧左右區(qū)間來(lái)確定left，right然后在彈出），將其分為左右兩部分區(qū)間，在對(duì)于左右兩部分開(kāi)始模擬
（2）代碼實(shí)現(xiàn)
void QuickSortNonR(int* a, int left, int right)
{
stack<int> st;
st.push(right);
st.push(left);
while (!st.empty())
{
int begin = st.top();
st.pop();
int end = st.top();
st.pop();
int keyi = PartSort3(a, begin, end);
if (left < keyi-1)
{
st.push(keyi - 1);;
st.push(left);
}
if (keyi + 1 < right)
{
st.push(right);
st.push(keyi + 1);
}
}
}
7.歸并排序
（1）基本思路
1.將待排序序列平均分成兩個(gè)子序列，分別對(duì)兩個(gè)子序列進(jìn)行遞歸排序，直到每個(gè)子序列的長(zhǎng)度變?yōu)?或?yàn)榭铡?br> 2.將排好序的子序列按照順序進(jìn)行合并，得到一個(gè)有序的序列。
（2）具體步驟
1.創(chuàng)建一個(gè)臨時(shí)數(shù)組，用來(lái)暫存合并后的結(jié)果。
2.找到位于中間的元素，將數(shù)組分為左右兩部分
3.每一部分都定義兩個(gè)指針，來(lái)指向頭和尾
4.將兩部分合并就是比較兩數(shù)組最靠前的兩個(gè)元素誰(shuí)小誰(shuí)先入數(shù)組(可參考合并鏈表)
（3）代碼實(shí)現(xiàn)
void _MergeSort(int* a, int left, int right,int* tmp)
{
if (left >= right)
{
return;
}
int mid = (left + right)>>1;
//[left,mid],[mid+1,right]
_MergeSort(a,left, mid,tmp);
_MergeSort(a,mid + 1,right, tmp);
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
for (int i = left; i <= right; ++i)
{
a[i] = tmp[i];
}
}
void MergeSort(int* a, int n)
{
int* tmp = new int[n];
_MergeSort(a, 0, n - 1, tmp);
delete[] tmp;
}
1.非遞歸實(shí)現(xiàn)
（1）基本思路
1.將待排序的序列劃分成若干個(gè)長(zhǎng)度為1的子序列。
2.創(chuàng)建一個(gè)與原始序列大小相同的輔助數(shù)組作為臨時(shí)存儲(chǔ)空間。
3.對(duì)于每個(gè)子序列，將相鄰的兩個(gè)子序列進(jìn)行合并，得到一個(gè)長(zhǎng)度為2的有序子序列。
4.按照步驟3的操作，不斷迭代地對(duì)有序子序列進(jìn)行兩兩合并，直到得到一個(gè)完全有序的序列。
5.合并的過(guò)程通過(guò)比較兩個(gè)子序列的元素，并將較小的元素放入臨時(shí)數(shù)組中，并移動(dòng)相應(yīng)的指針。
最終，將臨時(shí)數(shù)組中的元素復(fù)制回原始序列的對(duì)應(yīng)位置，完成排序。
（2）代碼實(shí)現(xiàn)
void Mergesortnonr(int* a, int left, int right, int n)//歸并排序非遞歸法
{
int* tmp = (int*)malloc(sizeof(int) * n);
int gap = 1;
while (gap < n)
{
for (int i = 0; i <= right; i = i + 2 * gap)
{
int begin1 = i, end1 = i + gap - 1, mid = i + gap - 1;
int begin2 = mid + 1, end2 = i + 2 * gap - 1;
int j = i;
if (begin2 > right) break;
if (end2 > right) end2 = right;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2]) tmp[j++] = a[begin1++];
else tmp[j++] = a[begin2++];
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
for (int j = i; j <= end2; j++)
{
a[j] = tmp[j];
}
}
gap = 2 * gap;
}
}
8.計(jì)數(shù)排序
（1）基本思想
計(jì)數(shù)排序的基本步驟如下：
1.統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)：遍歷原始數(shù)組，建立一個(gè)輔助數(shù)組count，數(shù)組的索引表示元素的值，數(shù)組的值表示該元素出現(xiàn)的次數(shù)。初始情況下，count數(shù)組的所有值都為0。
2.累加次數(shù)：對(duì)count數(shù)組做累加操作，將當(dāng)前索引位置的值與前一個(gè)索引位置的值相加，得到修改后的count數(shù)組。這個(gè)操作使得count數(shù)組的每個(gè)元素表示不大于該索引的值在原始數(shù)組中的最后一個(gè)位置。
3.排序：創(chuàng)建一個(gè)與原始數(shù)組大小相同的結(jié)果數(shù)組result。從原始數(shù)組的最后一個(gè)元素開(kāi)始遍歷，根據(jù)該元素的值，在count數(shù)組中查找對(duì)應(yīng)的位置，并將這個(gè)元素放到result數(shù)組中正確的位置上。同時(shí)更新count數(shù)組中對(duì)應(yīng)位置的值。
（該算法適用于元素都屬于一個(gè)較小范圍的整數(shù)集合時(shí)，例如排序一組學(xué)生成績(jī)、年齡等。）
（2）代碼實(shí)現(xiàn)
void CountSort(int* a, int n)
{
int maxi = a[0], mini = a[0];
for (int i = 0; i < n; ++i)
{
maxi = max(maxi, a[i]);
mini = min(mini, a[i]);
}
int range = maxi - mini + 1;//找出新建數(shù)組下標(biāo)的范圍
int* count = new int[range];
memset(count, 0, sizeof(int)*range);//重置元素值為0
for (int i = 0; i < n; ++i)
{
count[a[i] - mini]++;
}
int j = 0;
for (int i = 0; i < range; ++i)
{
while (count[i]--)
{
a[j++] = i+mini;
}
}
delete[] count;
}
四、優(yōu)劣對(duì)比及復(fù)雜度分析
1.穩(wěn)定性
穩(wěn)定性：指的是在排序過(guò)程中，如果兩個(gè)相同元素的相對(duì)順序在待排序的序列中已經(jīng)確定，那么在排序完成后，它們的相對(duì)順序仍然保持不變，則這個(gè)排序穩(wěn)定。
1.直接插入排序：在直接插入排序中，對(duì)于相等的元素，插入操作會(huì)將后面的元素依次往后移動(dòng)，為新元素騰出位置。而由于移動(dòng)的是后面的元素，相等元素的相對(duì)順序仍然保持不變，因此直接插入排序是穩(wěn)定的。
2.希爾排序：在希爾排序的過(guò)程中，由于是分了很多組，所以較大的元素可能會(huì)移動(dòng)到較小的元素的前面，破壞了相等元素之間的相對(duì)順序。因此，希爾排序是一個(gè)不穩(wěn)定的排序算法。
3.直接選擇排序：在每一次選擇最小（或最大）元素的過(guò)程中，可能會(huì)導(dǎo)致相等元素的相對(duì)順序發(fā)生改變。所以不穩(wěn)定。
4.堆排序：因?yàn)樵诖诉^(guò)程中會(huì)把頂元素移到最后一個(gè)去，所以會(huì)排到其相同元素后，所以不穩(wěn)定
5.冒泡排序：在進(jìn)行相鄰元素的比較時(shí)，如果兩個(gè)元素相等，我們不會(huì)進(jìn)行交換，從而保持了相同元素之間的相對(duì)順序不變。這種特性使得冒泡排序是一種穩(wěn)定的排序算法。
6.快速排序：在快速排序的劃分過(guò)程中，通過(guò)移動(dòng)指針，找到需要交換的元素并進(jìn)行交換。這個(gè)交換操作可能破壞相等元素的相對(duì)順序，導(dǎo)致不穩(wěn)定性。
7.歸并排序：在歸并排序的合并過(guò)程中，比較元素并進(jìn)行合并時(shí)，如果有相等的元素，我們會(huì)先將左子序列中的元素放入結(jié)果序列，這樣就保持了相等元素的相對(duì)順序，所以穩(wěn)定。
2.優(yōu)劣比較
1.直接插入排序：
優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，穩(wěn)定性好，在對(duì)小規(guī)模數(shù)據(jù)或近乎有序的數(shù)據(jù)進(jìn)行排序時(shí)表現(xiàn)良好。
（相較于冒泡和選擇： 插入排序適應(yīng)性比較強(qiáng)，再接近有序時(shí)會(huì)減少遍歷）
缺點(diǎn)：對(duì)大規(guī)模數(shù)據(jù)排序效率相對(duì)較低。
2.希爾排序：
優(yōu)點(diǎn)：對(duì)于中等大小的數(shù)據(jù)集合有較好的性能，相對(duì)于冒泡排序和插入排序有較高的效率。
缺點(diǎn)：不穩(wěn)定性，實(shí)現(xiàn)稍復(fù)雜，需要選擇合適的增量序列。
3.直接選擇排序：
優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，不占用額外的內(nèi)存空間。
缺點(diǎn)：在大規(guī)模數(shù)據(jù)排序時(shí)性能較低，不穩(wěn)定。
4.堆排序：
優(yōu)點(diǎn)：相對(duì)于其他基于比較的排序算法，堆排序性能較高，同時(shí)也是一種不穩(wěn)定的排序算法。
缺點(diǎn)：相對(duì)于其他算法，實(shí)現(xiàn)較復(fù)雜，需要了解和掌握堆的性質(zhì)和操作。
5.冒泡排序：
優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，易于理解。
缺點(diǎn)：效率較低，不穩(wěn)定。
6.快速排序：
優(yōu)點(diǎn)：平均情況下性能較好，實(shí)現(xiàn)相對(duì)簡(jiǎn)單，對(duì)大規(guī)模數(shù)據(jù)排序效率高。
缺點(diǎn)：在最壞情況下，時(shí)間復(fù)雜度可以達(dá)到O(n^2)，是一種不穩(wěn)定的排序算法。
7.歸并排序：
優(yōu)點(diǎn)：穩(wěn)定的排序算法，對(duì)大規(guī)模數(shù)據(jù)排序效率較高。
缺點(diǎn)：實(shí)現(xiàn)稍復(fù)雜，需要額外的空間來(lái)存儲(chǔ)臨時(shí)數(shù)組。
8.計(jì)數(shù)排序：
優(yōu)點(diǎn)：對(duì)于具有固定范圍的整數(shù)數(shù)據(jù)排序，具有較高的性能。
缺點(diǎn)：只能用于整數(shù)排序，不適用于其他類(lèi)型的數(shù)據(jù)；需要額外的空間來(lái)存儲(chǔ)計(jì)數(shù)數(shù)組，當(dāng)數(shù)據(jù)范圍較大時(shí)，空間消耗較高。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-694921.html
小白第一次寫(xiě)，大佬們輕點(diǎn)噴文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-694921.html
到了這里，關(guān)于c++【數(shù)據(jù)結(jié)構(gòu)】 八大排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
