46 lines
1.4 KiB
Python
46 lines
1.4 KiB
Python
|
"""
|
|||
|
|
核心：将小于基准的数移到左边，将大于基准的数移到右边，再对左右分区继续执行快速排序
|
|||
|
|
1. 选择列表中的一个数作为基准，一般是第一个元素
|
|||
|
|
2. 设置左右两个指针，分别指向第一个元素和最后一个元素
|
|||
|
|
3. 向左移动右指针，若发现比基准值小的值，则将其与基准值交换
|
|||
|
|
4. 接着向右移动左指针，若发现比基准值大的值，则将其与基准值交换
|
|||
|
|
5. 重复 3, 4，直到 左右指针相遇
|
|||
|
|
6. 最后基准值所在的位置，左边都比其小，右边都比其大
|
|||
|
|
7. 再对左右区域指向快排
|
|||
|
|
|
|||
|
|
复杂度为 O(n^2)
|
|||
|
|
"""
|
|||
|
|
|
|||
|
|
|
|||
|
|
def quick_sort(nums: list[int], low: int, high: int):
|
|||
|
|
i = low
|
|||
|
|
j = high
|
|||
|
|
# 一开始的基准值为 nums[i]
|
|||
|
|
if low >= high:
|
|||
|
|
return
|
|||
|
|
while i < j:
|
|||
|
|
while i < j and nums[j] >= nums[i]:
|
|||
|
|
j -= 1
|
|||
|
|
|
|||
|
|
if i < j:
|
|||
|
|
# 交换后基准值移到右边
|
|||
|
|
nums[i], nums[j] = nums[j], nums[i]
|
|||
|
|
i += 1
|
|||
|
|
|
|||
|
|
while i < j and nums[i] < nums[j]:
|
|||
|
|
i += 1
|
|||
|
|
|
|||
|
|
if i < j:
|
|||
|
|
# 交换后基准值移到左边
|
|||
|
|
nums[j], nums[i] = nums[i], nums[j]
|
|||
|
|
j -= 1
|
|||
|
|
|
|||
|
|
# 基准值位置是i，所以 low 到 i-1 是小区基准值的区域
|
|||
|
|
quick_sort(nums, low, i - 1)
|
|||
|
|
#
|
|||
|
|
quick_sort(nums, j + 1, high)
|
|||
|
|
|
|||
|
|
|
|||
|
|
nums = [47, 29, 71, 99, 78, 19, 24, 47]
|
|||
|
|
quick_sort(nums, 0, len(nums)-1)
|
|||
|
|
print(nums)
|