博客

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

计数排序是一种用于整数的线性时间排序算法。该算法的基本思想是对于给定的输入序列里的每一个元素x，确定该序列中值小于x的元素个数。利用这一信息，就可以直接把x放在最终的输出序列的正确位置上。

使用方法

计数排序算法适用于一定范围内的整数数组排序，虽然使用范围较窄，但是由于其速度较快，因此在某些特定场合下还是被广泛使用的。

算法步骤

计数排序算法的运行速度和所给出排序的数字范围的最大值max和最小值min有关，因此计数排序算法的时间复杂度约为O(k+n)，其中k= max-min+1，当数字范围不是很大考虑使用计数排序算法。

具体的实现步骤如下：

  1. 找出待排序数组中的最大值max和最小值min；
  2. 新建一个长度为k=max-min+1的数组c，用来记录输入数组中每个数字出现的次数。第i位的统计结果表示序列中有多少个元素相等于i+min；
  3. 遍历输入数组，此时的索引i表示当前处理元素的值，遍历时，如果输入的数字为a，则c(a-min)的值加1；
  4. 由于c的第i个元素表示输入数组中有多少个元素小于等于i+min，因此先统计小于等于i+min的元素个数之和sum，然后将数组输出的下标为sum-1的元素值更改为输入数组中的第i个元素值；
  5. 重复步骤4，直到数组所有元素有序为止。

代码样例

下面是python代码的实现示例：

def counting_sort(arr):
    max_num = max(arr)
    min_num = min(arr)
    k = max_num - min_num + 1
    c = [0] * k
    for i in range(len(arr)):
        c[arr[i]-min_num] += 1
    for i in range(1, k):
        c[i] += c[i-1]
    res = [0] * len(arr)
    for i in range(len(arr)-1, -1, -1):
        index = c[arr[i]-min_num] - 1
        res[index] = arr[i]
        c[arr[i]-min_num] -= 1
    return res

print(counting_sort([3, 1, 5, 7, 2, 4, 9, 3, 6]))
# 输出：[1, 2, 3, 3, 4, 5, 6, 7, 9]

该代码实现了对一个数组的计数排序操作，打印结果为从小到大排序后的数组。

示例说明

示例1：排序一组年龄数据

现在有一组年龄数据，需要对其进行排序：

arr = [18, 25, 27, 22, 17, 34, 60, 45, 12, 15, 20, 35]

将其代入计数排序算法：

res = counting_sort(arr)
print(res)

输出为经过排序后的数组：[12, 15, 17, 18, 20, 22, 25, 27, 34, 35, 45, 60]，该数组年龄递增有序排列。

示例2：统计一个自然文本中每个单词出现的次数

在自然文本处理中，统计每个单词出现的次数是十分常见的需求。计数排序算法可以结合哈希表实现该需求。

文本信息：

sentences = """This is a python textbook, and the author is very friendly.
In this textbook, you will learn python which is a popular language.
Python is used for web development, data science, artificial intelligence, etc."""

import re

def count_words(sentences):
    # 清理标点符号和空格
    sentences = re.sub(r'[^\w\s]', '', sentences)
    sentences = sentences.lower()
    word_list = sentences.split()
    max_len = max([len(word) for word in word_list])
    min_len = min([len(word) for word in word_list])
    k = max_len - min_len + 1
    c = [0] * k
    for word in word_list:
        c[len(word)-min_len] += 1

    # 构建哈希表
    hash_map = {}
    for word in word_list:
        hash_map[word] = c[len(word)-min_len]

    return hash_map

print(count_words(sentences))

输出为一个哈希映射的结果:

{'this': 2, 'is': 2, 'a': 2, 'python': 2, 'textbook': 2, 'and': 1, 'the': 1, 'author': 1, 'very': 1, 'friendly': 1, 'in': 1, 'you': 1, 'will': 1, 'learn': 1, 'which': 1, 'popular': 1, 'language': 1, 'used': 1, 'for': 1, 'web': 1, 'development': 1, 'data': 1, 'science': 1, 'artificial': 1, 'intelligence': 1, 'etc': 1}

计数排序算法可以将每个单词的出现次数统计出来，并将其构建为哈希表进行返回。

Tags: