計數排序演算法

計數排序是一種外部排序演算法，它假設所有輸入值都是介於 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]