柚子快報邀請碼778899分享：c語言 常用排序算法（下）

http://yzkb.51969.com/

目錄

2.5 冒泡排序

2.6 快速排序

2.6 1 快速排序思路

詳細(xì)步驟

2.6 2 快速排序遞歸實(shí)現(xiàn)?

2.6 3快速排序非遞歸：

快排非遞歸的優(yōu)勢

?非遞歸思路

1. 初始化棧

2. 將整個數(shù)組的起始和結(jié)束索引入棧

3. 循環(huán)處理?xiàng)Ｖ械淖訑?shù)組邊界

4. 單趟排序

5. 處理分區(qū)后的子數(shù)組

6. 重復(fù)步驟3和步驟5

注意事項(xiàng)

2.7 歸并排序

基本思想：

一、算法步驟

二、具體實(shí)現(xiàn)

歸并排序遞歸實(shí)現(xiàn)：

歸并排序非遞歸實(shí)現(xiàn)：?

三、性能分析

2.8 計(jì)數(shù)排序

計(jì)數(shù)排序概念：

一、計(jì)數(shù)排序的原理與步驟

二、計(jì)數(shù)排序的示例

?計(jì)數(shù)排序代碼實(shí)現(xiàn)：

三、注意事項(xiàng)

四、計(jì)數(shù)排序的特點(diǎn)

2.5 冒泡排序

? ?基本思路：

? ??冒泡排序的基本思路是通過重復(fù)遍歷待排序的數(shù)列，比較每對相鄰元素的值，若發(fā)現(xiàn)順序錯誤則交換它們的位置。這個過程重復(fù)進(jìn)行，直到?jīng)]有需要交換的元素為止，此時數(shù)列就完成了排序。冒泡排序的名字是因?yàn)檩^小的元素會逐漸“冒泡”到數(shù)列的頂端，即前面，而較大的元素則會沉到數(shù)列的底部，即后面。 冒泡排序的基本步驟如下： （1）比較相鄰的元素。如果第一個比第二個大，就交換它們兩個。 （2）對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。 （3）針對所有的元素重復(fù)以上的步驟，除了最后一個。 （4)持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。 冒泡排序的時間復(fù)雜度在最壞情況下是O(n^2)，其中n是數(shù)列的長度。盡管冒泡排序不是最高效的排序算法，但它的實(shí)現(xiàn)簡單，對于小數(shù)據(jù)量的排序問題還是相當(dāng)實(shí)用的。

? 動圖展示：

代碼實(shí)現(xiàn)：

void BubbleSort(int* a, int n)

{

for (int i = 1; i < n-1; i++)

{

int flag = 0;

for (int j = 0; j < n - i ; j++)

{

if (a[j] > a[j + 1])

{

Swap(&a[j], &a[j + 1]);

flag = 1;

}

}

if (flag == 0)

{

break;

}

}

}

?問：程序中的flag的作用是什么？

答：冒泡排序時間復(fù)雜度是O（N^2），但是這個時間復(fù)雜度是由這個算法的最壞情況決定的，也就是當(dāng)我們要排升序時，我們給了一個降序的數(shù)組，這時這個程序的時間復(fù)雜度就是O（N^2），而在這個組相對有序的情況下 ，我們可以使用一些手段來提高這個算法的效率，而這個flag就是我們優(yōu)化這個算法的關(guān)鍵。

? ?我們知道，如果一個相對有序甚至有序組因該是比無序的數(shù)組排序的速度更快的，但是，我們需要判斷何時有序，像這個程序中我們使用了兩個for循環(huán)，如果不判斷何時有序然后結(jié)束程序的話，它就會完完整整地將這兩個循環(huán)走完，也就是說，無論是有序還是無序的一組數(shù)來排序它的時間復(fù)雜度都是O（N^2）。這時我們就可以定義一個flag變量，將它初始化為0，如果里面有數(shù)排序了，說明這個數(shù)組是無序的，將flag置為1，下一次循環(huán)又將flag置為0，我們在下面判斷，如果flag為0的話，就說明這個數(shù)組沒有元素交換過，也就是說這個數(shù)組是有序的，既然它是有序的，我們就馬上結(jié)束這個程序，這樣優(yōu)化我們的冒泡排序就不會每次進(jìn)入它的時間復(fù)雜度都是O(N^2）了，如果這個數(shù)組是有序的，那么只會遍歷一遍數(shù)組就結(jié)束程序，此時它的速度是0(N)。

2.6 快速排序

? ? 快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。

2.6 1 快速排序思路

快速排序（Quick Sort）是一種高效的排序算法，它使用分治策略來對一個數(shù)組進(jìn)行排序。以下是快速排序的基本思路：

選擇基準(zhǔn)： 從數(shù)組中選擇一個元素作為基準(zhǔn)（key）。這個基準(zhǔn)可以是數(shù)組中的第一個元素、最后一個元素、中間元素，或者通過某種方式隨機(jī)選擇的元素。 分區(qū)： 重新排列數(shù)組，使得所有小于基準(zhǔn)的元素都位于基準(zhǔn)的左側(cè)，所有大于基準(zhǔn)的元素都位于基準(zhǔn)的右側(cè)。這個操作稱為分區(qū)（partition）。 遞歸排序： 對基準(zhǔn)左側(cè)和右側(cè)的子數(shù)組分別進(jìn)行快速排序。這是一個遞歸的過程，直到子數(shù)組的大小為零或一（此時子數(shù)組已經(jīng)是有序的）。 合并： 由于快速排序是原地排序，且通過遞歸已經(jīng)保證了每個子數(shù)組的有序性，所以最終整個數(shù)組也會是有序的，不需要額外的合并步驟。

詳細(xì)步驟

初始化：

設(shè)定數(shù)組的起始位置?left和結(jié)束位置?right。 選擇基準(zhǔn)：

選擇數(shù)組中的一個元素作為基準(zhǔn)，通常選擇?array[right]（也可以選擇其他元素）。 分區(qū)：

初始化一個指針?i，使其指向數(shù)組的起始位置?low。遍歷數(shù)組，從?left?到?right-1：

如果?array[i] <= key，則繼續(xù)向右移動?i。如果?array[i] > key，則交換?array[i]?和?array[righth-1]（或者任何一個大于key?的未處理元素的位置），并將?right-1?向左移動一位（因?yàn)樵撐恢靡呀?jīng)處理過）。最后，將基準(zhǔn)元素key?放到正確的位置上，即?array[i]?和?array[right]?之間（通常是通過交換?array[i]?和?array[right]?來完成）。 遞歸排序：

對基準(zhǔn)左側(cè)的子數(shù)組（left到?i-1）進(jìn)行快速排序。對基準(zhǔn)右側(cè)的子數(shù)組（i+1?到?right）進(jìn)行快速排序。 結(jié)束條件：

當(dāng)子數(shù)組的大小為零或一時，遞歸結(jié)束，數(shù)組已經(jīng)有序。

2.6 2 快速排序遞歸實(shí)現(xiàn)?

? 到現(xiàn)在為止，我們已經(jīng)了解了快速排序的大致思路，先來看遞歸實(shí)現(xiàn)的快速排序：

void Swap(int* p1, int* p2)

{

int tmp = *p1;

*p1 = *p2;

*p2 = tmp;

}

int GetMiddle(int* a, int left, int right)

{

int mid = left + right + 1;

if (a[left] < a[mid])

{

if (a[right] > a[mid])

{

return mid;

}

else if (a[right] > a[left])

{

return right;

}

else

{

return left;

}

}

else //a[left]>a[mid]

{

if (a[right] > a[left])

{

return left;

}

else if (a[right] > a[mid])

{

return right;

}

else

{

return mid;

}

}

}

void QuickSort(int* a, int left, int right)

{

if (left >= right)

{

return;

}

//當(dāng)left大于或等于right時，說明數(shù)組已經(jīng)有序

if ((left + right + 1) < 10)

{

InsertSort(a + left, left + right + 1);

//假設(shè)快排遞歸將被排序數(shù)組分散成了

//一棵二叉樹，我們知道二叉樹的最后一層

//占了這棵樹的大半結(jié)點(diǎn)，當(dāng)左右加起來

//的數(shù)據(jù)少于10時，我們可以使用

//插入排序提高它的效率

}

else

{

//三數(shù)取中

int mid = GetMiddle(a, left, right);

Swap(&a[left], &a[mid]);

int keyi = left;

int begin = left, end = right;

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[keyi], &a[begin]);

keyi = begin;

QuickSort(a, left, keyi - 1);

QuickSort(a, keyi + 1, right);

}

}

使用一組無序的數(shù)來測試一下：

int a[] = { 3,5,8,6,9,7,4,1,2,0,10 };

注意：此程序中的插入排序和三數(shù)取中算法都是為了優(yōu)化快速排序，使它擁有更好的效率，快速排序的核心邏輯代碼為：

void Swap(int* p1, int* p2)

{

int tmp = *p1;

*p1 = *p2;

*p2 = tmp;

}

void QuickSort(int* a, int left, int right)

{

if (left >= right)

{

return;

}

//當(dāng)left大于或等于right時，說明數(shù)組已經(jīng)有序

int keyi = left;

int begin = left, end = right;

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[keyi], &a[begin]);

keyi = begin;

QuickSort(a, left, keyi - 1);

QuickSort(a, keyi + 1, right);

}

2.6 3快速排序非遞歸：

? 看到這里，小伙伴們不禁疑惑：我們既然可以使用遞歸實(shí)現(xiàn)快速排序，為什么還要使用非遞歸實(shí)現(xiàn)呢？

快排非遞歸的優(yōu)勢

快速排序非遞歸實(shí)現(xiàn)的重要性主要體現(xiàn)在以下幾個方面：

避免遞歸調(diào)用開銷：遞歸實(shí)現(xiàn)雖然直觀易懂，但在一些編程語言中，遞歸調(diào)用會引入額外的函數(shù)調(diào)用棧的使用和維護(hù)開銷。非遞歸實(shí)現(xiàn)通過顯式地使用棧來管理狀態(tài)，可以有效避免這些開銷，從而提高性能。 防止棧溢出：在極端情況下，遞歸實(shí)現(xiàn)可能導(dǎo)致棧溢出，尤其是在處理大規(guī)模數(shù)據(jù)時。非遞歸實(shí)現(xiàn)使用顯式的數(shù)據(jù)結(jié)構(gòu)（如棧）來管理狀態(tài)，不依賴于系統(tǒng)的調(diào)用棧，從而避免了棧溢出的風(fēng)險。 降低空間復(fù)雜度：遞歸實(shí)現(xiàn)可能需要更多的內(nèi)存空間，因?yàn)槊總€遞歸調(diào)用都需要在內(nèi)存中保留一些信息。非遞歸實(shí)現(xiàn)通常使用更少的內(nèi)存，只需維護(hù)一些必要的狀態(tài)信息，有助于減少內(nèi)存使用。 提升性能：在某些編程語言和環(huán)境中，遞歸調(diào)用的性能可能不如循環(huán)，因?yàn)槊總€遞歸調(diào)用都需要函數(shù)調(diào)用的開銷。非遞歸實(shí)現(xiàn)可以更好地與一些編譯器和優(yōu)化器協(xié)同工作，從而提高性能。 便于優(yōu)化：非遞歸實(shí)現(xiàn)更容易進(jìn)行一些優(yōu)化，例如通過使用迭代而不是遞歸的方式來訪問數(shù)組，以更好地利用CPU緩存。這種優(yōu)化可以進(jìn)一步提升算法的執(zhí)行效率。 適應(yīng)特定場景：在一些對遞歸深度有限制的環(huán)境（如嵌入式系統(tǒng)）中，非遞歸實(shí)現(xiàn)是必須的，以確保算法能夠正常運(yùn)行。

?非遞歸思路

快速排序的非遞歸思路主要是通過手動管理一個棧來模擬遞歸過程中的函數(shù)調(diào)用棧，從而實(shí)現(xiàn)對數(shù)組的排序。以下是快速排序非遞歸思路的詳細(xì)步驟：

1. 初始化棧

創(chuàng)建一個空棧，用于保存接下來需要排序的子數(shù)組的邊界。這個?？梢允侨我忸愋偷臈＝Y(jié)構(gòu)，但通常使用整型棧來保存子數(shù)組的起始索引（left）和結(jié)束索引（right）。

2. 將整個數(shù)組的起始和結(jié)束索引入棧

這一步相當(dāng)于遞歸排序中的初始調(diào)用。將數(shù)組的起始索引（left）和結(jié)束索引（right）作為一對入棧，表示接下來需要處理整個數(shù)組。

3. 循環(huán)處理?xiàng)Ｖ械淖訑?shù)組邊界

不斷從棧中彈出子數(shù)組的邊界索引（一對），然后對這個子數(shù)組進(jìn)行快速排序的單趟排序。

4. 單趟排序

在單趟排序中，首先選擇一個元素作為基準(zhǔn)（pivot）?；鶞?zhǔn)的選擇可以是子數(shù)組的第一個元素，也可以通過其他策略（如三數(shù)取中法）來選擇。進(jìn)行分區(qū)操作，將子數(shù)組劃分為比基準(zhǔn)小的左側(cè)部分和比基準(zhǔn)大的右側(cè)部分，并確定基準(zhǔn)元素的最終位置。

5. 處理分區(qū)后的子數(shù)組

分區(qū)操作完成后，基準(zhǔn)元素左側(cè)的子數(shù)組（如果存在）和右側(cè)的子數(shù)組（如果存在）可能還需要繼續(xù)排序。如果左側(cè)子數(shù)組有多個元素，則將其起始和結(jié)束索引作為一對入棧。如果右側(cè)子數(shù)組有多個元素，也將其起始和結(jié)束索引作為一對入棧。

6. 重復(fù)步驟3和步驟5

繼續(xù)迭代該過程，直到棧為空。此時，所有的子數(shù)組都已經(jīng)被正確排序，整個數(shù)組也就完成了排序。

注意事項(xiàng)

在單趟排序中，分區(qū)操作是關(guān)鍵步驟，它決定了基準(zhǔn)元素的最終位置，并將數(shù)組劃分為兩個子數(shù)組。棧的使用是非遞歸快速排序的核心，它模擬了遞歸調(diào)用棧的功能，允許我們手動管理子數(shù)組的排序順序。非遞歸快速排序的性能與遞歸快速排序相近，但在某些情況下（如遞歸深度過大導(dǎo)致棧溢出）可能更加穩(wěn)定可靠。

總結(jié)：通過以上步驟，我們可以實(shí)現(xiàn)快速排序的非遞歸版本，從而在處理大規(guī)模數(shù)據(jù)時避免遞歸調(diào)用棧的限制。

由于c語言沒有STL，我們使用c＋＋來實(shí)現(xiàn)：

int GetMiddle(int* a, int left, int right)

{

int mid = left + right + 1;

if (a[left] < a[mid])

{

if (a[right] > a[mid])

{

return mid;

}

else if (a[right] > a[left])

{

return right;

}

else

{

return left;

}

}

else //a[left]>a[mid]

{

if (a[right] > a[left])

{

return left;

}

else if (a[right] > a[mid])

{

return right;

}

else

{

return mid;

}

}

}

int PartSort1(int* a, int left, int right)

{

// 三數(shù)取中

int midi = GetMiddle(a, left, right);

Swap(&a[left], &a[midi]);

int keyi = left;

int begin = left, end = right;

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[keyi], &a[begin]);

return begin;

}

//非遞歸

void QuickSortNonR(int* a, int left, int right)

{

stack st;

st.push(right);

st.push(left);

while (!st.empty())

{

int begin = st.top();

st.pop();

int end = st.top();

st.pop();

int keyi = PartSort1(a, begin, end);

if (keyi+1 < end)

{

st.push(end);

st.push(keyi+1);

}

if (begin < keyi - 1)

{

st.push(keyi - 1);

st.push(begin);

}

}

}

我們來測試一下：

可以看到我們的快排非遞歸也是成功地實(shí)現(xiàn)了。

快速排序的特性總結(jié)：

1. 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序 2. 時間復(fù)雜度：O(N*logN)

3. 空間復(fù)雜度：O(logN) 4. 穩(wěn)定性：不穩(wěn)定?

總結(jié)：快速排序是一種非常高效的排序算法，尤其適用于大部分元素已經(jīng)有序的情況。通過合理選擇基準(zhǔn)和優(yōu)化遞歸過程，可以進(jìn)一步提高其性能。

2.7 歸并排序

基本思想：

? ?歸并排序（Merge Sort）是一種分治策略的排序算法，其基本思想是將一個序列分為兩個較小的子序列，直到子序列的大小為1，然后將已排序的子序列合并成一個大的有序序列。以下是歸并排序的完整思路：

一、算法步驟

分割：

將待排序的數(shù)組分成兩半，如果數(shù)組長度為奇數(shù)，則其中一部分會比另一部分多一個元素。對這兩部分?jǐn)?shù)組繼續(xù)遞歸地進(jìn)行分割，直到子數(shù)組的長度為1，此時可以認(rèn)為每個子數(shù)組都是有序的（因?yàn)橹挥幸粋€元素）。 治理（解決）：

這一步在歸并排序中實(shí)際上是通過分割步驟隱含完成的。當(dāng)子數(shù)組的長度為1時，它們自然就是有序的，無需進(jìn)一步處理。 合并：

將相鄰的有序子數(shù)組合并成一個有序數(shù)組，直到合并為1個完整的數(shù)組。合并過程中，通過比較兩個子數(shù)組的元素，按大小順序依次放入新的數(shù)組中，從而實(shí)現(xiàn)排序。

二、具體實(shí)現(xiàn)

申請空間：

創(chuàng)建一個臨時數(shù)組，用于存放合并后的子數(shù)組。 設(shè)定指針：

在兩個待合并的子數(shù)組上分別設(shè)置指針，初始時都指向子數(shù)組的起始位置。 比較合并：

比較兩個指針?biāo)赶虻脑?，將較小的元素放入臨時數(shù)組，并移動該指針。重復(fù)此過程，直到某個子數(shù)組的所有元素都被復(fù)制到臨時數(shù)組中。將另一個子數(shù)組中剩余的元素（如果有的話）直接復(fù)制到臨時數(shù)組的末尾。 復(fù)制回原數(shù)組：

將臨時數(shù)組中的元素復(fù)制回原數(shù)組，以替換原來的子數(shù)組。

歸并排序遞歸實(shí)現(xiàn)：

void _MergeSort(int* a, int* tmp,int begin,int end)

{

if (begin >= end)

{

return;

}

int mid = (begin + end) / 2;

_MergeSort(a, tmp, begin, mid);

_MergeSort(a, tmp, mid+1, end);

int begin1 = begin, end1 = mid;

int begin2 = mid+1, end2 = end;

int i = begin;

while (begin1 <= end1 && begin2 <= end2)

{

if(a[begin1] < a[begin2])

{

tmp[i++] = a[begin1++];

}

else

{

tmp[i++] = a[begin2++];

}

}

while (begin1 <= end1)

{

tmp[i++] = a[begin1++];

}

while (begin2 <= end2)

{

tmp[i++] = a[begin2++];

}

memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));

}

void MergeSort(int* a, int n)

{

int* tmp = (int*)malloc(sizeof(int) * n);

if (tmp == NULL)

{

perror("malloc fail");

}

_MergeSort(a, tmp, 0, n - 1);

free(tmp);

tmp = NULL;

}

此程序涉及在堆上申請資源，所以我們分兩個接口實(shí)現(xiàn)。

歸并排序非遞歸實(shí)現(xiàn)：?

//歸并排序非遞歸

void MergeSortNonR(int* a, int n)

{

int* tmp = (int*)malloc(sizeof(int) * (n+1));

if (tmp == NULL)

{

perror("malloc fail");

return;

}

int gap = 1;

while (gap <= n)

{

for (int j = 0; j <= n;j+=gap*2)

{

int begin1 = j, end1 = j + gap - 1;

int begin2 = j + gap, end2 = j + gap * 2 - 1;

if (begin2 > n )

{

break;

}

if (end2 > n)

{

end2 = n;

}

int i = j;

while (begin1 <= end1 && begin2 <= end2)

{

if (a[begin1] < a[begin2])

{

tmp[i++] = a[begin1++];

}

else

{

tmp[i++] = a[begin2++];

}

}

while (begin1 <= end1)

{

tmp[i++] = a[begin1++];

}

while (begin2 <= end2)

{

tmp[i++] = a[begin2++];

}

memcpy(a + j, tmp + j, sizeof(int) * (end2 - j+1));

}

gap *= 2;

}

free(tmp);

tmp == NULL;

}

給一組無序數(shù)，我們來測試一下：

int a[] = { 3,5,7,1,2,0,9,10,4,8,11 };

?

可以看到?jīng)]有什么問題。

?

三、性能分析

時間復(fù)雜度：歸并排序的時間復(fù)雜度為O(n log n)，其中n是數(shù)組的長度。在每一層遞歸中，合并操作的時間復(fù)雜度為O(n)，而遞歸的層數(shù)為log n，因此總的時間復(fù)雜度為O(n log n)?？臻g復(fù)雜度：歸并排序的空間復(fù)雜度也是O(n)，因?yàn)樾枰~外的空間來創(chuàng)建臨時數(shù)組。穩(wěn)定性：歸并排序是穩(wěn)定的排序算法，即相等的元素在排序后的順序與它們在原數(shù)組中的順序相同。

總結(jié)：歸并排序因其穩(wěn)定的排序特性和較好的平均性能，在實(shí)際應(yīng)用中非常廣泛。特別是在數(shù)據(jù)量較大時，歸并排序能夠展現(xiàn)出其高效的排序能力。?

2.8 計(jì)數(shù)排序

計(jì)數(shù)排序概念：

? ? ?計(jì)數(shù)排序（Counting Sort）是一種非基于比較的排序算法，由Harold H. Seward在1954年提出。它適用于待排序元素為整數(shù)且范圍較小的情況。計(jì)數(shù)排序的基本思想是統(tǒng)計(jì)每個元素的出現(xiàn)次數(shù)，然后利用這些信息將原始序列重新組合成有序序列。

一、計(jì)數(shù)排序的原理與步驟

計(jì)數(shù)排序的工作原理主要包括以下幾個步驟：

統(tǒng)計(jì)元素出現(xiàn)次數(shù)：

遍歷待排序的數(shù)組，統(tǒng)計(jì)每個元素出現(xiàn)的次數(shù)。這通常通過創(chuàng)建一個輔助數(shù)組（計(jì)數(shù)數(shù)組）來實(shí)現(xiàn)，該數(shù)組的長度等于待排序數(shù)組中元素的最大值加1（如果元素是非負(fù)整數(shù)）。 前綴和操作：

對計(jì)數(shù)數(shù)組進(jìn)行前綴和操作，使得每個元素的值變?yōu)樾∮诘扔谠撛氐闹档脑乜倲?shù)。這樣，計(jì)數(shù)數(shù)組的每個位置就對應(yīng)了原數(shù)組中元素在排序后數(shù)組中的位置。 重建有序數(shù)組：

遍歷待排序數(shù)組，根據(jù)計(jì)數(shù)數(shù)組的信息，將元素放回其在有序數(shù)組中的正確位置。同時，更新計(jì)數(shù)數(shù)組中對應(yīng)元素的值，以確保相同元素的相對順序不變。

二、計(jì)數(shù)排序的示例

假設(shè)我們有一個待排序的數(shù)組arr = [4, 2, 2, 8, 3, 3, 1]，我們可以按照計(jì)數(shù)排序的步驟對其進(jìn)行排序：

統(tǒng)計(jì)元素出現(xiàn)次數(shù)：

遍歷數(shù)組arr，得到計(jì)數(shù)數(shù)組count = [0, 1, 2, 2, 2, 0, 1, 1]（假設(shè)數(shù)組中的元素都是非負(fù)整數(shù)，且最大值不超過7）。 前綴和操作：

對計(jì)數(shù)數(shù)組進(jìn)行前綴和操作，得到count = [0, 1, 3, 5, 7, 7, 7, 8]。 重建有序數(shù)組：

遍歷數(shù)組arr，根據(jù)計(jì)數(shù)數(shù)組的信息將元素放回有序數(shù)組中的正確位置。排序后的數(shù)組為sorted_arr = [1, 2, 2, 3, 3, 4, 8]。

?計(jì)數(shù)排序代碼實(shí)現(xiàn)：

void CountSort(int* a, int n)

{

int max = a[0], min = a[0];

for (int i = 0; i < n; i++)

{

if (a[i] > max)

{

max = a[i];

}

if (a[i] < min)

{

min = a[i];

}

}

int range = max - min + 1;

int* count = (int*)calloc(range, sizeof(int));

if (count == NULL)

{

perror("calloc fail");

}

for (int i = 0; i

{

count[a[i] - min]++;

}

int j = 0;

for (int i = 0; i < range; i++)

{

while (count[i]--)

{

a[j++] = i + min;

}

}

}

給一組無序數(shù)測試一下：

int a[] = { 2,4,76,87654,98,12,76,454,23,98 };

?

? ? 雖然我們的排序成功了，但是這個程序內(nèi)部開辟了非常多的空間，所以當(dāng)一組數(shù)的最大值和最小值相差太多時，不建議使用計(jì)數(shù)排序。

三、注意事項(xiàng)

在使用計(jì)數(shù)排序時，需要確保待排序數(shù)組中的元素都是非負(fù)整數(shù)或可映射到非負(fù)整數(shù)范圍內(nèi)。如果待排序的元素不滿足這個要求，就需要對其進(jìn)行映射轉(zhuǎn)換。當(dāng)待排序元素的范圍非常大時，計(jì)數(shù)排序可能會消耗大量的內(nèi)存空間，因此在實(shí)際應(yīng)用中需要注意這一點(diǎn)。

四、計(jì)數(shù)排序的特點(diǎn)

時間復(fù)雜度：

計(jì)數(shù)排序的時間復(fù)雜度為O(n+k)，其中n是待排序數(shù)組的長度，k是待排序數(shù)組中元素的范圍。當(dāng)k不是很大時，計(jì)數(shù)排序的時間復(fù)雜度接近線性，快于任何基于比較的排序算法（如快速排序、歸并排序等，它們的時間復(fù)雜度在理論上的下限是O(n log n)）。 空間復(fù)雜度：

計(jì)數(shù)排序的空間復(fù)雜度為O(k)，其中k是待排序數(shù)組中元素的范圍。因此，計(jì)數(shù)排序是一種犧牲空間換取時間的排序算法。 穩(wěn)定性：

計(jì)數(shù)排序是穩(wěn)定的排序算法，即相等的元素在排序后的序列中保持它們原有的先后順序。 適用場景：

計(jì)數(shù)排序特別適用于整數(shù)排序，特別是當(dāng)整數(shù)的范圍不是很大時。對于非整數(shù)類型的數(shù)據(jù)或整數(shù)范圍非常大的情況，計(jì)數(shù)排序可能不適用或效率較低。

?本章完。

柚子快報邀請碼778899分享：c語言 常用排序算法（下）

http://yzkb.51969.com/

相關(guān)閱讀