本文转载自微信公众号「贝塔学JAVA」,作者Silently9527 。转载本文请联系贝塔学JAVA公众号。
前言
本篇我们谈一种基于归并操作完成排序的算法。
归并排序算法思路
要将一个数组排序,可以先将数组分为两个数组分别排序,然后再将结果归并在一起,重复递归这个过程,直到数组整体有序,这就是归并排序的算法思路。
归并排序的优点是它能够保证任意长度为N的数组排序所需的时间与 NlogN 成正比,这个优点是初级排序无法达到的。
缺点是因为归并操作需要引入额外的数组,额外的空间与N成正比
原地归并实现
在实现归并排序之前,我们需要先完成两个有序数组的归并操作,即将两个有序的数组合并成一个有序的数组;
- public class MergeSort implements SortTemplate {
- private Comparable[] aux;
- @Override
- public void sort(Comparable[] array) {
- //待实现
- }
- private void merge(Comparable[] a, int lo, int mid, int hi) {
- for (int i = lo; i <= hi; i++) {
- aux[i] = a[i];
- }
- int i = lo, j = mid + 1;
- for (int k = lo; k <= hi; k++) {
- if (i > mid) {
- a[k] = aux[j++];
- } else if (j > hi) {
- a[k] = aux[i++];
- } else if (less(aux[i], aux[j])) {
- a[k] = aux[i++];
- } else {
- a[k] = aux[j++];
- }
- }
- }
- }
自顶向下的归并排序
基于分而治之的思想,大的数组排序,先递归拆分成小的数组,保证小的数组有序再归并,直到整个数组有序,这个操作就是自顶向下的归并排序
- public class MergeSort implements SortTemplate {
- private Comparable[] aux;
- @Override
- public void sort(Comparable[] array) {
- aux = new Comparable[array.length];
- doSort(array, 0, array.length - 1);
- }
- private void doSort(Comparable[] array, int lo, int hi) {
- if (lo >= hi) {
- return;
- }
- int mid = (hi - lo) / 2 + lo;
- doSort(array, lo, mid);
- doSort(array, mid + 1, hi);
- merge(array, lo, mid, hi);
- }
- private void merge(Comparable[] a, int lo, int mid, int hi) {
- //省略
- }
- }
以上代码是标准的递归归并排序操作,但是经过仔细思考之后,该算法还有可以优化的地方
「测试数组是否已经有序」;如果a[mid]<=a[mid+1],那么我们就可以跳过merge方法,减少merge操作;修复之后的doSort方法
- private void doSort(Comparable[] array, int lo, int hi) {
- if (lo >= hi) {
- return;
- }
- int mid = (hi - lo) / 2 + lo;
- doSort(array, lo, mid);
- doSort(array, mid + 1, hi);
- if (array[mid].compareTo(array[mid + 1]) >= 0) {
- merge(array, lo, mid, hi);
- }
- }
「对于小规模的数组可以是用插入排序」;对于小规模的数组使用归并排序会增加递归调用栈,所以我们可以考虑使用插入排序来处理子数组的排序
- private void doSort(Comparable[] array, int lo, int hi) {
- if (lo >= hi) {
- return;
- }
- if (hi - lo < 5) { //测试,小于5就使用插入排序
- insertionSort(array, lo, hi);
- return;
- }
- int mid = (hi - lo) / 2 + lo;
- doSort(array, lo, mid);
- doSort(array, mid + 1, hi);
- if (less(array[mid + 1], array[mid])) {
- merge(array, lo, mid, hi);
- }
- }
- //插入排序
- private void insertionSort(Comparable[] array, int lo, int hi) {
- for (int i = lo; i <= hi; i++) {
- for (int j = i; j > lo && less(array[j], array[j - 1]); j--) {
- exch(array, j, j - 1);
- }
- }
- }
「节省复制元素到辅助数组的时间」;要实现该操作较麻烦,需要在每一层递归的时候交换输入数据和输出数组的角色;修改之后的完整代码如下:
- public class MergeSort implements SortTemplate {
- private Comparable[] aux;
- @Override
- public void sort(Comparable[] array) {
- aux = array.clone();
- doSort(aux, array, 0, array.length - 1);
- }
- private void doSort(Comparable[] src, Comparable[] dest, int lo, int hi) {
- if (lo >= hi) {
- return;
- }
- if (hi - lo < 5) { //测试,小于5就使用插入排序
- insertionSort(dest, lo, hi);
- return;
- }
- int mid = (hi - lo) / 2 + lo;
- doSort(dest, src, lo, mid);
- doSort(dest, src, mid + 1, hi);
- if (less(src[mid + 1], src[mid])) {
- merge(src, dest, lo, mid, hi);
- }
- }
- //插入排序
- private void insertionSort(Comparable[] array, int lo, int hi) {
- for (int i = lo; i <= hi; i++) {
- for (int j = i; j > lo && less(array[j], array[j - 1]); j--) {
- exch(array, j, j - 1);
- }
- }
- }
- private void merge(Comparable[] src, Comparable[] dest, int lo, int mid, int hi) {
- int i = lo, j = mid + 1;
- for (int k = lo; k <= hi; k++) {
- if (i > mid) {
- dest[k] = src[j++];
- } else if (j > hi) {
- dest[k] = src[i++];
- } else if (less(src[i], src[j])) {
- dest[k] = src[i++];
- } else {
- dest[k] = src[j++];
- }
- }
- }
- }
每一层递归操作都会让子数组有序,但是子数组可能是aux[lo..hi]也有可能是a[lo..hi];由于第一次调用doSort传入的是src=aux,dest=array,所以递归最后的结果一定是输入到了array中,保证了array整体排序完成
自底向上的归并排序
实现归并算法还有另一种思路,就是先归并哪些小的数组,然后再成对归并得到子数组,直到整个数组有序
- public class MergeSort implements SortTemplate {
- private Comparable[] aux;
- @Override
- public void sort(Comparable[] array) {
- int length = array.length;
- aux = new Comparable[length];
- for (int sz = 1; sz < length; sz += sz) {
- for (int i = 0; i < length - sz; i += 2 * sz) {
- merge(array, i, i + sz - 1, Math.min(i + 2 * sz - 1, length - 1));
- }
- }
- }
- private void merge(Comparable[] a, int lo, int mid, int hi) {
- for (int i = lo; i <= hi; i++) {
- aux[i] = a[i];
- }
- int i = lo, j = mid + 1;
- for (int k = lo; k <= hi; k++) {
- if (i > mid) {
- a[k] = aux[j++];
- } else if (j > hi) {
- a[k] = aux[i++];
- } else if (less(aux[i], aux[j])) {
- a[k] = aux[i++];
- } else {
- a[k] = aux[j++];
- }
- }
- }
- }
hk 域名 哪里注册? .hk域名 在国内是可以注册的,只要提供了.hk 域名注册 服务...
描述 你正在和你的朋友玩 猜数字 (Bulls and Cows)游戏:你写下一个数字让你的朋...
背景 2020年9月16日 Snowflake成功IPO 交易首日市场估值达到704亿美元 募集资金3...
TOP云 (west.cn)1月25日消息,近日,功夫贷宣布获得4000万人民币A轮融资,本轮...
约束与限制 只有运行中的云服务器云主机才允许用户登录。 Windows操作系统用户名...
本文介绍了北京慧达天下如何使用运维编排OOS提高发布效率。 公司介绍 公司名称:...
我们知道效能提升 就是要应用系统方法实践和工具 通过它们改进技术、工程能力和...
有很多人在听说大数据之后,会开始纠结JAVA与大数据的区别,甚至还在纠结Java和...
本文由网易云音乐实时计算平台研发工程师岳猛分享,主要从以下四个部分将为大家...
作者 | 亮言 来源 | 阿里技术公众号 一 背景 订单状态流转是交易系统的最为核心...