LeetCode 快速排序题解

LeetCode 快速排序题解题目描述实现快速排序算法对一个整数数组进行排序。示例输入[64, 34, 25, 12, 22, 11, 90]输出[11, 12, 22, 25, 34, 64, 90]解题思路方法快速排序思路快速排序的核心思想是分治选择一个基准元素将数组分成两部分左边的元素都小于基准元素右边的元素都大于基准元素然后递归地对左右两部分进行排序。具体步骤选择一个基准元素通常选择数组的第一个元素、最后一个元素或中间元素。将数组分成两部分左边的元素都小于基准元素右边的元素都大于基准元素。递归地对左半部分进行排序。递归地对右半部分进行排序。复杂度分析时间复杂度O(n log n)其中 n 是数组的长度。最坏情况下时间复杂度为 O(n²)当数组已经有序或基本有序时。空间复杂度O(log n)需要额外的空间来存储递归调用的栈。代码实现方法快速排序# 快速排序 def quick_sort(arr): if len(arr) 1: return arr # 选择基准元素这里选择中间元素 pivot arr[len(arr) // 2] # 分成三部分小于基准元素的等于基准元素的大于基准元素的 left [x for x in arr if x pivot] middle [x for x in arr if x pivot] right [x for x in arr if x pivot] # 递归地对左半部分和右半部分进行排序 return quick_sort(left) middle quick_sort(right) # 测试 def test_quick_sort(): arr [64, 34, 25, 12, 22, 11, 90] print(quick_sort(arr)) # 输出[11, 12, 22, 25, 34, 64, 90] arr [5, 4, 3, 2, 1] print(quick_sort(arr)) # 输出[1, 2, 3, 4, 5] arr [1, 2, 3, 4, 5] print(quick_sort(arr)) # 输出[1, 2, 3, 4, 5] if __name__ __main__: test_quick_sort()方法原地快速排序# 原地快速排序 def quick_sort_in_place(arr, low0, highNone): if high is None: high len(arr) - 1 if low high: # 分区返回基准元素的位置 pivot_idx partition(arr, low, high) # 递归地对左半部分进行排序 quick_sort_in_place(arr, low, pivot_idx - 1) # 递归地对右半部分进行排序 quick_sort_in_place(arr, pivot_idx 1, high) return arr # 分区函数 def partition(arr, low, high): # 选择基准元素这里选择最后一个元素 pivot arr[high] # i 是小于基准元素的区域的边界 i low - 1 # 遍历数组将小于基准元素的元素移到左边 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] # 将基准元素移到正确的位置 arr[i 1], arr[high] arr[high], arr[i 1] return i 1 # 测试 def test_quick_sort_in_place(): arr [64, 34, 25, 12, 22, 11, 90] print(quick_sort_in_place(arr)) # 输出[11, 12, 22, 25, 34, 64, 90] arr [5, 4, 3, 2, 1] print(quick_sort_in_place(arr)) # 输出[1, 2, 3, 4, 5] arr [1, 2, 3, 4, 5] print(quick_sort_in_place(arr)) # 输出[1, 2, 3, 4, 5] if __name__ __main__: test_quick_sort_in_place()测试用例测试用例 1基本情况输入[64, 34, 25, 12, 22, 11, 90]输出[11, 12, 22, 25, 34, 64, 90]测试用例 2逆序数组输入[5, 4, 3, 2, 1]输出[1, 2, 3, 4, 5]测试用例 3已排序数组输入[1, 2, 3, 4, 5]输出[1, 2, 3, 4, 5]总结快速排序是一种高效的排序算法它通过分治的思想将数组分成两部分左边的元素都小于基准元素右边的元素都大于基准元素然后递归地对左右两部分进行排序。快速排序的平均时间复杂度为 O(n log n)但最坏情况下时间复杂度为 O(n²)。快速排序的核心思想是选择一个基准元素将数组分成两部分左边的元素都小于基准元素右边的元素都大于基准元素然后递归地对左右两部分进行排序。掌握快速排序的原理和实现对于理解分治算法的思想非常重要。