Java常见排序算法详解——归并排序

Demo_Yang

发布于 2019-04-18 20:28:18

1K0

发布于 2019-04-18 20:28:18

文章被收录于专栏：yang0rangeyang0range

概念：

归并排序Merge Sort

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的典型应用。

它指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。

原理：

把 n 个记录看成 n 个长度为 l 的有序子表
进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表
重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。图解：列如我们有个数组29 4 11 10 5 7 99 66 用归并排序按照从小到大排序首先，我们先将数组分为长度为2的子数组,然后对每个子数组进行排序

[29  4]  [11  10]  [5  7]  [99  66]
   ↓        ↓         ↓       ↓
[4  29]  [10 11]   [5  7]  [66 99]

然后再两两合并

[4 29 10 11]  [5 7 66 99]
      ↓             ↓
[4 10 11 29]  [5 7 66 99]

最后，再将这两个子数组合并

[4 10 11 29 5 7 66 99]
            ↓
[4 5 7 10 11 29 66 99]

代码实现：

 public  void mergesort() {
        int[] orderedArr = new int[array.length];
        for (int i = 2; i < array.length * 2; i *= 2) {
            for (int j = 0; j < (array.length + i - 1) / i; j++) {
                int left = i * j;
                int mid = left + i / 2 >= array.length ? (array.length - 1) : (left + i / 2);
                int right = i * (j + 1) - 1 >= array.length ? (array.length - 1) : (i * (j + 1) - 1);
                int start = left, l = left, m = mid;
                while (l < mid && m <= right) {
                    if (array[l] < array[m]) {
                        orderedArr[start++] = array[l++];
                    } else {
                        orderedArr[start++] = array[m++];
                    }
                }
                while (l < mid)
                    orderedArr[start++] = array[l++];
                while (m <= right)
                    orderedArr[start++] = array[m++];
            }
        }
    }