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)是一种不稳定的排序算法适用于大规模数据的排序。掌握快速排序的原理对于理解分治算法和递归思想非常重要。