计数排序算法（附带 Python/Java/C/C++ 程序）

2025年5月20日 | 阅读 12 分钟

计数排序算法不通过比较元素进行排序。它通过计算具有不同键值的对象的数量来进行排序，类似于哈希。然后，它执行一些算术运算来计算每个对象在输出序列中的索引位置。计数排序不作为通用排序算法使用。

当范围不大于要排序的对象数量时，计数排序是有效的。它可以用于对负数输入值进行排序。

算法

countingSort(array, n) // 'n' is the size of the array  
max = find the maximum element in the given array  
create a count array with a size maximum + 1  
Initialize the count array with all 0's  
for i = 0 to n  
find the count of every unique element and   
store that count at the i-th position in the count array  
for j = 1 to max  
Now, find the cumulative sum and store it in the count array  
Create an output array of the same size as the input array.
for i = n to 1  
Restore the array elements  
Decrease the count of every restored element by 1 in the count array
Display the result of the output array
end countingSort  

计数排序算法的步骤

步骤 1：找到输入数组中的最大元素。

步骤 2：创建一个大小为 **max** + 1 的计数数组，其中 max 是最大元素。

步骤 3：将计数数组的元素初始化为 0。

步骤 4：将每个元素的频率存储在计数数组中，使得每个元素都存储在其对应的索引处。例如，元素 **2** 的频率将存储在 countArray[**2**] 中。

步骤 5：使用循环，将累积和存储在计数数组中。我们通过执行以下操作来实现此目的。

countArray[i] = countArray[i] + countArray[i - 1]

步骤 6：从后向前遍历输入数组并执行以下操作

outputArray[countArray[inputArray[i]] - 1] =inputArray[i]
countArray[inputArray[i]] = countArray[inputArray[i]] - 1

计数排序算法的工作原理

现在，让我们看看计数排序算法的工作原理。

为了理解计数排序算法的工作原理，让我们拿一个未排序的数组。

找到输入数组中的最大元素。最大元素是 6。

现在，我们创建一个大小为 max + 1 的计数数组。因此，计数数组中有 7 个元素。确保计数数组的所有元素都初始化为 0。

现在，我们必须将每个数组元素在计数数组中的计数存储在其对应的索引处。元素计数将按以下方式存储。

我们看到数组元素 '4' 出现两次，所以元素 4 的计数是 2。因此，2 存储在计数数组的第 4 个位置。如果数组中不存在某个元素，我们将在此索引处赋值 0。我们看到元素 '2' 不存在于数组中，所以第 2 个位置将存储 0。

现在，存储 **count** 数组元素的累积和。累积和计算如下：

这将有助于将元素放置在排序数组的正确索引处。

现在，创建一个输出数组。它将以排序的顺序存储元素。现在，借助计数数组和输入数组，开始将元素放置在输出数组的适当位置。

我们将从右向左遍历输入数组中的元素。最后一个元素是输入数组中的 3。因此，我们转到计数数组的索引 3。在索引 3 处，我们看到元素是 5。现在，将 5 减 1。得到 4。在输出数组的索引 4 处，放入元素 3。

将元素放入其位置后，在计数数组中将其计数减一，然后再放置倒数第二个元素，即 1。现在，我们找到计数数组索引 1 处的值。我们看到值为 2。在索引 2 - 1 = 1 的输出数组的第一个索引处，放入元素 1。

再次，将计数数组索引 1 处的计数减一。之后，移动到输入数组的第三个最后一个元素，即 4。转到计数数组的索引 4，我们得到 7。因此，在输出数组的索引 7 - 1 = 6 处，放入元素 4。

再次，将计数数组索引 4 处的计数减一。之后，移动到输入数组的第四个最后一个元素，即 3。转到计数数组的索引 3，我们得到 4。因此，在输出数组的索引 4 - 1 = 3 处，放入元素 3。

与之前的步骤类似，将计数数组索引 3 处的计数减一。之后，移动到输入数组的第五个最后一个元素，即 1。转到计数数组的索引 1，我们得到 1。因此，在输出数组的索引 1 - 1 = 0 处，放入元素 1。

再次，将计数数组索引 1 处的计数减一。之后，移动到输入数组的第六个最后一个元素，即 4。转到计数数组的索引 4，我们得到 6。因此，在输出数组的索引 6 - 1 = 5 处，放入元素 4。

再次，将计数数组索引 4 处的计数减一。之后，移动到输入数组的第二个元素，即 6。转到计数数组的索引 6，我们得到 8。因此，在输出数组的索引 8 - 1 = 7 处，放入元素 6。

再次，将计数数组索引 6 处的计数减一。之后，移动到输入数组的第一个元素，即 3。转到计数数组的索引 3，我们得到 3。因此，在输出数组的索引 3 - 1 = 2 处，放入元素 3。

我们可以看到输出数组是排序好的数组。

Python/Java/C/C++/C# 中计数排序的实现

Python 程序

def countSort(inputArray):
    # Finding the maximum element of inputArray.
    MaxElement = max(inputArray)
    # Initializing countArray with 0
    countArray = [0] * (MaxElement + 1)
    # Mapping each element of inputArray as an index of countArray
    for num in inputArray:
        countArray[num] += 1
    # Calculating prefix sum at every index of countArray
    for j in range(1, MaxElement + 1):
        countArray[j] += countArray[j - 1]
    # Creating outputArray from inputArrays
    outputArray = [0] * len(inputArray)
    for j in range(len(inputArray) - 1, -1, -1):
        outputArray[countArray[inputArray[j]] - 1] = inputArray[j]
        countArray[inputArray[j]] -= 1
    return outputArray
# Driver code
if __name__ == "__main__":
    # Input array
	inputArray = [3, 6, 4, 1, 3, 4, 1, 3]
	s = len(inputArray)
	print("Before Sorting array elements are: ")
	for j in range(s):
		print("%d" % inputArray[j], end=" ")
    # Output array
	outputArray = countSort(inputArray)
	print("\nAfter Sorting array elements are: ")
	for num in outputArray:
		print(num, end=" ")

立即执行

Java 程序

class Main {  
int getMax(int[] a, int n) {  
  int max = a[0];  
  for(int i = 1; i<n; i++) {  
      if(a[i] > max)  
         max = a[i];  
  }  
  return max; //maximum element from the array  
}  
void countSort(int[] a, int n) { // function to perform counting sort  
   int[] outputArray = new int [n+1];  
   int max = getMax(a, n);  
   //int max = 42;  
   int[] count = new int [max+1]; //create count array with size [max+1]  
  for (int i = 0; i <= max; ++i)    {  
    count[i] = 0; // Initialize count array with all zeros  
  }  
  for (int i = 0; i < n; i++)   {  // Store the count of each element  
    count[a[i]]++;  
  }  
   for(int i = 1; i<=max; i++)   
      count[i] += count[i-1]; //find cumulative frequency  
  /* The loop will find the index of each element of the original array in  
       the count array, and place the elements in the output array*/  
  for (int i = n - 1; i >= 0; i--) {  
    outputArray[count[a[i]] - 1] = a[i];  
    count[a[i]]--; // decrease count for same numbers  
}  
   for(int i = 0; i<n; i++) {  
      a[i] = outputArray[i]; //store the sorted elements into main array  
   }  
}  
/* Function to print the array elements */  
void printArray(int a[], int n)  {  
    int i;  
    for (i = 0; i < n; i++)  
        System.out.print(a[i] + " ");  
}  
public static void main(String args[])  
{  
    int inputArray[] = {3, 6, 4, 1, 3, 4, 1, 3};  
    int n = inputArray.length;  
    Main c1 = new Main();  
    System.out.println("Before sorting array elements are: ");  
    c1.printArray(inputArray, n);  
    c1.countSort(inputArray,n);  
    System.out.println("\nAfter sorting array elements are: ");  
    c1.printArray(inputArray, n);  
    System.out.println();  
}  
}  

编译并运行

C++ 程序

#include <iostream>  
using namespace std;  
int getMax(int a[], int n) {  
   int max = a[0];  
   for(int i = 1; i<n; i++) {  
      if(a[i] > max)  
         max = a[i];  
   }  
   return max; //maximum element from the array  
}  
void countSort(int a[], int n) { // function to perform counting sort  
   int outputArray[n+1];  
   int max = getMax(a, n);  
   int count[max+1]; //create count array with size [max+1]  
  for (int i = 0; i <= max; ++i)  {  
    count[i] = 0; // Initialize count array with all zeros  
  }  
  for (int i = 0; i < n; i++) { // Store the count of each element  
    count[a[i]]++;  
  }  
   for(int i = 1; i<=max; i++)   
      count[i] += count[i-1]; //find cumulative frequency  
  /* This loop will find the index of each element of the original array in the count array, and place the elements in the output array*/  
  for (int i = n - 1; i >= 0; i--) {  
    outputArray[count[a[i]] - 1] = a[i];  
    count[a[i]]--; // decrease count for same numbers  
}  
   for(int i = 0; i<n; i++) {  
      a[i] = outputArray[i]; //store the sorted elements into main array  
   }  
}  
void printArr(int a[], int n) { /* function to print the array */  
    int i;  
    for (i = 0; i < n; i++)  
        cout<<a[i]<<" ";  
}  
int main() {  
    int inputArray[] = {3, 6, 4, 1, 3, 4, 1, 3};  
    int n = sizeof(inputArray)/sizeof(inputArray[0]);  
    cout<<"Before sorting array elements are: \n";  
    printArr(inputArray, n);  
    countSort(inputArray, n);  
    cout<<"\nAfter sorting array elements are: \n";    
    printArr(inputArray, n);  
    return 0;  
}  

编译并运行

C 语言程序

#include<stdio.h>  
int getMax(int a[], int n) {  
   int max = a[0];  
   for(int i = 1; i<n; i++) {  
      if(a[i] > max)  
         max = a[i];  
   }  
   return max; //maximum element from the array  
}  
void countSort(int a[], int n) { // function to perform counting sort  
   int outputArray[n+1];  
   int max = getMax(a, n);  
   int count[max+1]; //create count array with size [max+1]  
  for (int i = 0; i <= max; ++i)  {  
    count[i] = 0; // Initialize count array with all zeros  
  }  
  for (int i = 0; i < n; i++) { // Store the count of each element  
    count[a[i]]++;  
  }  
   for(int i = 1; i<=max; i++)   
      count[i] += count[i-1]; //find cumulative frequency  
  /* This loop will find the index of each element of the original array in the count array, and place the elements in the output array*/  
  for (int i = n - 1; i >= 0; i--) {  
    outputArray[count[a[i]] - 1] = a[i];  
    count[a[i]]--; // decrease count for same numbers  
}  
   for(int i = 0; i<n; i++) {  
      a[i] = outputArray[i]; //store the sorted elements into main array  
   }  
}  
void printArr(int a[], int n)  {   /* function to print the array */ 
    int i;  
    for (i = 0; i < n; i++)  
        printf("%d ", a[i]);  
}  
int main() {  
    int inputArray[] = {3, 6, 4, 1, 3, 4, 1, 3};  
    int n = sizeof(inputArray)/sizeof(inputArray[0]);  
    printf("Before sorting array elements are: \n");  
    printArr(inputArray, n);  
    countSort(inputArray, n);  
    printf("\nAfter sorting array elements are: \n");    
    printArr(inputArray, n);  
    return 0;  
}

编译并运行

C# 程序

using System;  
class CountingSort {  
static int getMax(int[] a, int n) {  
  int max = a[0];  
  for(int i = 1; i<n; i++) {  
      if(a[i] > max)  
         max = a[i];  
  }  
  return max; //maximum element from the array  
}  
static void countSort(int[] a, int n) {  // function to perform counting sort  
   int[] outputArray = new int [n+1];  
   int max = getMax(a, n);  
   int[] count = new int [max+1]; //create count array with size [max+1]  
  for (int i = 0; i <= max; ++i)   {  
    count[i] = 0; // Initialize count array with all zeros  
  }  
  for (int i = 0; i < n; i++)   {  // Store the count of each element  
    count[a[i]]++;  
  }  
   for(int i = 1; i<=max; i++)   
      count[i] += count[i-1]; //find cumulative frequency  
  /* This loop will find the index of each element of the original array in the count array and place the elements in the output array*/  
  for (int i = n - 1; i >= 0; i--) {  
    outputArray[count[a[i]] - 1] = a[i];  
    count[a[i]]--; // decrease count for same numbers  
}  
   for(int i = 0; i<n; i++) {  
      a[i] = outputArray[i]; //store the sorted elements into main array  
   }  
}  
static void printArr(int[] a, int n) /* function to print the array */  
{  
    int i;  
    for (i = 0; i < n; i++)  
        Console.Write(a[i] + " ");  
}  
  static void Main() {  
    int[] inputArray = {3, 6, 4, 1, 3, 4, 1, 3};  
    int n = inputArray.Length;  
    Console.Write("Before sorting array elements are: \n");  
    printArr(inputArray,n);  
    countSort(inputArray,n);  
    Console.Write("\nAfter sorting array elements are: \n");    
    printArr(inputArray,n);  
}  
}  

编译并运行

输出

Before sorting array elements are: 
3 6 4 1 3 4 1 3 
After sorting array elements are: 
1 1 3 3 3 4 4 6

复杂度分析

现在，让我们看看计数排序在最佳情况、平均情况和最坏情况下的时间复杂度。我们还将看看计数排序的空间复杂度。

时间复杂度

最佳情况复杂度：当不需要排序时发生，即数组已排序。计数排序的最佳情况时间复杂度为 **O(n + k)**。

平均情况复杂度：当数组元素混乱无序，既非升序也非降序时发生。计数排序的平均情况时间复杂度为 **O(n + k)**。

最坏情况复杂度：当需要反向排序数组元素时发生。这意味着我们需要按升序排序数组元素，但其元素是降序的。计数排序的最坏情况时间复杂度为 **O(n + k)**，其中 **n** 和 **k** 分别是 **inputArray[]** 和 **outputarray[]** 的大小。

在以上所有情况下，计数排序的时间复杂度都相同，因为算法会遍历 **n + k** 次，而不管元素在数组中的放置方式如何。

计数排序比基于比较的排序技术更好，因为计数排序中没有元素之间的比较。但是当整数非常大时，计数排序效果不好，因为必须创建那么大的数组。

情况	时间复杂度
最佳情况	O(n + k)
平均情况	O(n + k)
最坏情况	O(n + k)

空间复杂度

计数排序的空间复杂度为 **O(max)**，其中 **max** 是输入数组中的最大元素。元素的范围越大，空间复杂度越大。

计数排序的应用

在那些范围不大但有限制的场景中，它是一种常用的算法。例如，按时间对事件进行排序，按成绩对学生进行排序，按天、年、月、时间等对事件进行排序。
在基数排序中，它被用作子程序。
为了将元素分成不同的桶，使用了计数排序的思想。

计数排序的优点

如果输入范围与输入数量大致相同，则计数排序通常比快速排序和归并排序等其他基于比较的排序算法执行得更快。
它易于编码。
它是一种稳定的算法。

计数排序的缺点

在十进制值上，计数排序不起作用。
如果需要排序的值的范围非常大，则计数排序效率不高。
计数排序不是原地排序算法，因为它使用额外的空间来排序数组元素。

结论

计数排序是特定场景下的重要工具，这些场景中稳定性是首要考虑因素，特别是当对定义范围内的数字进行排序时。但是，当范围很大或数字不是整数时，它不适合。

下一个主题希尔排序

← 上一个下一个 →

计数排序算法（附带 Python/Java/C/C++ 程序）

算法

计数排序算法的步骤

计数排序算法的工作原理

Python/Java/C/C++/C# 中计数排序的实现

Python 程序

Java 程序

C++ 程序

C 语言程序

C# 程序

复杂度分析

时间复杂度

空间复杂度

计数排序的应用

计数排序的优点

计数排序的缺点

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

计数排序算法（附带 Python/Java/C/C++ 程序）

算法

计数排序算法的步骤

计数排序算法的工作原理

Python/Java/C/C++/C# 中计数排序的实现

Python 程序

Java 程序

C++ 程序

C 语言程序

C# 程序

复杂度分析

时间复杂度

空间复杂度

计数排序的应用

计数排序的优点

计数排序的缺点

结论

相关帖子

基数排序算法

排序算法

桶排序算法

归并排序算法

选择排序算法

快速排序算法

排序算法的时间复杂度

插入排序算法

堆排序算法

冒泡排序算法

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器