计数排序算法

计数排序是一种外部排序算法，它假设所有输入值都是介于 0 到 k 之间的整数。然后对这些输入值进行数学计算，将它们放置在输出数组中的正确位置。

该算法使用计数器来计算数字出现的频率并进行相应的排列。假设数字"m"在输入序列中出现了5次，则该数字的计数器值将变为5，并在输出数组中重复5次。

计数排序算法

计数排序算法假设输入相对较小，因此算法如下 −

步骤1 − 维护两个数组，一个数组的大小与输入元素大小相同（无重复），用于存储计数值；另一个数组的大小与输入数组大小相同，用于存储输出。

步骤2 −将计数数组初始化为全零，并保持输出数组为空。

步骤 3 − 每当输入列表中出现一个元素时，相应的计数器值加 1，直到到达输入列表的末尾。

步骤 4 − 现在，在输出数组中，每当计数器大于 0 时，就将元素添加到其相应的索引处。例如，如果计数器"0"为 2，则在输出数组的第 2 个位置（即第一个索引）添加"0"。然后将计数器值减 1。

步骤 5 − 重复步骤 4，直到所有计数器值都变为 0。得到的列表即为输出列表。

COUNTING-SORT(A, B, k)
let C[0 … k] be a new array
for i = 0 to k
C[i] = 0
for j = 1 to A.length
C[A[j]] = C[A[j]] + 1

// C[i] 现在包含等于 i 的元素个数。
for i = 1 到 k
C[i] = C[i] + C[i – 1]
// C[i] 现在包含小于或等于 i 的元素个数。
for j = A.length downto 1
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j – 1]

分析

计数排序算法的平均时间复杂度与桶排序相同。运行时间为 Θ(n)。

示例

假设输入列表排序为 0、2、1、4、6、2、1、1、0、3、7、7、9。

为了便于计算，我们从个位数开始。

步骤 1

创建两个数组：分别用于存储计数器和输出。用零初始化计数器数组。

步骤 2

将所有计数器值递增，直到到达输入列表的末尾，我们得到 −

步骤 3

现在，将输出列表中相应索引处的元素推送到输出列表中。

步骤 4

减少计数器在输出数组中添加元素后增加 1。现在，在第 4 个索引处添加 1。

步骤 5

添加上一步中索引前面的剩余值。

步骤 6

添加最后的值后，我们得到 −

最终排序后的输出为 0, 0, 1, 1, 1, 2, 2, 3, 4, 6, 7, 7, 9

实现

计数排序的实现与算法紧密相关，我们构造一个数组来存储输入数组中每个元素的频率。根据这些频率，将元素放置在输出数组中。重复元素也会在计数排序算法中排序。

示例

在本章中，我们将研究用四种不同的编程语言实现的计数排序程序。

#include<stdio.h>
int countingsort(int a[], int n){
   int i, j;
   int output[15], c[100];
   for (i = 0; i < 100; i++)
      c[i] = 0;
   for (j = 0; j < n; j++)
      ++c[a[j]];
   for (i = 1; i <= 99; i++)
      c[i] += c[i-1];
   for (j = n-1; j >= 0; j--) {
      output[c[a[j]] - 1] = a[j];
      --c[a[j]];
   }
   printf("
排序后数组元素为：");
   for (i = 0; i<n; i++)
      printf("%d ", output[i]);
}
void main(){
   int n , i;
   int a[] = {12, 32, 44, 8, 16};
   n = sizeof(a) / sizeof(a[0]);
   printf("排序前数组元素为：");
   for(int i = 0; i<n; i++){
       printf("%d " , a[i]);
   }
   countingsort(a, n);
}

排序前数组元素为：12 32 44 8 16 
排序后数组元素为：8 12 16 32 44

#include<iostream>
using namespace std;
void countingsort(int a[], int n){
   int i, j;
   int output[15], c[100];
   for (i = 0; i < 100; i++)
      c[i] = 0;
   for (j = 0; j < n; j++)
      ++c[a[j]];
   for (i = 1; i <= 99; i++)
      c[i] += c[i-1];
   for (j = n-1; j >= 0; j--) {
      output[c[a[j]] - 1] = a[j];
      --c[a[j]];
   }
   cout << "
排序后数组元素为：";
   for (i = 0; i <n; i++)
      cout << output[i] << " ";
}
int main(){
   int n , i;
   int a[] = {12, 32, 44, 8, 16};
   n = sizeof(a) / sizeof(a[0]);
   cout<<"排序前数组元素为：";
   for(int i = 0; i<n; i++){
       cout<<a[i]<<" ";
   }
   countingsort(a, n);
   cout << "
";
   return 0;
}

排序前数组元素为：12 32 44 8 16 
排序后数组元素为：8 12 16 32 44 

import java.io.*;
public class counting_sort {
   static void sort(int a[], int n) {
      int i, j;
      int output[] = new int[15];
      int c[] = new int[100];
      for (i = 0; i < 100; i++)
      c[i] = 0;
      for (j = 0; j < n; j++)
      ++c[a[j]];
      for (i = 1; i <= 99; i++)
      c[i] += c[i-1];
      for (j = n-1; j >= 0; j--) {
         output[c[a[j]] - 1] = a[j];
         --c[a[j]];
      }
      System.out.println("
排序后数组元素为：");
      for (i = 0; i < n; ++i)
      System.out.print(output[i] + " ");
   }
   public static void main(String args[]){
      int a[] = {12, 32, 44, 8, 16};
      int n = a.length;
      System.out.println("排序前数组元素为：");
      for(int i = 0; i<n; i++){
          System.out.print(a[i] + " ");
      }
      // Function call
      sort(a, n);
   }
}

排序前数组元素为：
12 32 44 8 16 
排序后数组元素为：
8 12 16 32 44 

output = []
def counting_sort(a, n):
    output = [0] * n
    c = [0] * 100
    for i in range(100):
        c[i] = 0
    for j in range(n):
        c[a[j]] += 1
    for i in range(1, 99):
        c[i] += c[i-1]
    for j in range(n-1, -1, -1):
        output[c[a[j]] - 1] = a[j]
        c[a[j]] -= 1
    print("排序后数组元素为：")
    print(output)
a = [12, 32, 44, 8, 16]
n = len(a)
print("排序前数组元素为：")
print (a)
counting_sort(a, n)

排序前数组元素为：
[12, 32, 44, 8, 16]
排序后数组元素为：
[8, 12, 16, 32, 44]