设计与分析-计数排序

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

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

计数排序算法

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

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

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

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

步骤 4 - 现在，在输出数组中，每当计数器大于 0 时，就在其各自的索引处添加该元素，即如果“0”的计数器为 2，则在第 2 个位置（即第 1 个索引）添加“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] 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。^{现在，在第 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("\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]