计数排序算法
- 计数排序算法
- 实现
计数排序是一种外部排序算法，它假设所有输入值都是位于 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] 现在包含等于 i 的元素个数。 for i = 1 to 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]
分析
计数排序算法的平均情况时间复杂度与桶排序相同。它在 O(n) 时间内运行。
示例
考虑一个待排序的输入列表：0, 2, 1, 4, 6, 2, 1, 1, 0, 3, 7, 7, 9。
为了便于计算，我们从个位数开始。
步骤 1
创建两个数组：一个用于存储计数器，另一个用于输出。将计数器数组初始化为零。
步骤 2
遍历输入列表并递增所有计数器值后，我们得到 −
步骤 3
现在，将元素推入输出列表的对应索引位置。
步骤 4
在输出数组中添加元素后，将计数器减 1。现在，1 被添加到第 4th 个索引。
步骤 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]