1T数据快速排序！十种经典排序算法总结( 三 )
合并的过程是将两个指针指向两个子数组的首位元素 ， 两个元素进行比较 ， 较小的插入到一个temp数组中 ， 同时将该数组的指针右移一位 ， 继续比较该数组的第二个元素和另一个元素…重复这个过程 。 这样temp数组保存的便是这两个子数组排好序的结果 。 最后将temp数组复制回原数组的位置处即可 。
public int[] mergeSort(int[] array) {if (array == null || array.length < 2) {return array;}return mergeSort(array, 0, array.length - 1);}private int[] mergeSort(int[] array, int left, int right) {if (left < right) {//这里没有选择“(left + right) / 2”的方式 ， 是为了防止数据溢出int mid = left + ((right - left) >>> 1);// 拆分子数组mergeSort(array, left, mid);mergeSort(array, mid + 1, right);// 对子数组进行合并merge(array, left, mid, right);}return array;}private void merge(int[] array, int left, int mid, int right) {int[] temp = new int[right - left + 1];// p1和p2为需要对比的两个数组的指针 ， k为存放temp数组的指针int p1 = left, p2 = mid + 1, k = 0;while (p1 <= mid} else {temp[k++] = array[p2++];}}// 把剩余的数组直接放到temp数组中while (p1 <= mid) {temp[k++] = array[p1++];}while (p2 <= right) {temp[k++] = array[p2++];}// 复制回原数组for (int i = 0; i < temp.length; i++) {array[i + left] = temp[i];}}7 快速排序快速排序的核心是要有一个基准数据temp ， 一般取数组的第一个位置元素 。 然后需要有两个指针left和right ， 分别指向数组的第一个和最后一个元素 。
首先从right开始 ， 比较right位置元素和基准数据 。 如果大于等于 ， 则将right指针左移 ， 比较下一位元素；如果小于 ， 就将right指针处数据赋给left指针处（此时left指针处数据已保存进temp中） ， left指针+1 ， 之后开始比较left指针处数据 。
拿left位置元素和基准数据进行比较 。 如果小于等于 ， 则将left指针右移 ， 比较下一位元素；而如果大于就将left指针处数据赋给right指针处 ， right指针-1 ， 之后开始比较right指针处数据…重复这个过程 。
直到left和right指针相等时 ， 说明这一次比较过程完成 。 此时将先前存放进temp中的基准数据赋值给当前left和right指针共同指向的位置处 ， 即可完成这一次排序操作 。
之后递归排序基础数据的左半部分和右半部分 ， 递归的过程和上面讲述的过程是一样的 ， 只不过数组范围不再是原来的全部数组了 ， 而是现在的左半部分或右半部分 。 当全部的递归过程结束后 ， 最终结果即为排好序的结果 。
快速排序执行示意图：
文章插图
正如上面所说的 ， 一般取第一个元素作为基准数据 ， 但如果当前数据为从大到小排列好的数据 ， 而现在要按从小到大的顺序排列 ， 则数据分摊不均匀 ， 时间复杂度会退化为
文章插图
， 而不是正常情况下的
文章插图
。 此时采取一个优化手段 ， 即取最左边、最右边和最中间的三个元素的中间值作为基准数据 ， 以此来避免时间复杂度为
文章插图
的情况出现 ， 当然也可以选择更多的锚点或者随机选择的方式来进行选取 。
还有一个优化的方法是：像快速排序、归并排序这样的复杂排序方法在数据量大的情况下是比选择排序、冒泡排序和插入排序的效率要高的 ， 但是在数据量小的情况下反而要更慢 。 所以我们可以选定一个阈值 ， 这里选择为47（和源码中使用的一样） 。 当需要排序的数据量小于47时走插入排序 ， 大于47则走快速排序 。
推荐阅读
- 西部数据在CES 2021推出多款4TB容量的旗舰级SSD
- WhatsApp收集用户数据新政惹众怒，“删除WhatsApp”在土耳其上热搜
- “千店同开”引质量担忧，小米回应
- 未来想进入AI领域，该学习Python还是Java大数据开发
- 企业|技术快速迭代倒逼知识产权“贴身”服务，上海首家AI商标品牌指导站入驻徐汇西岸
- 黑客窃取250万个人数据 意大利运营商提醒用户尽快更换SIM卡
- 阳狮报告：4成受访者认为自己的数据比免费服务更有价值
- 中消协点名大数据网络杀熟 反对利用消费者个人数据画像
- 学习大数据是否需要学习JavaEE
- 意大利运营商Ho Mobile被曝数据泄露