LeetCode 补充题 5. 手撕归并排序

Categories:

Tags:

题目描述
思路分析
1. 解法一：归并排序（推荐）
相似题目

题目描述

✅ 补充题 5. 手撕归并排序

思路分析

解法一：归并排序（推荐）

核心思路：

将数组递归划分为两半，分别排序。

再通过归并过程合并为有序数组。

利用辅助数组减少重复拷贝。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(n)，需要辅助数组。

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

    private void mergeSort(int[] nums, int left, int right, int[] temp) {
        if (left >= right) {
            return;
        }

        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid, temp);
        mergeSort(nums, mid + 1, right, temp);

        if (nums[mid] <= nums[mid + 1]) {
            return;
        }

        merge(nums, left, mid, right, temp);
    }

    private void merge(int[] nums, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int k = left;

        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= right) {
            temp[k++] = nums[j++];
        }

        for (int p = left; p <= right; p++) {
            nums[p] = temp[p];
        }
    }
}

func sortArray(nums []int) []int {
	temp := make([]int, len(nums))
	mergeSort(nums, 0, len(nums)-1, temp)
	return nums
}

func mergeSort(nums []int, left int, right int, temp []int) {
	if left >= right {
		return
	}

	mid := left + (right-left)/2
	mergeSort(nums, left, mid, temp)
	mergeSort(nums, mid+1, right, temp)

	if nums[mid] <= nums[mid+1] {
		return
	}

	merge(nums, left, mid, right, temp)
}

func merge(nums []int, left int, mid int, right int, temp []int) {
	i := left
	j := mid + 1
	k := left

	for i <= mid && j <= right {
		if nums[i] <= nums[j] {
			temp[k] = nums[i]
			i++
		} else {
			temp[k] = nums[j]
			j++
		}
		k++
	}

	for i <= mid {
		temp[k] = nums[i]
		i++
		k++
	}
	for j <= right {
		temp[k] = nums[j]
		j++
		k++
	}

	for p := left; p <= right; p++ {
		nums[p] = temp[p]
	}
}

相似题目

题目	难度	考察点
912. 排序数组	中等	归并排序
148. 排序链表	中等	归并排序
88. 合并两个有序数组	简单	归并
315. 计算右侧小于当前元素的个数	困难	归并排序
327. 区间和的个数	困难	归并排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/34361985