搜 索

排序算法丨计数排序

  • 2.7k阅读
  • 2021年05月23日
  • 4评论
首页 / 默认分类 / 正文

前言

希尔排序通过交换非相邻元素,打破了 O(n2) 的魔咒,使得排序算法的时间复杂度降到了 O(nlogn) 级,此后的快速排序、堆排序都是基于这样的思想,所以他们的时间复杂度都是 O(nlogn)。

那么,排序算法最好的时间复杂度就是 O(nlogn)吗?

事实上,存在 O(n)级的排序算法,但只能用于特定的场景。
计数排序(Counting Sort),就是一种时间复杂度为 O(n)的排序算法,该算法于 1954年由 Harold H.Seward 提出。
在对一定范围内的整数排序时,它的复杂度为 Ο(n+k)(其中 k 是整数的范围大小)。

排序思路

这种排序算法不是基于比较元素大小的,而是利用数组下标来确定元素的正确位置。
例如,需要对一列数组排序,这个数组中每个元素都是[0, 10]区间内的整数,如果是基于元素比较的排序,就需要比较整数大小进行调整位置。

  1. 我们可以根据这个数组的取值范围,构建一个长度为 11 的数组用于计数,计数数组的下标分别对应区间内的 11 个整数。
  2. 然后遍历待排序的数组,将区间内每个整数出现的次数统计到计数数组中对应下标的位置。
  3. 最后遍历计数数组,将每个元素输出,输出的次数就是对应位置记录的次数。

对应的代码实现

public static int[] countSort(int[] array) {
    // 1.得到数列的最大值
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }

    // 2.根据数列最大值确定统计数组的长度:有个缺点
    int[] countArray = new int[max + 1];

    // 3.遍历数列,填充统计数组
    for (int i = 0; i < array.length; i++) {
        countArray[array[i]]++;
    }

    //4.遍历统计数组,输出结果
    int index = 0;
    int[] sortedArray = new int[array.length];
    for (int i = 0; i < countArray.length; i++) {
        for (int j = 0; j < countArray[i]; j++) {
            sortedArray[index++] = i;
        }
    }
    return sortedArray;
}

改进

虽然这种思路非常简单,但这样的排序算法并不是真正的计数排序

改进1

以待排序数列的最大值 + 1 作为统计数组的长度,并不严谨,可能会造成空间浪费。
例如,输入的数列中最大值为 1000,但是最小值为 990;如果新建一个长度为 1001 的统计数组,那么从 0 到 989 的空间都没用上。
所以,使用数列中元素大小的极值差(最大值 - 最小值) + 1 作为统计数组的长度。
同时,数列的最小值作为一个偏移量,用于统计数组的对号入座,也就是说,元素A对应的统计数组下标是 A - min(min 为最小值)。

public static int[] countSort2(int[] array) {
    // 1.得到数列的最大值与最小值
    int max = array[0], min = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
        if (array[i] < min){
            min = array[i];
        }
    }

    // 2.根据数列的取值范围确定统计数组的长度:避免浪费空间
    int[] countArray = new int[max - min + 1];

    // 3.遍历数列,填充统计数组
    for (int i = 0; i < array.length; i++) {
        // 偏移量等于数列的最小值
        countArray[array[i] - min]++;
    }

    //4.遍历统计数组,输出结果
    int index = 0;
    int[] sortedArray = new int[array.length];
    for (int i = 0; i < countArray.length; i++) {
        for (int j = 0; j < countArray[i]; j++) {
            sortedArray[index++] = i;
        }
    }
    return sortedArray;
}

该进2

还有一个非常大的弊端:排序完成后,数组中记录的元素已经不再是最开始的那个元素了,它们只是数值相等,但却不是同一个对象。
所以,如果是单纯的纯数字排序,这种做法没问题,但在实际工作中,这样的排序算法几乎无法使用。
因为被排序的对象往往都会携带其他的属性,但这份算法将被排序对象的其他属性都丢失了。
例如,老师对学生们的考试成绩排序,只知道排序的结果,不知道分数对应的学生姓名(如果分数是唯一的还能知道,分数相同的就不知道了)。

这种情况,可以使用哈希表来解决,但这也不是真正的计数排序。

真正的计数排序

计数排序并不是把计数数组的下标直接作为结果输出,而是通过计数的结果,计算出每个元素在排序完成后的位置,然后将元素赋值到对应位置。

public static void countSort3(int[] array) {
    // 判空及防止数组越界
    if (array == null || array.length <= 1) {
        return;
    }

    // 找到最大值,最小值
    int max = array[0];
    int min = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        } else if (array[i] < min) {
            min = array[i];
        }
    }
    // 确定计数范围:元素极值 + 1
    int range = max - min + 1;
    // 建立长度为 range 的数组,下标 0~range-1 对应数字 min~max
    int[] counting = new int[range];
    // 遍历 arr 中的每个元素
    for (int element : array) {
        // 将每个整数出现的次数统计到计数数组中对应下标的位置
        // 这里需要将每个元素减去 min,才能映射到 0~range-1 范围内
        counting[element - min]++;
    }
    // 记录前面比自己小的数字的总数
    int preCounts = 0;
    for (int i = 0; i < range; i++) {
        // 当前的数字比下一个数字小,累计到 preCounts 中
        preCounts += counting[i];
        // 将 counting 计算成当前数字在结果中的起始下标位置。位置 = 前面比自己小的数字的总数。
        counting[i] = preCounts - counting[i];
    }
    int[] result = new int[array.length];
    for (int element : array) {
        // counting[element - min] 表示此元素在结果数组中的下标
        result[counting[element - min]] = element;
        // 更新 counting[element - min],指向此元素的下一个下标
        counting[element - min]++;
    }
    // 将结果赋值回 arr
    for (int i = 0; i < array.length; i++) {
        array[i] = result[i];
    }
}

倒序遍历的计数排序

计数排序还有一种写法,在计算元素在最终结果数组中的下标位置这一步,不是计算初始下标位置,而是计算最后一个下标位置。
最后倒序遍历 arr 数组,逐个将 arr 中的元素放到最终位置上。

public static void countSort4(int[] array) {
    // 防止数组越界
    if (array == null || array.length <= 1) {
        return;
    }
    // 找到最大值,最小值
    int max = array[0];
    int min = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        } else if (array[i] < min) {
            min = array[i];
        }
    }
    // 确定计数范围
    int range = max - min + 1;
    // 建立长度为 range 的数组,下标 0~range-1 对应数字 min~max
    int[] counting = new int[range];
    // 遍历 arr 中的每个元素
    for (int element : array) {
        // 将每个整数出现的次数统计到计数数组中对应下标的位置,
        // 这里需要将每个元素减去 min,才能映射到 0~range-1 范围内
        counting[element - min]++;
    }
    // 每个元素在结果数组中的最后一个下标位置 = 前面比自己小的数字的总数 + 自己的数量 - 1。
    // 我们将 counting[0] 先减去 1,后续 counting 直接累加即可
    counting[0]--;
    for (int i = 1; i < range; i++) {
        // 将 counting 计算成当前数字在结果中的最后一个下标位置。
        // 位置 = 前面比自己小的数字的总数 + 自己的数量 - 1
        // 由于 counting[0] 已经减了 1,所以后续的减 1 可以省略。
        counting[i] += counting[i - 1];
    }
    int[] result = new int[array.length];
    // 从后往前遍历数组,通过 counting 中记录的下标位置,将 arr 中的元素放到 result 数组中
    for (int i = array.length - 1; i >= 0; i--) {
        // counting[arr[i] - min] 表示此元素在结果数组中的下标
        result[counting[array[i] - min]] = array[i];
        // 更新 counting[arr[i] - min],指向此元素的前一个下标
        counting[array[i] - min]--;
    }
    // 将结果赋值回 arr
    for (int i = 0; i < array.length; i++) {
        array[i] = result[i];
    }
}

两种算法的核心思想是一致的,并且都是稳定的。第一种写法理解起来简单一些,第二种写法在性能上更好一些。
在计算下标位置时,不仅计算量更少,还省去了 preCounts 这个变量。在《算法导论》一书中,便是采用的此种写法。
实际上,这个算法最后不通过倒序遍历也能得到正确的排序结果,但这里只有通过倒序遍历的方式,才能保证计数排序的稳定性。

动画演示

演示动画来自于Visualgo

计数排序

复杂度分析

从计数排序的实现代码中,可以看到,每次遍历都是进行 n 次或者 k 次,所以计数排序的时间复杂度为 O(n + k),k 表示数据的范围大小,快于任何比较排序算法。
用到的空间主要是长度为 k 的计数数组和长度为 n 的结果数组,所以空间复杂度也是 O(n + k)。
需要注意的是,一般我们分析时间复杂度和空间复杂度时,常数项都是忽略不计的。
但计数排序的常数项可能非常大,以至于我们无法忽略。

计数排序存在一个非常大的隐患,比如我们想要对这个数组排序:

int[] arr = new int[]{1, Integer.MAX_VALUE};

尽管它只包含两个元素,但数据范围是 [1, 231],我们知道 java 中 int 占 4 个字节,一个长度为 231次方的 int 数组大约会占 8G 的空间。
如果使用计数排序,仅仅排序这两个元素,声明计数数组就会占用超大的内存,甚至导致 OutOfMemory 异常。

所以,计数排序只适用于数据范围不大且数据分布比较密集的场景
此外,当数列元素不是整数,也不适用计数排序。

参考

程序员小灰
百度百科
LeetCode
打 赏
  • 支付宝
  • 微信
Alipay
WeChatPay
评论区
青益 2021年08月19日 14:06
回复 取消

友链头像用这个链接吧,我开防盗链了,以前那个头像你用不了
https://q1.qlogo.cn/g?b=qq&nk=1351856278&s=100

New
1 条回复
New
New 2021年08月22日 13:45
回复 取消

ok

青益 2021年08月01日 20:35
回复 取消

青益友链变更 www.oreo-me.cn,谢谢啦

New
1 条回复
New
New 2021年08月13日 18:18
回复 取消

已更换

avatar