計數排序算法 · Programiz 中文系列教程

# 計數排序算法 > 原文： [https://www.programiz.com/dsa/counting-sort](https://www.programiz.com/dsa/counting-sort) #### 在本教程中，您將學習計數排序的工作原理。此外，您還將找到 C，C++ ，Java 和 Python 中計數排序的工作示例。計數排序是一種排序算法，它通過計算數組中每個唯一元素的出現次數來對數組的元素進行排序。計數存儲在輔助數組中，并通過將計數映射為輔助數組的索引來完成排序。 * * * ## 計數排序如何工作？ 1. 從給定數組中找出最大元素（將其設為`max`）。 ![Counting Sort steps](https://img.kancloud.cn/89/45/89452c635ef7ee34654cc31b8e76c983_1194x240.png "Given array") 給定數組 2. 使用所有元素 0 初始化長度為`max+1`的數組。此數組用于存儲數組中元素的計數。 ![Counting Sort Step](https://img.kancloud.cn/ad/b3/adb3fd8b52e35b42971bb42a50865887_1280x232.png "Count Array") 計數數組 3. 將每個元素的計數存儲在`count`數組中它們各自的索引處，例如：如果元素 3 的計數為 2，則將 2 存儲在`count`數組的第 3 位。如果數組中不存在元素“5”，則在第 5 個位置存儲 0。 ![Counting Sort Step](https://img.kancloud.cn/e5/b8/e5b8bbc0cbc2a3769d4757e0c30a17ad_1280x236.png "Count of each element") 存儲的每個元素的計數 4. 存儲計數數組元素的累積和。它有助于將元素放入已排序數組的正確索引中。 ![Counting Sort Step](https://img.kancloud.cn/e0/0d/e00d90e3a7de0d80c00ca8af890a4a00_1280x236.png "Cumulative count") 累計計數 5. 在`count`數組中找到原始數組的每個元素的索引。這給出了累計計數。將元素放置在計算出的索引處，如下圖所示。 ![Counting Sort Steps](https://img.kancloud.cn/41/bc/41bc7306a4b8820d51ee4f57b44f861a_1428x720.png "Counting Sort") 計數類別 6. 將每個元素放置在正確位置后，將其數量減少一。 * * * ## 計數排序算法 ``` countingSort(array, size) max <- find largest element in array initialize count array with all zeros for j <- 0 to size find the total count of each unique element and store the count at jth index in count array for i <- 1 to max find the cumulative sum and store it in count array itself for j <- size down to 1 restore the elements to array decrease count of each element restored by 1 ``` * * * ## Python，Java 和 C/C++ 示例 ```py # Counting sort in Python programming def countingSort(array): size = len(array) output = [0] * size # Initialize count array count = [0] * 10 # Store the count of each elements in count array for i in range(0, size): count[array[i]] += 1 # Store the cummulative count for i in range(1, 10): count[i] += count[i - 1] # Find the index of each element of the original array in count array # place the elements in output array i = size - 1 while i >= 0: output[count[array[i]] - 1] = array[i] count[array[i]] -= 1 i -= 1 # Copy the sorted elements into original array for i in range(0, size): array[i] = output[i] data = [4, 2, 2, 8, 3, 3, 1] countingSort(data) print("Sorted Array in Ascending Order: ") print(data) ``` ```java // Counting sort in Java programming import java.util.Arrays; class CountingSort { void countSort(int array[], int size) { int[] output = new int[size + 1]; // Find the largest element of the array int max = array[0]; for (int i = 1; i < size; i++) { if (array[i] > max) max = array[i]; } int[] count = new int[max + 1]; // Initialize count array with all zeros. for (int i = 0; i < max; ++i) { count[i] = 0; } // Store the count of each element for (int i = 0; i < size; i++) { count[array[i]]++; } // Store the cummulative count of each array for (int i = 1; i <= max; i++) { count[i] += count[i - 1]; } // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i >= 0; i--) { output[count[array[i]] - 1] = array[i]; count[array[i]]--; } // Copy the sorted elements into original array for (int i = 0; i < size; i++) { array[i] = output[i]; } } // Driver code public static void main(String args[]) { int[] data = { 4, 2, 2, 8, 3, 3, 1 }; int size = data.length; CountingSort cs = new CountingSort(); cs.countSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); } } ``` ```c // Counting sort in C programming #include <stdio.h> void countingSort(int array[], int size) { int output[10]; // Find the largest element of the array int max = array[0]; for (int i = 1; i < size; i++) { if (array[i] > max) max = array[i]; } // The size of count must be at least (max+1) but // we cannot declare it as int count(max+1) in C as // it does not support dynamic memory allocation. // So, its size is provided statically. int count[10]; // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) { count[i] = 0; } // Store the count of each element for (int i = 0; i < size; i++) { count[array[i]]++; } // Store the cummulative count of each array for (int i = 1; i <= max; i++) { count[i] += count[i - 1]; } // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i >= 0; i--) { output[count[array[i]] - 1] = array[i]; count[array[i]]--; } // Copy the sorted elements into original array for (int i = 0; i < size; i++) { array[i] = output[i]; } } // Function to print an array void printArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("\n"); } // Driver code int main() { int array[] = {4, 2, 2, 8, 3, 3, 1}; int n = sizeof(array) / sizeof(array[0]); countingSort(array, n); printArray(array, n); } ``` ```cpp // Counting sort in C++ programming #include <iostream> using namespace std; void countSort(int array[], int size) { // The size of count must be at least the (max+1) but // we cannot assign declare it as int count(max+1) in C++ as // it does not support dynamic memory allocation. // So, its size is provided statically. int output[10]; int count[10]; int max = array[0]; // Find the largest element of the array for (int i = 1; i < size; i++) { if (array[i] > max) max = array[i]; } // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) { count[i] = 0; } // Store the count of each element for (int i = 0; i < size; i++) { count[array[i]]++; } // Store the cummulative count of each array for (int i = 1; i <= max; i++) { count[i] += count[i - 1]; } // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i >= 0; i--) { output[count[array[i]] - 1] = array[i]; count[array[i]]--; } // Copy the sorted elements into original array for (int i = 0; i < size; i++) { array[i] = output[i]; } } // Function to print an array void printArray(int array[], int size) { for (int i = 0; i < size; i++) cout << array[i] << " "; cout << endl; } // Driver code int main() { int array[] = {4, 2, 2, 8, 3, 3, 1}; int n = sizeof(array) / sizeof(array[0]); countSort(array, n); printArray(array, n); } ``` * * * ## 復雜度 **時間復雜度**：主要有四個主要循環。（可以在函數之外找到最大值。） | 循環 | 計數時間 | | --- | --- | | 第一 | `O(max)` | | 第二 | `O(size)` | | 第三 | `O(max)` | | 第四 | `O(size)` | 總體復雜度= `O(max)+O(size)+O(max)+O(size)` = `O(max+size)` * **最壞情況**： `O(n+k)` * **最佳情況復雜度**： `O(n+k)` * **平均情況復雜度**： `O(n+k)` 在上述所有情況下，復雜度都是相同的，因為無論元素如何放置在數組中，算法都會經歷`n+k`次。沒有任何元素之間的比較，因此它比基于比較的排序技術要好。但是，如果整數很大，那是不好的，因為應該制作該大小的數組。 **空間復雜度**：計數排序的空間復雜度為`O(max)`。元素范圍越大，空間復雜度越大。 * * * ## 計算排序應用在以下情況下使用計數排序： * 有多個較小的整數。 * 線性復雜度是必要的。