1T数据快速排序！十种经典排序算法总结( 五 )
从上面的实现中可以看到 ， 计数排序仅适合数据跨度不大的场景 。 如果最大值和最小值之间的差距比较大 ， 生成的临时数组就会比较长 。 比如说一个数组是[2, 1, 3, 1000] ， 最小值是1 ， 最大值是1000 。 那么就会生成一个长度为1000的临时数组 ， 但是其中绝大部分的空间都是没有用的 ， 所以这就会导致空间复杂度变得很高 。
计数排序是稳定的排序算法 ， 但在上面的实现中并没有体现出这一点 ， 上面的实现没有维护相同元素之间的先后顺序 。 所以需要做些变换：将临时数组中从第二个元素开始 ， 每个元素都加上前一个元素的值 。 还是拿之前的[3, 3, 5, 2, 7, 4, 2]数组来举例 。 计完数后的临时数组为[2, 2, 1, 1, 0, 1] ， 此时做上面的变换 ， 每个数都累加前面的一个数 ， 结果为[2, 4, 5, 6, 6, 7] 。 这个时候临时数组的含义就不再是每个数出现的次数了 ， 此时记录的是每个数在最后排好序的数组中应该要存放的位置+1（如果有重复的就记录最后一个） 。 对于上面的待排序数组来说 ， 最后排好序的数组应该为[2, 2, 3, 3, 4, 5, 7] 。 也就是说 ， 此时各个数最后一次出现的索引位为：1, 3, 4, 5, 6 ， 分别都+1后就是2, 4, 5, 6, 7 ， 这不就是上面做过变换之后的数组吗？（没有出现过的数字不管它）所以 ， 此时从后往前遍历原数组中的每一个值 ， 将其减去最小值后 ， 找到其在变换后的临时数组中的索引 ， 也就是找到了最后排好序的数组中的位置了 。 当然 ， 每次找到临时数组中的索引后 ， 这个位置的数需要-1 。 这样如果后续有重复的该数字的话 ， 就会插入到当前位置的前一个位置了 。 由此也说明了遍历必须是从后往前遍历 ， 以此来维护相同数字之间的先后顺序 。
public int[] stableCountingSort(int[] array) {if (array == null || array.length < 2) {return array;}//记录待排序数组中的最大值int max = array[0];//记录待排序数组中的最小值int min = array[0];for (int i : array) {if (i > max) {max = i;}if (i < min) {min = i;}}int[] temp = new int[max - min + 1];//记录每个数出现的次数for (int i : array) {temp[i - min]++;}//将temp数组进行转换 ， 记录每个数在最后排好序的数组中应该要存放的位置+1（如果有重复的就记录最后一个）for (int j = 1; j < temp.length; j++) {temp[j] += temp[j - 1];}int[] sortedArray = new int[array.length];//这里必须是从后往前遍历 ， 以此来保证稳定性for (int i = array.length - 1; i >= 0; i--) {sortedArray[temp[array[i] - min] - 1] = array[i];temp[array[i] - min]--;}return sortedArray;}9 桶排序上面的计数排序在数组最大值和最小值之间的差值是多少 ， 就会生成一个多大的临时数组 ， 也就是生成了一个这么多的桶 ， 而每个桶中就只插入一个数据 。 如果差值比较大的话 ， 会比较浪费空间 。 那么我能不能在一个桶中插入多个数据呢？当然可以 ， 而这就是桶排序的思路 。 桶排序类似于哈希表 ， 通过一定的映射规则将数组中的元素映射到不同的桶中 ， 每个桶内进行内部排序 ， 最后将每个桶按顺序输出就行了 。 桶排序执行的高效与否和是否是稳定的取决于哈希散列的算法以及内部排序的结果 。 需要注意的是 ， 这个映射算法并不是常规的映射算法 ， 要求是每个桶中的所有数都要比前一个桶中的所有数都要大 。 这样最后输出的才是一个排好序的结果 。 比如说第一个桶中存1-30的数字 ， 第二个桶中存31-60的数字 ， 第三个桶中存61-90的数字...以此类推 。 下面给出一种实现：
public int[] bucketSort(int[] array) {if (array == null || array.length < 2) {return array;}//记录待排序数组中的最大值int max = array[0];//记录待排序数组中的最小值int min = array[0];for (int i : array) {if (i > max) {max = i;}if (i
推荐阅读
- 西部数据在CES 2021推出多款4TB容量的旗舰级SSD
- WhatsApp收集用户数据新政惹众怒，“删除WhatsApp”在土耳其上热搜
- “千店同开”引质量担忧，小米回应
- 未来想进入AI领域，该学习Python还是Java大数据开发
- 企业|技术快速迭代倒逼知识产权“贴身”服务，上海首家AI商标品牌指导站入驻徐汇西岸
- 黑客窃取250万个人数据 意大利运营商提醒用户尽快更换SIM卡
- 阳狮报告：4成受访者认为自己的数据比免费服务更有价值
- 中消协点名大数据网络杀熟 反对利用消费者个人数据画像
- 学习大数据是否需要学习JavaEE
- 意大利运营商Ho Mobile被曝数据泄露