快速排序(Quick Sort)是一种高效的排序算法,采用分而治之(Divide and Conquer)的策略来把一个序列分为较小和较大的两个子序列,然后递归地排序两个子序列。
基本思想
- 选择基准(Pivot):从数列中挑出一个元素,称为“基准”(pivot)。
- 分区(Partitioning):重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
- 递归(Recursion):递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
Python 实现
下面是快速排序的Python实现:
python复制代码
def quicksort(arr): |
|
if len(arr) <= 1: |
|
return arr |
|
else: |
|
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 quicksort(left) + middle + quicksort(right) # 递归排序左右子序列,并合并结果 |
|
# 示例 |
|
arr = [10, 7, 8, 9, 1, 5] |
|
sorted_arr = quicksort(arr) |
|
print("Sorted array is:", sorted_arr) |
注意:在实际应用中,上述实现可能不是最优的,因为它在每次递归时都进行了列表的切片和合并操作,这会增加额外的时间复杂度。一种更优化的方式是使用原地分区(in-place partitioning),这样可以避免使用额外的空间来存储分区后的子列表。
原地分区快速排序的Python实现
python复制代码
def quicksort_inplace(arr, low, high): |
|
if low < high: |
|
# partition the array and get the partition index |
|
pi = partition(arr, low, high) |
|
# Separately sort elements before |
|
# partition and after partition |
|
quicksort_inplace(arr, low, pi-1) |
|
quicksort_inplace(arr, pi+1, high) |
|
def partition(arr, low, high): |
|
# 选择最后一个元素作为基准 |
|
pivot = arr[high] |
|
i = low - 1 # 小于基准的元素的索引 |
|
for j in range(low, high): |
|
# 如果当前元素小于或等于pivot |
|
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) |
|
# 示例 |
|
arr = [10, 7, 8, 9, 1, 5] |
|
n = len(arr) |
|
quicksort_inplace(arr, 0, n-1) |
|
print("Sorted array is:", arr) |
这个版本的快速排序使用了原地分区技术,更加高效。