归并排序

算法分析

• 归并排序算法就是用分治策略实现对n个元素进行排序的算法。
• 将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最终将排好序的子集合合并成所要求的排好序的集合。

代码实现

流程图

public class Solution {

    public static void main(String[] args) {
        int[] nums = {1, 4, 3, 9, 7, 6};
        System.out.println("排序前：" + Arrays.toString(nums));
        new Solution().mergeSort(nums, 0, nums.length - 1);
        System.out.println("排序后：" + Arrays.toString(nums));
    }

    public void mergeSort(int[] nums, int left, int right) {
        int[] tmp = new int[nums.length];
        if (left < right) {
            int i = (left + right) >> 1;
            // 对前半部分排序。
            mergeSort(nums, left, i);
            // 对后半部分排序。
            mergeSort(nums, i + 1, right);
            // 合并到数组b
            merge(nums, tmp, left, i, right);
        }
    }

    public void merge(int[] nums, int[] tmp, int l, int m, int r) {
        int i = l;
        int j = m + 1;
        int k = l;
        // nums[l:m]与nums[m+1,r]中的元素两两比较，把小的放在前面，大的放在后面。
        while (i <= m && j <= r) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        // 当nums[l:m]或nums[m+1,r]的某一个中的全部元素已经全部放入tmp[]中后，将另一个接在tmp[]的最后。
        if (i > m) {
            for (int q = j; q <= r; q++) {
                tmp[k++] = nums[q];
            }
        } else {
            for (int q = i; q <= m; q++) {
                tmp[k++] = nums[q];
            }
        }
        // 复制回数组nums
        for (int x = l; x <= r; x++) {
            nums[x] = tmp[x];
        }
    }

}

• mergeSort(int[] nums, int left, int right)：对nums[left:right]进行排序。
• merge(int[] nums, int[] tmp, int l, int m, int r)：合并nums[l:m]和nums[m+1:r]到tmp[l:r]

算法改进

• 迭代实现：首先将数组a中相邻元素两两配对，用合并算法将它们排序，构成n/2组长度为2的排好序的子数组段，然后再将它们排序成长度为4的排好序的子数组段，如此继续下去，直至整个数组排好序。

public class Solution {

    public static void main(String[] args) {
        int[] nums = {1, 4, 3, 9, 7, 6};
        new Solution().mergeSort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }

    public void mergeSort(int[] nums, int n) {
        int[] tmp = new int[nums.length];
        int s = 1;
        // 至少有2个元素。
        while (s < n) {
            // 合并排序到数组b
            mergePass(nums, tmp, s, n);
            s += s;
            // 合并排序到数组a
            mergePass(tmp, nums, s, n);
            s += s;
        }
    }

    public void mergePass(int[] x, int[] y, int s, int n) {
        int i = 0;
        // 合并大小为s的相邻2段子数组。
        while (i <= n - 2 * s) {
            merge(x, y, i, i + s - 1, i + 2 * s - 1);
            i = i + 2 * s;
        }
        // 剩下的元素个数少于2s
        // 当剩下元素可被划分成大小不同的数组段时。
        if (i + s < n) {
            merge(x, y, i, i + s - 1, n - 1);
            // 当剩下元素个数不够s时，不用划分在合并，直接加在最后。
        } else {
            for (int j = i; j <= n - 1; j++) {
                y[j] = x[j];
            }
        }
    }

    public void merge(int[] nums, int[] tmp, int l, int m, int r) {
        int i = l;
        int j = m + 1;
        int k = l;
        //nums[l:m]nums[m+1,r]中的元素两两比较，把小的放在前面，大的放在后面。
        while (i <= m && j <= r) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        // 当nums[l:m]或nums[m+1,r]的某一个中的全部元素已经全部放入tmp[]中后，将另一个接在tmp[]的最后。
        if (i > m) {
            for (int q = j; q <= r; q++) {
                tmp[k++] = nums[q];
            }
        } else {
            for (int q = i; q <= m; q++) {
                tmp[k++] = nums[q];
            }
        }
    }

}

• mergeSort(int[] nums, int n)：对数组nums[n-1]进行排序。
• mergePass(int[] x, int[] y, int s, int n) ：将数组x[n-1]以s个元素一组，划分出n/s组，合并排序大小为s的相邻子数组，并存入数组y[n]中。