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

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

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

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

需要注意的是，計數(shù)排序適用于元素范圍較小且非負整數(shù)的排序，如果待排序數(shù)組包含負數(shù)或者小數(shù)，則需要進行適當?shù)霓D換或調整。計數(shù)排序是穩(wěn)定的排序算法，因為相同元素的相對順序在排序后保持不變，但它不是基于比較的排序算法，因此在某些情況下比其他排序算法更高效。

下面是一個使用C語言實現(xiàn)的計數(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)計數(shù)組count[]，并初始化為0int count[max + 1];for (int i = 0; i <= max; i++){count[i] = 0;}// 統(tǒng)計每個元素的次數(shù)for (int i = 0; i < n; i++){count[arr[i]]++;}// 累加count[]數(shù)組，表示小于等于元素i的元素個數(shù)for (int i = 1; i <= max; i++){count[i] += count[i - 1];}// 創(chuàng)建臨時數(shù)組temp[]，存儲排好序的元素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ù)組的元素復制回原數(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;
}

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

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

運行如上代碼，你可以看到以下輸出：