原創(chuàng)不易，轉(zhuǎn)載請(qǐng)注明出處。歡迎點(diǎn)贊收藏~

計(jì)數(shù)排序（Counting Sort）是一種線性時(shí)間復(fù)雜度的排序算法，其核心思想是通過(guò)統(tǒng)計(jì)待排序元素的個(gè)數(shù)來(lái)確定元素的相對(duì)位置，從而實(shí)現(xiàn)排序。

具體的計(jì)數(shù)排序算法步驟如下：
1. 找出待排序數(shù)組中的最大值，并創(chuàng)建一個(gè)統(tǒng)計(jì)數(shù)組count[]，其長(zhǎng)度為最大值加1。
2. 遍歷待排序數(shù)組，統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)，將統(tǒng)計(jì)結(jié)果存儲(chǔ)在count[]數(shù)組中。count[i]表示元素i出現(xiàn)的次數(shù)。
3. 對(duì)count[]數(shù)組進(jìn)行累加，得到每個(gè)元素在排序后的數(shù)組中的最后一個(gè)位置。即count[i]表示小于等于元素i的元素個(gè)數(shù)。
4. 創(chuàng)建一個(gè)臨時(shí)數(shù)組temp[]，其長(zhǎng)度與待排序數(shù)組相同。
5. 逆序遍歷待排序數(shù)組，根據(jù)count[]數(shù)組中的記錄，將每個(gè)元素放入temp[]數(shù)組中的正確位置。
6. 將temp[]數(shù)組的元素復(fù)制回待排序數(shù)組，完成排序。

計(jì)數(shù)排序的時(shí)間復(fù)雜度為O(n+k)，其中n是待排序數(shù)組的長(zhǎng)度，k是待排序數(shù)組中的最大值。由于需要?jiǎng)?chuàng)建額外的count[]和temp[]數(shù)組，所以空間復(fù)雜度為O(n+k)。

需要注意的是，計(jì)數(shù)排序適用于元素范圍較小且非負(fù)整數(shù)的排序，如果待排序數(shù)組包含負(fù)數(shù)或者小數(shù)，則需要進(jìn)行適當(dāng)?shù)霓D(zhuǎn)換或調(diào)整。計(jì)數(shù)排序是穩(wěn)定的排序算法，因?yàn)橄嗤氐南鄬?duì)順序在排序后保持不變，但它不是基于比較的排序算法，因此在某些情況下比其他排序算法更高效。

下面是一個(gè)使用C語(yǔ)言實(shí)現(xiàn)的計(jì)數(shù)排序示例：

#include <stdio.h>void counting_sort(int arr[], int n)
{int max = arr[0];// 找出最大值for (int i = 1; i < n; i++){if (arr[i] > max){max = arr[i];}}// 創(chuàng)建統(tǒng)計(jì)數(shù)組count[]，并初始化為0int count[max + 1];for (int i = 0; i <= max; i++){count[i] = 0;}// 統(tǒng)計(jì)每個(gè)元素的次數(shù)for (int i = 0; i < n; i++){count[arr[i]]++;}// 累加count[]數(shù)組，表示小于等于元素i的元素個(gè)數(shù)for (int i = 1; i <= max; i++){count[i] += count[i - 1];}// 創(chuàng)建臨時(shí)數(shù)組temp[]，存儲(chǔ)排好序的元素int temp[n];// 根據(jù)count[]數(shù)組中的記錄，將元素放入temp[]數(shù)組的正確位置for (int i = n - 1; i >= 0; i--){temp[count[arr[i]] - 1] = arr[i];count[arr[i]]--;}// 將temp[]數(shù)組的元素復(fù)制回原數(shù)組arr[]for (int i = 0; i < n; i++){arr[i] = temp[i];}
}int main()
{int arr[] = {9, 3, 6, 1, 3, 2, 9, 0};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的數(shù)組：\n");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}counting_sort(arr, n);printf("\n排序后的數(shù)組: \n");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}putchar('\n');return 0;
}

這段代碼實(shí)現(xiàn)了計(jì)數(shù)排序算法。主要包括以下步驟：

1.遍歷數(shù)組找出最大值，確定統(tǒng)計(jì)數(shù)組count[]的長(zhǎng)度。
2.創(chuàng)建并初始化統(tǒng)計(jì)數(shù)組count[]，長(zhǎng)度為最大值加1。
3.遍歷數(shù)組，統(tǒng)計(jì)每個(gè)元素的出現(xiàn)次數(shù)，存儲(chǔ)在count[]中。
4.累加count[]數(shù)組，表示小于等于元素i的元素個(gè)數(shù)。
5.創(chuàng)建臨時(shí)數(shù)組temp[]，用于存儲(chǔ)排好序的元素。
6.逆序遍歷原數(shù)組，根據(jù)count[]數(shù)組中的記錄，將元素放入temp[]數(shù)組的正確位置。
7.將temp[]數(shù)組的元素復(fù)制回原數(shù)組arr[]，完成排序。

運(yùn)行如上代碼，你可以看到以下輸出：