34 lines
856 B
Python
34 lines
856 B
Python
|
"""
|
||
|
|
快速排序 — 分治策略
|
||
|
|
平均时间复杂度 O(n log n)，最坏 O(n²)
|
||
|
|
"""
|
||
|
|
|
||
|
|
def partition(arr, low, high):
|
||
|
|
"""划分：选择基准，将小于基准的放左边，大于的放右边"""
|
||
|
|
pivot = arr[high] # 选最后一个元素作为基准
|
||
|
|
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 quick_sort(arr, low, high):
|
||
|
|
"""快速排序递归实现"""
|
||
|
|
if low < high:
|
||
|
|
pi = partition(arr, low, high)
|
||
|
|
quick_sort(arr, low, pi - 1)
|
||
|
|
quick_sort(arr, pi + 1, high)
|
||
|
|
|
||
|
|
def sort(arr):
|
||
|
|
quick_sort(arr, 0, len(arr) - 1)
|
||
|
|
|
||
|
|
if __name__ == "__main__":
|
||
|
|
data = [10, 7, 8, 9, 1, 5]
|
||
|
|
print("排序前:", data)
|
||
|
|
sort(data)
|
||
|
|
print("排序后:", data)
|