27 lines
883 B
Python
27 lines
883 B
Python
#快速排序算法, 1、递归实现 2、任务拆分子任务 3、起止条件 4、sample data
|
||
# input: arr = [3, 7, 1, 9, 2, 5]， 左边和右边交替，左边只要找打比3小的就交换，再走右边
|
||
#描述：
|
||
|
||
#快速排序算法
|
||
def quick_sort(arr, start, end):
|
||
if start >= end:
|
||
return
|
||
pivot = arr[start]
|
||
left = start + 1
|
||
right = end
|
||
while left <= right:
|
||
while left <= right and arr[left] <= pivot:
|
||
left += 1
|
||
while left <= right and arr[right] >= pivot:
|
||
right -= 1
|
||
if left < right:
|
||
arr[left], arr[right] = arr[right], arr[left]
|
||
arr[start], arr[right] = arr[right], arr[start]
|
||
quick_sort(arr, start, right - 1)
|
||
quick_sort(arr, right + 1, end)
|
||
|
||
arr = [3, 7, 1, 9, 2, 5]
|
||
quick_sort(arr, 0, len(arr) - 1)
|
||
print(arr) # [1, 2, 3, 5, 7, 9]
|
||
|