快速排序（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) |
这个版本的快速排序使用了原地分区技术，更加高效。
![2024/07 近期关于AI的阅读和理解[笔记]](https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8){kind=icon}
