Python 3 中 快速排序 和 归并排序
1. 快速排序实现：
快速排序采用 分治法，选择一个基准元素（pivot），将数组分成两部分，分别排序。
快速排序代码实现：
def quick_sort(arr):
# 基本情况：如果数组为空或只有一个元素，则无需排序
if len(arr) <= 1:
return arr
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 quick_sort(left) + middle + quick_sort(right)
# 示例数组
arr = [10, 7, 8, 9, 1, 5]
# 调用快速排序函数
sorted_arr_quick = quick_sort(arr)
# 输出排序后的数组
print("Quick Sort Result:", sorted_arr_quick)
2. 归并排序实现：
归并排序同样是 分治法，但它通过递归将数组分割成更小的部分，最终将小部分合并起来。
归并排序代码实现：
def merge_sort(arr):
# 基本情况：如果数组只有一个元素，则无需排序
if len(arr) <= 1:
return arr
# 递归分割数组
mid = len(arr) // 2 # 取数组的中间索引
left_half = merge_sort(arr[:mid]) # 递归排序左半部分
right_half = merge_sort(arr[mid:]) # 递归排序右半部分
# 合并两个已排序的子数组
return merge(left_half, right_half)
def merge(left, right):
sorted_arr = []
i = j = 0
# 比较两个数组的元素，按升序合并
while i < len(left) and j < len(right):
if left[i] <= right[j]:
sorted_arr.append(left[i])
i += 1
else:
sorted_arr.append(right[j])
j += 1
# 将剩余的元素加入结果数组
sorted_arr.extend(left[i:]) # 如果左边还有元素
sorted_arr.extend(right[j:]) # 如果右边还有元素
return sorted_arr
# 示例数组
arr = [10, 7, 8, 9, 1, 5]
# 调用归并排序函数
sorted_arr_merge = merge_sort(arr)
# 输出排序后的数组
print("Merge Sort Result:", sorted_arr_merge)
3. 快速排序和归并排序的对比：
| 特性 | 快速排序 (Quick Sort) | 归并排序 (Merge Sort) |
|---|---|---|
| 时间复杂度 | 最优：O(n log n)，最坏：O(n²)，平均：O(n log n) | O(n log n)（最坏、最优和平均时间复杂度均相同） |
| 空间复杂度 | O(log n)（递归调用栈的空间） | O(n)（需要额外的数组来存储合并结果） |
| 稳定性 | 不稳定 | 稳定 |
| 适用场景 | 当数据集较小或者排序部分已经大体有序时，快速排序较为高效。 | 适合需要稳定排序的场景，或者数据集较大时，特别是外部排序。 |
| 实现难度 | 较简单，但需要注意最坏情况的处理。 | 相对复杂，尤其是合并过程的实现。 |
| 实际表现 | 对大部分随机数组，性能非常好。 | 对大数据集性能较为稳定，适合处理大型数据集。 |
总结：
- 快速排序 在大部分情况下表现非常好，但最坏情况下的时间复杂度是 O(n²)，特别是当数组已经基本有序或逆序时。
- 归并排序 总是有稳定的 O(n log n) 时间复杂度，适合稳定排序和处理非常大的数据集，特别是当数据无法完全装入内存时。
如果排序的数组较小，快速排序通常会更快一些，因为它的常数项比较小；而归并排序虽然稳定且时间复杂度较好，但它的额外空间开销较大。