排序算法之【归并排序】

目录

实现归并排序【MergeSort】并提供升序和降序方法

归并排序方法测试

LeetCode-215题

实现归并排序【MergeSort】并提供升序和降序方法

/**
 * 归并排序
 */
public class MergeSort {

    // 升序排列
    private static final int UP_SORT_TYPE = 1;

    // 降序排列
    private static final int DOWN_SORT_TYPE = -1;

    /**
     * 升序排列
     *
     * @param nums：要排序的数组
     */
    public static void upSort(int[] nums) {
        if (nums == null || nums.length < 2)
            return;
        split(nums, 0, nums.length - 1, UP_SORT_TYPE);
    }

    /**
     * 降序排列
     *
     * @param nums：要排序的数组
     */
    public static void downSort(int[] nums) {
        if (nums == null || nums.length < 2)
            return;
        split(nums, 0, nums.length - 1, DOWN_SORT_TYPE);
    }

    /**
     * 分-治-合思想的体现
     */
    private static void split(int[] nums, int low, int high, int sortType) {
        if (low == high)
            return;
        int mid = (low + high) >>> 1;
        split(nums, low, mid, sortType);
        split(nums, mid + 1, high, sortType);
        merge(nums, low, mid, high, sortType);
    }

    private static void merge(int[] nums, int low, int mid, int high, int sortType) {
        int[] help = new int[high - low + 1];
        int i = 0;
        // 双指针
        int p1 = low;
        int p2 = mid + 1;

        while (p1 <= mid && p2 <= high) {
            if (sortType == UP_SORT_TYPE) {
                // 处理成升序排列
                help[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++];
            } else {
                // 处理成降序排列
                help[i++] = nums[p1] > nums[p2] ? nums[p1++] : nums[p2++];
            }
        }

        while (p1 <= mid)
            help[i++] = nums[p1++];

        while (p2 <= high)
            help[i++] = nums[p2++];

        for (i = 0; i < help.length; i++) {
            nums[low + i] = help[i];
        }
    }
}

归并排序方法测试

import java.util.Arrays;

public class MergeSortTest {
    public static void main(String[] args) {
        // 测试升序
        int[] nums1 = {23, 12, 34, 42, 345, 56, 45, 34, 37, 43, 1, 23, 44, 67};
        MergeSort.upSort(nums1);
        // [1, 12, 23, 23, 34, 34, 37, 42, 43, 44, 45, 56, 67, 345]
        System.out.println(Arrays.toString(nums1));

        // 测试降序
        int[] nums2 = {23, 12, 34, 42, 345, 56, 45, 34, 37, 43, 1, 23, 44, 67};
        MergeSort.downSort(nums2);
        // [345, 67, 56, 45, 44, 43, 42, 37, 34, 34, 23, 23, 12, 1]
        System.out.println(Arrays.toString(nums2));
    }
}

LeetCode-215题

求数组中的第K个最大元素，这里使用归并排序方式

class Solution {
    public int findKthLargest(int[] nums, int k) {
        MergeSort.downSort(nums);
        return nums[k - 1];
    }

    /**
     * 归并排序
     */
    class MergeSort {

        // 升序排列
        private static final int UP_SORT_TYPE = 1;

        // 降序排列
        private static final int DOWN_SORT_TYPE = -1;

        /**
         * 升序排列
         *
         * @param nums：要排序的数组
         */
        public static void upSort(int[] nums) {
            if (nums == null || nums.length < 2)
                return;
            split(nums, 0, nums.length - 1, UP_SORT_TYPE);
        }

        /**
         * 降序排列
         *
         * @param nums：要排序的数组
         */
        public static void downSort(int[] nums) {
            if (nums == null || nums.length < 2)
                return;
            split(nums, 0, nums.length - 1, DOWN_SORT_TYPE);
        }

        /**
         * 分-治-合思想的体现
         */
        private static void split(int[] nums, int low, int high, int sortType) {
            if (low == high)
                return;
            int mid = (low + high) >>> 1;
            split(nums, low, mid, sortType);
            split(nums, mid + 1, high, sortType);
            merge(nums, low, mid, high, sortType);
        }

        private static void merge(int[] nums, int low, int mid, int high, int sortType) {
            int[] help = new int[high - low + 1];
            int i = 0;
            // 双指针
            int p1 = low;
            int p2 = mid + 1;

            while (p1 <= mid && p2 <= high) {
                if (sortType == UP_SORT_TYPE) {
                    // 处理成升序排列
                    help[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++];
                } else {
                    // 处理成降序排列
                    help[i++] = nums[p1] > nums[p2] ? nums[p1++] : nums[p2++];
                }
            }

            while (p1 <= mid)
                help[i++] = nums[p1++];

            while (p2 <= high)
                help[i++] = nums[p2++];

            for (i = 0; i < help.length; i++) {
                nums[low + i] = help[i];
            }
        }
    }
}