LeetCode 快速排序 题解
LeetCode 快速排序 题解
题目描述
实现快速排序算法，对一个整数数组进行排序。
示例 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。
复杂度分析：
- 时间复杂度：O(n log n)，其中 n 是数组的长度。最坏情况下，时间复杂度为 O(n²)，但平均情况下是 O(n log n)。
- 空间复杂度：O(log n)，需要使用递归栈空间。
代码实现
方法：快速排序
def quick_sort(nums): # 调用辅助函数 quick_sort_helper(nums, 0, len(nums) - 1) return nums def quick_sort_helper(nums, left, right): # 递归终止条件 if left < right: # 分区操作，返回基准元素的位置 pivot_idx = partition(nums, left, right) # 递归排序左半部分 quick_sort_helper(nums, left, pivot_idx - 1) # 递归排序右半部分 quick_sort_helper(nums, pivot_idx + 1, right) def partition(nums, left, right): # 选择最右边的元素作为基准 pivot = nums[right] # 初始化指针 i i = left - 1 # 遍历数组 for j in range(left, right): # 如果当前元素小于基准，交换元素并移动指针 i if nums[j] < pivot: i += 1 nums[i], nums[j] = nums[j], nums[i] # 将基准元素放到正确的位置 nums[i + 1], nums[right] = nums[right], nums[i + 1] # 返回基准元素的位置 return i + 1 # 测试 nums1 = [5,2,3,1] print(quick_sort(nums1)) # 输出：[1,2,3,5] nums2 = [5,1,1,2,0,0] print(quick_sort(nums2)) # 输出：[0,0,1,1,2,5]测试用例
测试用例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
测试用例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
总结
本题是排序算法的经典问题，主要考察对快速排序算法的理解和实现。快速排序是一种分治算法，它通过选择基准元素，将数组分成两部分，然后对左右两部分分别进行快速排序来完成排序。
快速排序的核心思想是：选择一个基准元素，将数组分成两部分，小于基准的元素放在左边，大于基准的元素放在右边，然后递归地对左右两部分进行排序。
这种方法的平均时间复杂度为 O(n log n)，是一种不稳定的排序算法，适用于大规模数据的排序。掌握快速排序的原理，对于理解分治算法和递归思想非常重要。