计数排序算法

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

此算法利用计数器来计算数字出现的频率并相应地对其进行排列。假设，如果数字“m”在输入序列中出现 5 次，则该数字的计数器值将变为 5，并且它在输出数组中重复 5 次。

计数排序算法

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

步骤 1 - 维持两个数组，一个数组的大小为输入元素（不重复）以存储计数值，另一个数组的大小为输入数组以存储输出。

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

步骤 3 - 每次输入列表中出现元素时，将相应的计数器值增加 1，直到到达输入列表的末尾。

步骤 4 - 现在，在输出数组中，每当计数器大于 0 时，在其各自的索引处添加元素，即如果“0”的计数器为 2，“0”添加到输出数组的第 2 个位置（即第 1 个索引）。然后将计数器值减 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] now contains the number of elements equal to i.
for i = 1 to k
C[i] = C[i] + C[i – 1]
// C[i] now contains the number of elements less than or equal to 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。现在，1 添加到第 4 个索引处。

步骤 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("\nAfter sorting array elements are: ");
   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("Before sorting array elements are: ");
   for(int i = 0; i<n; i++){
       printf("%d " , a[i]);
   }
   countingsort(a, n);
}

Before sorting array elements are: 12 32 44 8 16 
After sorting array elements are: 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 << "\nAfter sorting array elements are: ";
   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<<"Before sorting array elements are: ";
   for(int i = 0; i<n; i++){
       cout<<a[i]<<" ";
   }
   countingsort(a, n);
   cout << "\n";
   return 0;
}

Before sorting array elements are: 12 32 44 8 16 
After sorting array elements are: 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("\nAfter sorting array elements are: ");
      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("Before sorting array elements are: ");
      for(int i = 0; i<n; i++){
          System.out.print(a[i] + " ");
      }
      // Function call
      sort(a, n);
   }
}

Before sorting array elements are: 
12 32 44 8 16 
After sorting array elements are: 
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("After sorting array elements are: ")
    print(output)
a = [12, 32, 44, 8, 16]
n = len(a)
print("Before sorting array elements are: ")
print (a)
counting_sort(a, n)

Before sorting array elements are: 
[12, 32, 44, 8, 16]
After sorting array elements are: 
[8, 12, 16, 32, 44]