博客

详解计数排序算法原理与使用方法

计数排序（Counting Sort）是一种非比较排序算法，该算法的核心思想就是将输入的数值转化为键存储在一个数组中，然后确定每个数值在输入序列中的出现次数，最后根据每个数值的出现次数，将输入的序列排列成有序序列。

计数排序的特点是：最优时间复杂度O(n)，最坏时间复杂度O(n)，平均时间复杂度O(n+k)，空间复杂度O(n+k)，稳定排序。

基本思想

计数排序的基本思想是：对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。有了这个信息，就可以将x直接存放到输出序列的正确位置上了。

算法步骤

  1. 统计数组中每个值出现的次数，存放到计数数组中。
  2. 对计数数组进行累加，这样计数数组中的第i位就存储的是小于等于i的数的个数。
  3. 新建一个临时数组，从后往前扫描原数组，将每个元素放到临时数组中的正确位置上，并依此修改计数数组中的数值，以保证同样数值的元素放置时是从后往前放。
  4. 将新数组复制到原数组中，排序完成。

代码示例

Python 代码示例：

def countingSort(arr):
    count = [0] * (max(arr) + 1)   # 初始化计数数组
    n = len(arr)

    result = [0] * n   # 初始化输出数组
    for i in range(n):
        count[arr[i]] += 1  # 统计每个值出现的次数

    for i in range(1, len(count)):
        count[i] += count[i-1]  # 计算小于等于i的数的个数

    for i in range(n-1, -1, -1):
        result[count[arr[i]] - 1] = arr[i]   # 将arr[i]放到输出数组中的正确位置上
        count[arr[i]] -= 1  # 修改计数数组中的数值

    for i in range(n):
        arr[i] = result[i]   # 将新数组复制到原数组中

    return arr

Java 代码示例：

public static void countingSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();   // 获取数组中的最大值
    int[] count = new int[max+1];   // 初始化计数数组

    int n = arr.length;
    int[] result = new int[n];   // 初始化输出数组

    for (int i = 0; i < n; i++) {
        count[arr[i]]++;   // 统计每个值出现的次数
    }

    for (int i = 1; i < count.length; i++) {
        count[i] = count[i-1] + count[i];   // 计算小于等于i的数的个数
    }

    for (int i = n-1; i >= 0; i--) {
        result[count[arr[i]]-1] = arr[i];   // 将arr[i]放到输出数组中的正确位置上
        count[arr[i]]--;   // 修改计数数组中的数值
    }

    System.arraycopy(result, 0, arr, 0, n);   // 将新数组复制到原数组中
}

使用示例

计数排序适用于一定范围内的整数序列排序，对于可以使用整数类型存储的数据类型（如字符串），可以使用ASCII码进行转换。以下是两个使用示例。

示例一：对于给定的整数数组进行排序

arr = [3, 7, 10, 2, 9, 4, 12, 6]
countingSort(arr)
print(arr)
# 结果：[2, 3, 4, 6, 7, 9, 10, 12]

示例二：对于给定的字符串数组进行排序

arr = ['def', 'abc', 'jkl', 'ghi', 'mno']
ascii_arr = [sum([ord(c) for c in word]) for word in arr]   # 将字符串转换为ASCII码
countingSort(ascii_arr)
sorted_arr = [chr(i) for i in ascii_arr]   # 将ASCII码转换为字符串
print(sorted_arr)
# 结果：['abc', 'def', 'ghi', 'jkl', 'mno']
Tags: