仿站多少钱一套,微信crm管理系统免费,加强国资集团网站建设,wordpress建立php站点地图前文说到#xff0c;19591959 年 77 月#xff0c;希尔排序通过交换非相邻元素#xff0c;打破了O(n^2)的魔咒#xff0c;使得排序算法的时间复杂度降到了O(nlogn) 级#xff0c;此后的快速排序、堆排序都是基于这样的思想#xff0c;所以他们的时间复杂度都是 O(nlogn)。… 前文说到19591959 年 77 月希尔排序通过交换非相邻元素打破了O(n^2)的魔咒使得排序算法的时间复杂度降到了O(nlogn) 级此后的快速排序、堆排序都是基于这样的思想所以他们的时间复杂度都是 O(nlogn)。 那么排序算法最好的时间复杂度就是 O(nlogn) 吗是否有比 O(nlogn) 级还要快的排序算法呢?能否在O(n^2)的时间复杂度下完成排序呢 事实上O(n) 级的排序算法存在已久但他们只能用于特定的场景。 计数排序就是一种时间复杂度为 O(n) 的排序算法该算法于 1954 年由 Harold H. Seward 提出。在对一定范围内的整数排序时它的复杂度为 O(nk)其中 k 是整数的范围大小。
伪计数排序 举个例子我们需要对一列数组排序这个数组中每个元素都是[1,9] 区间内的整数。那么我们可以构建一个长度为 9 的数组用于计数计数数组的下标分别对应区间内的 9 个整数。然后遍历待排序的数组将区间内每个整数出现的次数统计到计数数组中对应下标的位置。最后遍历计数数组将每个元素输出输出的次数就是对应位置记录的次数。
算法实现如下以 [1,9]为例
public static void countingSort9(int[] arr) {// 建立长度为 9 的数组下标 0~8 对应数字 1~9int[] counting new int[9];// 遍历 arr 中的每个元素for (int element : arr) {// 将每个整数出现的次数统计到计数数组中对应下标的位置counting[element - 1];}int index 0;// 遍历计数数组将每个元素输出for (int i 0; i 9; i) {// 输出的次数就是对应位置记录的次数while (counting[i] ! 0) {arr[index] i 1;counting[i]--;}}
} 算法非常简单但这里的排序算法 并不是 真正的计数排序。因为现在的实现有一个非常大的弊端排序完成后arr 中记录的元素已经不再是最开始的那个元素了他们只是值相等但却不是同一个对象。 在纯数字排序中这个弊端或许看起来无伤大雅但在实际工作中这样的排序算法几乎无法使用。因为被排序的对象往往都会携带其他的属性但这份算法将被排序对象的其他属性都丢失了。 就好比业务部门要求我们将 1 号商品2 号商品3 号商品4 号商品按照价格排序它们的价格分别为 8 元、6 元6 元9 元。 我们告诉业务部门排序完成后价格为 6 元、 6 元、8 元9元但不知道这些价格对应哪个商品。这显然是不可接受的。
伪计数排序 2.0 对于这个问题我们很容易想到一种解决方案在统计元素出现的次数时同时把真实的元素保存到列表中输出时从列表中取真实的元素。算法实现如下
public static void countingSort9(int[] arr) {// 建立长度为 9 的数组下标 0~8 对应数字 1~9int[] counting new int[9];// 记录每个下标中包含的真实元素使用队列可以保证排序的稳定性HashMapInteger, QueueInteger records new HashMap();// 遍历 arr 中的每个元素for (int element : arr) {// 将每个整数出现的次数统计到计数数组中对应下标的位置counting[element - 1];if (!records.containsKey(element - 1)) {records.put(element - 1, new LinkedList());}records.get(element - 1).add(element);}int index 0;// 遍历计数数组将每个元素输出for (int i 0; i 9; i) {// 输出的次数就是对应位置记录的次数while (counting[i] ! 0) {// 输出记录的真实元素arr[index] records.get(i).remove();counting[i]--;}}
} 在这份代码中我们通过队列来保存真实的元素计数完成后将队列中真实的元素赋到 arr 列表中这就解决了信息丢失的问题并且使用队列还可以保证排序算法的稳定性。
但是这也不是 真正的计数排序计数排序中使用了一种更巧妙的方法解决这个问题。
真正的计数排序 举个例子班上有 10 名同学他们的考试成绩分别是7,8,9,7,6,7,6,8,6,6他们需要按照成绩从低到高坐到 09 共 10 个位置上。 用计数排序完成这一过程需要以下几步
第一步仍然是计数统计出4 名同学考了 6 分3 名同学考了 7 分2 名同学考了 8 分1 名同学考了 9 分然后从头遍历数组第一名同学考了 77 分共有 44 个人比他分数低所以第一名同学坐在 44 号位置也就是第 55 个位置第二名同学考了 88 分共有 77 个人44 33比他分数低所以第二名同学坐在 77 号位置第三名同学考了 99 分共有 99 个人44 33 22比他分数低所以第三名同学坐在 99 号位置第四名同学考了 7 分共有 4 个人比他分数低并且之前已经有一名考了 7 分的同学坐在了 4 号位置所以第四名同学坐在 5 号位置。...依次完成整个排序。 区别就在于计数排序并不是把计数数组的下标直接作为结果输出而是通过计数的结果计算出每个元素在排序完成后的位置然后将元素赋值到对应位置。
代码如下
public static void countingSort9(int[] arr) {// 建立长度为 9 的数组下标 0~8 对应数字 1~9int[] counting new int[9];// 遍历 arr 中的每个元素for (int element : arr) {// 将每个整数出现的次数统计到计数数组中对应下标的位置counting[element - 1];}// 记录前面比自己小的数字的总数int preCounts 0;for (int i 0; i counting.length; i) {int temp counting[i];// 将 counting 计算成当前数字在结果中的起始下标位置。位置 前面比自己小的数字的总数。counting[i] preCounts;// 当前的数字比下一个数字小累计到 preCounts 中preCounts temp;}int[] result new int[arr.length];for (int element : arr) {// counting[element - 1] 表示此元素在结果数组中的下标int index counting[element - 1];result[index] element;// 更新 counting[element - 1]指向此元素的下一个下标counting[element - 1];}// 将结果赋值回 arrfor (int i 0; i arr.length; i) {arr[i] result[i];}
}
首先我们将每位元素出现的次数记录到 counting 数组中。
然后将 counting[i] 更新为数字 i 在最终排序结果中的起始下标位置。这个位置等于前面比自己小的数字的总数。
例如本例中考 7 分的同学前面有 4 个比自己分数低的同学所以 7 对应的下标为 4。
这一步除了使用 temp 变量这种写法以外还可以通过多做一次减法省去 temp 变量
// 记录前面比自己小的数字的总数
int preCounts 0;
for (int i 0; i counting.length; i) {// 当前的数字比下一个数字小累计到 preCounts 中preCounts counting[i];// 将 counting 计算成当前数字在结果中的起始下标位置。位置 前面比自己小的数字的总数。counting[i] preCounts - counting[i];
}
接下来从头访问 arr 数组根据 counting 中计算出的下标位置将 arr 的每个元素直接放到最终位置上然后更新 counting 中的下标位置。这一步中的 index 变量也是可以省略的。
最后将 result 数组赋值回 arr完成排序。
这就是计数排序的思想我们还剩下最后一步那就是根据 arr 中的数字范围计算出计数数组的长度。使得计数排序不仅仅适用于 [1,9]代码如下
public static void countingSort(int[] arr) {// 判空及防止数组越界if (arr null || arr.length 1) return;// 找到最大值最小值int max arr[0];int min arr[0];for (int i 1; i arr.length; i) {if (arr[i] max) max arr[i];else if (arr[i] min) min arr[i];}// 确定计数范围int range max - min 1;// 建立长度为 range 的数组下标 0~range-1 对应数字 min~maxint[] counting new int[range];// 遍历 arr 中的每个元素for (int element : arr) {// 将每个整数出现的次数统计到计数数组中对应下标的位置这里需要将每个元素减去 min才能映射到 0range-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[arr.length];for (int element : arr) {// counting[element - min] 表示此元素在结果数组中的下标result[counting[element - min]] element;// 更新 counting[element - min]指向此元素的下一个下标counting[element - min];}// 将结果赋值回 arrfor (int i 0; i arr.length; i) {arr[i] result[i];}
}
这就是完整的计数排序算法。
倒序遍历的计数排序
计数排序还有一种写法在计算元素在最终结果数组中的下标位置这一步不是计算初始下标位置而是计算最后一个下标位置。最后倒序遍历 arr 数组逐个将 arr 中的元素放到最终位置上。
代码如下
public static void countingSort(int[] arr) {// 防止数组越界if (arr null || arr.length 1) return;// 找到最大值最小值int max arr[0];int min arr[0];for (int i 1; i arr.length; i) {if (arr[i] max) max arr[i];else if (arr[i] min) min arr[i];}// 确定计数范围int range max - min 1;// 建立长度为 range 的数组下标 0~range-1 对应数字 min~maxint[] counting new int[range];// 遍历 arr 中的每个元素for (int element : arr) {// 将每个整数出现的次数统计到计数数组中对应下标的位置这里需要将每个元素减去 min才能映射到 0range-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[arr.length];// 从后往前遍历数组通过 counting 中记录的下标位置将 arr 中的元素放到 result 数组中for (int i arr.length - 1; i 0; i--) {// counting[arr[i] - min] 表示此元素在结果数组中的下标result[counting[arr[i] - min]] arr[i];// 更新 counting[arr[i] - min]指向此元素的前一个下标counting[arr[i] - min]--;}// 将结果赋值回 arrfor (int i 0; i arr.length; i) {arr[i] result[i];}
}
两种算法的核心思想是一致的并且都是稳定的。第一种写法理解起来简单一些第二种写法在性能上更好一些。
在计算下标位置时不仅计算量更少还省去了 preCounts 这个变量。在《算法导论》一书中便是采用的此种写法。
实际上这个算法最后不通过倒序遍历也能得到正确的排序结果但这里只有通过倒序遍历的方式才能保证计数排序的稳定性。
时间复杂度 空间复杂度
从计数排序的实现代码中可以看到每次遍历都是进行 n 次或者 k 次所以计数排序的时间复杂度为 O(nk)k 表示数据的范围大小。
用到的空间主要是长度为 k 的计数数组和长度为 n 的结果数组所以空间复杂度也是 O(nk)。
需要注意的是一般我们分析时间复杂度和空间复杂度时常数项都是忽略不计的。但计数排序的常数项可能非常大以至于我们无法忽略。不知你是否注意到计数排序的一个非常大的隐患比如我们想要对这个数组排序
int[] arr new int[]{1, Integer.MAX_VALUE};
尽管它只包含两个元素但数据范围是 [1,2^31]我们知道 java 中 int 占 4 个字节一个长度为 2^31次方的 int 数组大约会占 8G 的空间。如果使用计数排序仅仅排序这两个元素声明计数数组就会占用超大的内存甚至导致 OutOfMemory 异常。
所以计数排序只适用于数据范围不大的场景。例如对考试成绩排序就非常适合计数排序如果需要排序的数字中存在一位小数可以将所有数字乘以 10再去计算最终的下标位置。
