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

概念:

归并排序Merge Sort 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的典型应用。 它指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。归并排序有多路归并排序、两路归并排序 , 可用于内排序,也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。

原理:

  1. 把 n 个记录看成 n 个长度为 l 的有序子表
  2. 进行两两归并使记录关键字有序,得到 n/2 个长度为 2 的有序子表
  3. 重复第 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++];
            }
        }
    }

算法系列

冒泡排序 选择排序 直接插入排序 二分插入排序 希尔排序 堆排序 归并排序

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券