LeetCode 补充题 4. 手撕快速排序

Categories:

Tags:

题目描述
思路分析
1. 解法一：随机化快速排序（推荐）
相似题目

题目描述

✅ 补充题 4. 手撕快速排序

题目：

给定一个整数数组 nums，要求手写快速排序将其升序排列后返回。不得使用任何内置排序函数，时间复杂度要求 O(n log n)，空间复杂度尽可能小。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

1 <= nums.length <= 5 * 10^4
-5 * 10^4 <= nums[i] <= 5 * 10^4

思路分析

解法一：随机化快速排序（推荐）

核心思路：

使用分治思想，每轮选取一个基准元素 pivot，将数组划分为左右两部分。

采用随机化选择 pivot，避免在近乎有序数组上退化到 O(n^2)。

使用挖坑法单次扫描完成分区，pivot 最终落在正确位置。

复杂度分析：

时间复杂度：O(n log n)（平均），O(n^2)（最坏），其中 n 表示数组长度。

空间复杂度：O(log n)，其中 log n 表示递归栈深度。

class Solution {
    private final Random random = new Random();

    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

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

        // 随机选择基准，防止退化
        int pivotIndex = left + random.nextInt(right - left + 1);
        swap(nums, left, pivotIndex);
        int pivot = nums[left];

        int i = left, j = right;
        while (i < j) {
            while (i < j && nums[j] >= pivot) {
                j--;
            }
            if (i < j) {
                nums[i++] = nums[j];
            }
            while (i < j && nums[i] <= pivot) {
                i++;
            }
            if (i < j) {
                nums[j--] = nums[i];
            }
        }

        // pivot 归位
        nums[i] = pivot;

        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

func sortArray(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	quickSort(nums, 0, len(nums)-1)
	return nums
}

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

	// 随机选择基准元素
	pivotIndex := rand.Intn(right-left+1) + left
	nums[left], nums[pivotIndex] = nums[pivotIndex], nums[left]
	pivot := nums[left]

	i, j := left, right
	for i < j {
		for i < j && nums[j] >= pivot {
			j--
		}
		if i < j {
			// 将小于基准的元素放到左边
			nums[i] = nums[j]
			i++
		}
		for i < j && nums[i] <= pivot {
			i++
		}
		if i < j {
			// 将大于基准的元素放到右边
			nums[j] = nums[i]
			j--
		}
	}

	nums[i] = pivot

	quickSort(nums, left, i-1)
	quickSort(nums, i+1, right)
}

相似题目

题目	难度	考察点
215. 数组中的第 K 个最大元素	中等	快速选择（快排变体）
912. 排序数组	中等	归并排序/快速排序实现
75. 颜色分类	中等	三路快排思想（荷兰国旗）
148. 排序链表	中等	归并排序思想
347. 前 K 个高频元素	中等	快速选择/堆排序
973. 最接近原点的 K 个点	中等	快速选择

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/33242831