「分治思想」的应用

「排序算法」专题 4：归并排序的优化

根据上一节的「归并排序」的 3 个优化，写出的代码。

Java 代码：

public class Solution {

    /**
     * 列表大小等于或小于该大小，将优先于 mergeSort 使用插入排序
     */
    private static final int INSERTION_SORT_THRESHOLD = 7;

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        int[] temp = new int[len];
        mergeSort(nums, 0, len - 1, temp);
        return nums;
    }

    /**
     * 对数组 nums 的子区间 [left, right] 进行归并排序
     *
     * @param nums
     * @param left
     * @param right
     * @param temp  用于合并两个有序数组的辅助数组，全局使用一份，避免多次创建和销毁
     */
    private void mergeSort(int[] nums, int left, int right, int[] temp) {
        // 小区间使用插入排序
        if (right - left <= INSERTION_SORT_THRESHOLD) {
            insertionSort(nums, left, right);
            return;
        }

        int mid = left + (right - left) / 2;
        // Java 里有更优的写法，在 left 和 right 都是大整数时，即使溢出，结论依然正确
        // int mid = (left + right) >>> 1;

        mergeSort(nums, left, mid, temp);
        mergeSort(nums, mid + 1, right, temp);
        // 如果数组的这个子区间本身有序，无需合并
        if (nums[mid] <= nums[mid + 1]) {
            return;
        }
        mergeOfTwoSortedArray(nums, left, mid, right, temp);
    }

    /**
     * 对数组 arr 的子区间 [left, right] 使用插入排序
     *
     * @param arr   给定数组
     * @param left  左边界，能取到
     * @param right 右边界，能取到
     */
    private void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int temp = arr[i];
            int j = i;
            while (j > left && arr[j - 1] > temp) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = temp;
        }
    }

    /**
     * 合并两个有序数组：先把值复制到临时数组，再合并回去
     *
     * @param nums
     * @param left
     * @param mid   [left, mid] 有序，[mid + 1, right] 有序
     * @param right
     * @param temp  全局使用的临时数组
     */
    private void mergeOfTwoSortedArray(int[] nums, int left, int mid, int right, int[] temp) {
        System.arraycopy(nums, left, temp, left, right + 1 - left);

        int i = left;
        int j = mid + 1;

        for (int k = left; k <= right; k++) {
            if (i == mid + 1) {
                nums[k] = temp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                // 注意写成 < 就丢失了稳定性（相同元素原来靠前的排序以后依然靠前）
                nums[k] = temp[i];
                i++;
            } else {
                // temp[i] > temp[j]
                nums[k] = temp[j];
                j++;
            }
        }
    }
}

Python 代码：

class MergeSortOptimizer:

    def __str__(self):
        return "归并排序的优化"

    def __merge_of_two_sorted_array(self, arr, left, mid, right):
        # 将原数组 [left, right] 区间内的元素复制到辅助数组
        for index in range(left, right + 1):
            nums_for_compare[index] = arr[index]

        i = left
        j = mid + 1
        for k in range(left, right + 1):
            if i == mid + 1:
                # i 用完了，就拼命用 j
                arr[k] = nums_for_compare[j]
                j += 1
            elif j > right:
                # j 用完了，就拼命用 i
                arr[k] = nums_for_compare[i]
                i += 1
            elif nums_for_compare[i] <= nums_for_compare[j]:
                arr[k] = nums_for_compare[i]
                i += 1
            else:
                assert nums_for_compare[i] > nums_for_compare[j]
                arr[k] = nums_for_compare[j]
                j += 1

    def insert_sort_for_sub_interval(self, arr, left, right):
        """多次赋值的插入排序"""
        for i in range(left + 1, right + 1):
            temp = arr[i]
            j = i
            # 注意：这里 j 最多到 left
            while j > left and arr[j - 1] > temp:
                arr[j] = arr[j - 1]
                j -= 1
            arr[j] = temp

    def __merge_sort(self, arr, left, right):
        if right - left <= 15:
            self.insert_sort_for_sub_interval(arr, left, right)
            return
        mid = left + (right - left) // 2
        self.__merge_sort(arr, left, mid)
        self.__merge_sort(arr, mid + 1, right)
        if arr[mid] <= arr[mid + 1]:
            return
        self.__merge_of_two_sorted_array(arr, left, mid, right)

    @SortingUtil.cal_time
    def sort(self, arr):
        global nums_for_compare
        size = len(arr)
        nums_for_compare = list(range(size))
        self.__merge_sort(arr, 0, size - 1)

复杂度分析：

• 时间复杂度：$O(N \log N)$，这里 $N$ 是数组的长度；
• 空间复杂度：$O(N)$，辅助数组与输入数组规模相当。

（本节完）