关于java:死磕归并排序算法

39次阅读

共计 3992 个字符，预计需要花费 10 分钟才能阅读完成。

本文已被 Github 仓库收录 https://github.com/silently9527/JavaCore

程序员罕用的 IDEA 插件：https://github.com/silently9527/ToolsetIdeaPlugin

齐全开源的淘客我的项目：https://github.com/silently9527/mall-coupons-server

微信公众号：贝塔学 Java

前言

在上一篇《常见的高级排序算法，这次全搞懂》，次要谈了罕用的高级算法，这些算法的工夫复杂度都是 O(n²)，这些算法无奈解决大量数据；本篇咱们谈一种基于归并操作实现排序的算法。

归并排序算法思路

要将一个数组排序，能够先将数组分为两个数组别离排序，而后再将后果归并在一起，反复递归这个过程，直到数组整体有序，这就是归并排序的算法思路。

归并排序的长处是它可能保障任意长度为 N 的数组排序所需的工夫与 NlogN 成正比，这个长处是高级排序无奈达到的。

毛病是因为归并操作须要引入额定的数组，额定的空间与 N 成正比

原地归并实现

在实现归并排序之前，咱们须要先实现两个有序数组的归并操作，行将两个有序的数组合并成一个有序的数组；

  • 在此过程中咱们须要引入一个辅助数组；
  • 定义的办法签名为 merge(a, lo, mid, hi)，这个办法将数组 a[lo..mid]与 a[mid..hi]归并成一个有序的数组，后果寄存到 a[lo..mid]中；
  • 该办法中须要应用的上一篇中的公共函数 less，参考上一篇文章《常见的高级排序算法，这次全搞懂》
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) {// 省略}

}

以上代码是规范的递归归并排序操作，然而通过认真思考之后，该算法还有能够优化的中央

  1. 测试数组是否曾经有序；如果 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);
    }
}
  1. 对于小规模的数组能够是用插入排序；对于小规模的数组应用归并排序会减少递归调用栈，所以咱们能够思考应用插入排序来解决子数组的排序
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);
        }
    }
}
  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++];
            }
        }
    }

}

最初（点关注，不迷路）

文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。

最初，写作不易，请不要白嫖我哟 ，心愿敌人们能够 点赞评论关注 三连，因为这些就是我分享的全副能源起源????

文中所有源码已放入到了 github 仓库 https://github.com/silently9527/JavaCore

正文完
java
发表至： java
2021-03-01
 0
关于java:初识HTTP11
关于java:cms垃圾回收器
力扣LeetCode88
git-切换远程仓库地址