计数排序

计数排序（Counting Sort）

基于比较的排序算法的最优下界为 $\Omega(nlogn)$ 。计数排序是一种不基于比较的排序算法，而是利用数组下标来确定元素的正确位置。

遍历数列，将每一个整数按照其值对号入座，对应数组下标的元素加1。数组的每一个下标位置的值，代表了数列中对应整数出现的次数。有了这个统计结果，直接遍历数组，输出数组元素的下标值，元素的值是多少就输出多少次。

从功能角度，这个算法可以实现整数的排序，但是也存在一些问题。如果只以最大值来决定统计数组的长度并不严谨，例如数列{95, 94, 91, 98, 99, 90, 99, 93, 91, 92}，这个数列的最大值是99，但最小值是90。如果创建长度为100的数组，前面的从0到89的空间位置都浪费了。

因此，不应再以数列的max + 1作为统计数组的长度，而是以数列max - min + 1作为统计数组的长度。同时，数列的最小值作为一个偏移量，用于统计数组的对号入座。

计数排序适用于一定范围的整数排序，在取值范围不是很大的情况下，它的性能甚至快过那些 $O(nlogn)$ 的排序算法。

计数排序

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

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

int *counting_sort(int *arr, int n) {
    if (n == 0) {
        return arr;
    }

    int max_val = arr[0];
    int min_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
        if (arr[i] < min_val) {
            min_val = arr[i];
        }
    }

    int range = max_val - min_val + 1;
    int *counts = (int *)calloc(range, sizeof(int));
    if (counts == NULL) {
        exit(1);
    }

    for (int i = 0; i < n; i++) {
        counts[arr[i] - min_val]++;
    }

    int cnt = 0;
    for (int i = 0; i < range; i++) {
        while (counts[i]--) {
            arr[cnt] = i + min_val;
            cnt++;
        }
    }

    free(counts);
    return arr;
}

int main() {
    int arr[] = {95, 94, 91, 98, 99, 90, 99, 93, 91, 92};
    int n = sizeof(arr) / sizeof(arr[0]);

    counting_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

令 $k=max-min+1$ ，此实现的时间复杂度为 $O(n+k)$ ，空间复杂度为 $O(k)$ 。它只重建整数值，不能直接保留附属记录的稳定次序。

题目

原稿中min=90，值95应该增加哪个计数格？

题目

只排序少量整数，但max−min非常大，计数排序可能有什么问题？

对[-2,1,-2,0,3,1]使用计数排序。写出min、max、k，每次计数后的counts，以及逐个重建的最终数组。

计数排序（Counting Sort）

基于比较的排序算法的最优下界为

\Omega(nlogn)

。计数排序是一种不基于比较的排序算法，而是利用数组下标来确定元素的正确位置。

计数排序适用于一定范围的整数排序，在取值范围不是很大的情况下，它的性能甚至快过那些

O(nlogn)

的排序算法。

计数排序

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

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

int *counting_sort(int *arr, int n) {
    if (n == 0) {
        return arr;
    }

    int max_val = arr[0];
    int min_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
        if (arr[i] < min_val) {
            min_val = arr[i];
        }
    }

    int range = max_val - min_val + 1;
    int *counts = (int *)calloc(range, sizeof(int));
    if (counts == NULL) {
        exit(1);
    }

    for (int i = 0; i < n; i++) {
        counts[arr[i] - min_val]++;
    }

    int cnt = 0;
    for (int i = 0; i < range; i++) {
        while (counts[i]--) {
            arr[cnt] = i + min_val;
            cnt++;
        }
    }

    free(counts);
    return arr;
}

int main() {
    int arr[] = {95, 94, 91, 98, 99, 90, 99, 93, 91, 92};
    int n = sizeof(arr) / sizeof(arr[0]);

    counting_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

令 $k=max-min+1$ ，此实现的时间复杂度为 $O(n+k)$ ，空间复杂度为 $O(k)$ 。它只重建整数值，不能直接保留附属记录的稳定次序。

题目

原稿中min=90，值95应该增加哪个计数格？

题目

只排序少量整数，但max−min非常大，计数排序可能有什么问题？

对[-2,1,-2,0,3,1]使用计数排序。写出min、max、k，每次计数后的counts，以及逐个重建的最终数组。

计数排序

计数排序

计数排序（Counting Sort）

计数：按偏移量统计，再按值重建

知识测验

知识测验

用偏移处理负整数

计数排序

计数排序

计数排序（Counting Sort）

计数：按偏移量统计，再按值重建

知识测验

知识测验

用偏移处理负整数