算法——初级排序算法之归并排序

介绍

将两个有序的数组归并成一个更大的有序数组，这种算法叫归并排序

特点

优点：能够保证将任意长度为N的数组排序所需时间和NlogN成正比

缺点：所需的额外空间和N成正比

1、**原地归并 **

实现归并的一种直截了当的办法是将两个不同的有序数组归并到每三个数组中，两个数组中的元素应该都实现了Comparable接口。实现的方法：创建一个适当大小的数组然后将两个输入数组中的元素一个个从小到大放入这个数组中。

// 原地归并 抽象
public static void merge(Comparable[] a, int lo, int mid, int hi, Comparable[] temp) {
  // 将a[lo..mid] 和 a[mid +1..hi] 归并
  int i = lo, j = mid + i;
  for (int k = lo; k <= hi; k++) {
    temp[k] = a[k];
  }

  for (int k = lo; k <= hi; k++) {
    if (i > mid && j <= hi) a[k] = temp[j++];
    else if (j > hi) a[k] = temp[i++];
    else if (less(temp[j], temp[i])) a[k] = temp[j++];
    else a[k] = temp[i++];
  }


}

2、自顶向下归并

package algorithm.sort.merge;

import java.util.Arrays;

/**
 * 描述：归并排序 原地归并\自顶向下\自底向上
 * Created by zjw on 2021/6/27 22:20
 */
public class MergeSort {


    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3, 4, 5, 22, 2, 12, 13, 21, 9};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    // 原地归并
    public static void merge(Comparable[] a, int lo, int mid, int hi, Comparable[] temp) {
        // 将a[lo..mid] 和 a[mid +1..hi] 归并
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            temp[k] = a[k];
        }

        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = temp[j++];
            else if (j > hi) a[k] = temp[i++];
            else if (less(temp[j], temp[i])) a[k] = temp[j++];
            else a[k] = temp[i++];
        }


    }

    // 自顶向下的归并
    public static void sort(Comparable[] arr) {
        Comparable[] temp = new Comparable[arr.length]; // 一次性分配内存空间\避免递归中频繁开辟空间
        // sortDown(arr, 0, arr.length - 1, temp);
        sortUp(arr, temp);

    }

    // 自顶向下的归并
    public static void sortDown(Comparable[] arr, int lo, int hi, Comparable[] temp) {
        // 将数组a[lo..hi]排序
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;

        sortDown(arr, lo, mid, temp);// 排序左半边 左边归并排序，使得左子序列有序
        sortDown(arr, mid + 1, hi, temp);// 排序右半边 右边归并排序，使得右子序列有序
        merge(arr, lo, mid, hi, temp); // 归并结果
    }

    // 自底向上的归并
    public static void sortUp(Comparable[] arr, Comparable[] temp) {
        // 进行lgN次两两归并
        int N = arr.length;
        temp = new Comparable[N];
        for (int sz = 1; sz < N; sz = sz + sz) {
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(arr, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1), temp);
            }
        }
    }


    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
}

3、自底向上归并

// 自底向上的归并
    public static void sortUp(Comparable[] arr, Comparable[] temp) {
        // 进行lgN次两两归并
        int N = arr.length;
        temp = new Comparable[N];
        for (int sz = 1; sz < N; sz = sz + sz) {
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(arr, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1), temp);
            }
        }
    }

总结

当数组长度为2的幂时，向上和向下比较次数和数组访问次数是一样的，只是顺序不同。

自底向上的归并排序比较适合用链表组织的数据。