排序算法 - 计数排序(Counting Sort)

by LauCyun Aug 10,2014 20:22:20 13,249 views

计数排序,顾名思义,就是对待排序数组按元素进行计数。使用前提是需要先知道待排序数组的元素范围,将这些一定范围的元素置于新数组中,新数组的大小为待排序数组中最大元素与最小元素的差值。

通俗地理解,例如有10个年龄不同的人,统计出有8个人的年龄比A小,那A的年龄就排在第9位,用这个方法可以得到其他每个人的位置,也就排好了序。当然,年龄有重复时需要特殊处理(保证稳定性),这就是为什么最后要反向填充目标数组,以及将每个数字的统计减去1的原因。

算法的步骤如下:

  • 定新数组大小——找出待排序的数组中最大和最小的元素
  • 统计次数——统计数组中每个值为\(i\)的元素出现的次数,存入新数组\(c\)的第\(i\)
  • 对统计次数逐个累加——对所有的计数累加(从\(c\)中的第一个元素开始,每一项和前一项相加)
  • 反向填充目标数组——将每个元素\(i\)放在新数组的第\(c(i)\)项,每放一个元素就将\(c(i)\)减去1

图1演示了计数排序作用于有10个数的输入数组(值的范围为0~15)上的操作过程:

图1 计数排序

其中反向填充主要是为了避免重复元素落入新数组的同一索引处。

当输入的元素是n个0到k之间的整数时,它的运行时间是\(Θ(n + k)\)。计数排序不是比较排序,排序的速度快于任何比较排序算法。

由于用来计数的数组\(c\)的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。例如:计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名。但是,计数排序可以用在基数排序算法中,能够更有效的排序数据范围很大的数组。

 

1 算法实现

C

#include <stdio.h>
#include <stdlib.h>

#define ElemType int
#define random(x) rand()%(x)
#define N 20         // 数组个数
#define MAXNUM 100   // 待排序的数字范围是0-100


void printArray(ElemType *arr, int n);

void countingSort(ElemType A[], int n, int k);


void printArray(ElemType *arr, int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%-4d", arr[i]);
    printf("\n");
}


/***
 * 计数排序
 * @param array: 待排序数组
 * @param n: 数组长度
 * @param k: 数组的最大值
 */
void countingSort(ElemType array[], int n, int k) {
    ElemType *ptemp, *pout;
    int i;
    ptemp = (ElemType *) malloc(sizeof(ElemType) * k);
    pout = (ElemType *) malloc(sizeof(ElemType) * n);
    // 初始化ptemp,每个元素都为0
    for (i = 0; i < k; i++)
        ptemp[i] = 0;
    // 统计array中每个值为i的元素出现的次数,存入数组ptemp的第i项
    for (i = 0; i < n; i++)
        ptemp[array[i]] += 1;
    // 对所有的计数累加(从ptemp中的第一个元素开始,每一项和前一项相加)
    for (i = 1; i < k; i++)
        ptemp[i] = ptemp[i - 1] + ptemp[i];
    // 将每个元素i放在新数组的第pout(i)项,每放一个元素就将ptemp(i)减去1
    for (i = n - 1; i >= 0; i--) {
        pout[ptemp[array[i]] - 1] = array[i];
        ptemp[array[i]] -= 1;
    }
    //
    for (i = 0; i < n; i++)
        array[i] = pout[i];
    free(ptemp);
    free(pout);
}

int main(int argc, char **argv) {
    ElemType arr[N];
    int i;
    for (i = 0; i < N; i++)
        arr[i] = random(MAXNUM);

    printf("before sorting:\n");
    printArray(arr, N);

    countingSort(arr, N, MAXNUM);

    printf("after sorting:\n");
    printArray(arr, N);
    return 0;
}

Python

 #!/usr/bin/env python
# -*- coding: utf-8 -*-


import random


def counting_sort(alist, n, max):
    """
        计数排序:当输入的元素是 n 个 0 到 k 之间的整数时(k不能太大,即max不能太大)
    @param alist: 待排序数组
    @:param n: 数组长度
    @param max: 数组中的最大值
    """
    result = [None for i in range(n)]  # 最后的结果
    temp = [0 for i in range(max + 1)]

    # 用数组temp统计每个值=d的元素个数
    for l in alist:
        temp[l] += 1

    # temp[i]表示alist中值<=i的元素个数
    for i in range(1, max + 1):
        temp[i] += temp[i - 1]

    # 将每个元素i放在新数组的第result(i)项,每放一个元素就将temp(i)减去1
    for j in range(n - 1, -1, -1):
        result[temp[alist[j]] - 1] = alist[j]
        temp[alist[j]] -= 1

    return result


N = 20
MAX = 100
unsortedArray = [random.randint(0, MAX) for i in range(N)]
print("before sorting:")
print(unsortedArray)
print("after sorting:")
print(counting_sort(unsortedArray, N, MAX))

 

2 算法过程演示

如果显示不正常,请戳这里

 

3 复杂度分析

最坏、最优和平均的时间复杂度都为\({\displaystyle O(n+k)}\),空间复杂度为\({\displaystyle O(n+k)}\)

 

4 稳定性

计数排序是稳定的。

 

5 应用

优化前向星

前向星不需要像邻接表那样用指针指向下一条边,还是挺方便的。但是,由于前向星初始化需要快排一遍,相对邻接表要慢许多。考虑到一般图论题点数都不会很大,所以可以改为采用计数排序的思想对前向星进行排序。

一开始读入时,先算出每个点出去的边有多少条,然后计算出排序后每个点出去的第一条边位置应在哪里,最后把全部边扫一遍放到排序后应在的位置就好了。

这样排序的话初始化的时间复杂度就降到了\(O(m)\),总体时间并不会逊色于邻接表。

优化后缀数组的倍增算法

如果用快速排序,该算法的复杂度为\(O(nlog^2n)\)。改用计数排序后,复杂度降为\(O(nlogn)\)

 

6 参考文档

(全文完)

Tags