归并排序

发表于 更新于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

Leetcode-912.排序数组

给你一个整数数组 nums，请你将该数组升序排列。

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int[] sortArray(int[] nums) {
        if (nums.length < 2) {
            return nums;
        }
        process(nums, 0, nums.length - 1);
        return nums;
    }

    public void process(int[] nums, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        process(nums, left, mid);
        process(nums, mid + 1, right);
        merge(nums, left, right, mid);
    }

    public void merge(int[] nums, int left, int right, int mid) {
        int[] help = new int[right - left + 1];
        int i = 0;
        int leftPoint = left;
        int rightPoint = mid + 1;
        while (leftPoint <= mid && rightPoint <= right) {
            help[i++] = nums[leftPoint] < nums[rightPoint] ? nums[leftPoint++] : nums[rightPoint++];
        }
        while (leftPoint <= mid) {
            help[i++] = nums[leftPoint++];
        }
        while (rightPoint <= right){
            help[i++] = nums[rightPoint++];
        }
        for (int j = 0; j < help.length; j++) {
            nums[left + j] = help[j]; 
        }
    }
}

非递归版本

image-20210920094229297

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public int[] sortArray(int[] nums) {
        if (nums.length < 2) {
            return nums;
        }
        int stepSize = 1;
        while (nums.length > stepSize) {
            process(nums, stepSize);
            stepSize <<= 1;
        }
        return nums;
    }

    public void process(int[] nums, int stepSize){
        int left = 0;
        while (left < nums.length - 1) {
            int mid = left + stepSize - 1;
            if (mid >= nums.length -1) {
                break;
            }
            int right = Math.min(mid + stepSize, nums.length - 1);
            merge(nums, left, right, mid);
            left += stepSize << 1;
        }
    }

    public void merge(int[] nums, int left, int right, int mid) {
            int[] help = new int[right - left + 1];
            int i = 0;
            int leftPoint = left;
            int rightPoint = mid + 1;
            while (leftPoint <= mid && rightPoint <= right) {
                help[i++] = nums[leftPoint] < nums[rightPoint] ? nums[leftPoint++] : nums[rightPoint++];
            }
            while (leftPoint <= mid) {
                help[i++] = nums[leftPoint++];
            }
            while (rightPoint <= right) {
                help[i++] = nums[rightPoint++];
            }
            for (int j = 0; j < help.length; j++) {
                nums[left + j] = help[j];
            }
        }
}