计数排序算法
提示
- 计数排序基本概念:计数排序是通过计算数组中每个唯一元素的出现次数,并利用辅助数组的索引来排序这些元素的算法。
- 工作原理:首先找到数组中的最大元素,并创建一个长度为最大元素加一的辅助数组。然后,在辅助数组中存 储每个元素的出现次数,最后按累计计数顺序放置元素。
- 性能和应用:计数排序的时间复杂度为
O(n+k)
(n 是元素数量,k 是元素范围),适用于具有多个重复较小整数的情况,但在整数范围非常大时不理想。
计数排序是一种排序算法,通过计算数组中每个唯一元素的出现次数来对元素进行排序。计数存储在辅助数组中,排序通过将计数作为辅助数组的索引来完成。
计数排序的工作原理
-
找出给定数组中的最大元素(设为
max
)。 -
初始化一个长度为
max+1
的数组,所有元素为 0。这个数组用于存储数组中元素的计数。 -
在
count
数组的各自索引处存储每个元素的计数。例如:如果元素 3 的计数为 2,则在
count
数组的第 3 个位置存储 2。如果数组中不存在元素 "5",则在第 5 个位置存储 0。 -
存储
count
数组元素的累计和。这有助于将元素正确放置到排序数组的相应索引中。 -
找出原始数组中每个元素在
count
数组中的索引。这提供了累计计数。如下图所示,将元素放置在计算出的索引处。 -
将每个元素放置在其正确位置后,将其计数减一。
计数排序算法
countingSort(array, size)
max <- find largest element in array
initialize count array with all zeros
for j <- 0 to size
find the total count of each unique element and
store the count at jth index in count array
for i <- 1 to max
find the cumulative sum and store it in count array itself
for j <- size down to 1
restore the elements to array
decrease count of each element restored by 1
Python、Java 和 C/C++ 中的计数排序代码
# Python 编程中的计 数排序
def countingSort(array):
size = len(array)
output = [0] * size
# 初始化计数数组
count = [0] * 10
# 在计数数组中存储每个元素的计数
for i in range(0, size):
count[array[i]] += 1
# 存储累计计数
for i in range(1, 10):
count[i] += count[i - 1]
# 在计数数组中 找出原始数组中每个元素的索引
# 并将元素放置在输出数组中
i = size - 1
while i >= 0:
output[count[array[i]] - 1] = array[i]
count[array[i]] -= 1
i -= 1
# 将排序后的元素复制到原始数组中
for i in range(0, size):
array[i] = output[i]
data = [4, 2, 2, 8, 3, 3, 1]
countingSort(data)
print("按升序排序的数组:")
print(data)
// Java 编程中的计数排序
import java.util.Arrays;
class CountingSort {
void countSort(int array[], int size) {
int[] output = new int[size + 1];
// 查找数组中的最大元素
int max = array[0];
for (int i = 1; i < size; i++) {
if (array[i] > max)
max = array[i];
}
int[] count = new int[max + 1];
// 用零初始化计数数组
for (int i = 0; i < max; ++i) {
count[i] = 0;
}
// 存储每个元素的计数
for (int i = 0; i < size; i++) {
count[array[i]]++;
}
// 存储每个数组的累积计数
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// 在计数数组中找到原始数组每个元素的索引,并将元素放置在输出数组中
for (int i = size - 1; i >= 0; i--) {
output[count[array[i]] - 1] = array[i];
count[array[i]]--;
}
// 将排序后的元素复制回原数组
for (int i = 0; i < size; i++) {
array[i] = output[i];
}
}
// 驱动代码
public static void main(String args[]) {
int[] data = { 4, 2, 2, 8, 3, 3, 1 };
int size = data.length;
CountingSort cs = new CountingSort();
cs.countSort(data, size);
System.out.println("按升序排序后的数组: ");
System.out.println(Arrays.toString(data));
}
}
// C 语言中的计数排序
#include <stdio.h>
void countingSort(int array[], int size) {
int output[10];
// 查找数组中的最大元素
int max = array[0];
for (int i = 1; i < size; i++) {
if (array[i] > max)
max = array[i];
}
// 计数数组的大小至少为 (max+1),但
// 在 C 中不能声明为 int count(max+1),因为
// 它不支持动态内存分配。
// 因此,它的大小是静态提供的。
int count[10];
// 用零初始化计数数组
for (int i = 0; i <= max; ++i) {
count[i] = 0;
}
// 存储每个元素的计数
for (int i = 0; i < size; i++) {
count[array[i]]++;
}
// 存储每个数组的累积计数
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// 在计数数组中找到原始数组每个元素的索引,并将元素放置在输出数组中
for (int i = size - 1; i >= 0; i--) {
output[count[array[i]] - 1] = array[i];
count[array[i]]--;
}
// 将排序后的元素复制回原数组
for (int i = 0; i < size; i++) {
array[i] = output[i];
}
}
// 打印数组的函数
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// 驱动代码
int main() {
int array[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(array) / sizeof(array[0]);
countingSort(array, n);
printArray(array, n);
}
// C++ 编程中的计数排序
#include <iostream>
using namespace std;
void countSort(int array[], int size) {
// 计数数组的大小至少为 (max+1),但是
// 我们不能在 C++ 中声明为 int count(max+1),因为
// 它不支持动态内存分配。
// 所以,其大小是静态提供的。
int output[10];
int count[10];
int max = array[0];
// 找到数组中的最大元素
for (int i = 1; i < size; i++) {
if (array[i] > max)
max = array[i];
}
// 使用全部零初始化计数数组。
for (int i = 0; i <= max; ++i) {
count[i] = 0;
}
// 存储每个元素的计数
for (int i = 0; i < size; i++) {
count[array[i]]++;
}
// 存储每个数组的累计计数
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// 在计数数组中找出原始数组中每个元素的索引,并
// 将元素放置在输出数组中
for (int i = size - 1; i >= 0; i--) {
output[count[array[i]] - 1] = array[i];
count[array[i]]--;
}
// 将排序后的元素复制到原始数组中
for (int i = 0; i < size; i++) {
array[i] = output[i];
}
}
// 打印数组的函数
void printArray(int array[], int size) {
for (int i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
// 驱动代码
int main() {
int array[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(array) / sizeof(array[0]);
countSort(array, n);
printArray(array, n);
}
复杂度
时间复杂度 | |
---|---|
最好 | O(n+k) |
最坏 | O(n+k) |
平均 | O(n+k) |
空间复杂度 | O(max) |
--- | --- |
稳定性 | 是 |
--- | --- |
时间复杂度
主要有四个循环。(寻找最大值可以在函数外部完成。) | 循环 | 计数时间 |
---|---|---|
第1次 | O(max) | |
第2次 | O(size) | |
第3次 | O(max) | |
第4次 | O(size) |
总复杂度 = O(max)+O(size)+O(max)+O(size)
= O(max+size)
- 最坏情况复杂度:
O(n+k)
- 最佳情况复杂度:
O(n+k)
- 平均情况复杂度:
O(n+k)
在上述所有情况中,复杂度是相同的,因为无论数组中的元素如何排列,算法都会运行 n+k
次。
由于不需要对任何元素进行比较,因此它比基于比较的排序技术更好。但是,如果整数非常大,这种方法就不理想,因为需要创建这么大规模的数组。
空间复杂度
计数排序的空间复杂度为 O(max)
。元素范围越大,空间复杂度越大。
计数排序的应用
计数排序适用于以下情况:
- 存在多个重复的较小整数。
- 需要线性复杂度。