算法|从零学算法:排序算法(4)

1. 经典算法

1.1 归并排序

归并排序（Merge Sort）是一种分治算法，由约翰·冯·诺伊曼在1945年发明。它通过递归地将数组分成两半，然后对每一半进行排序，最后将排序好的两半合并在一起，从而完成整个数组的排序。

1.1.1 算法步骤

? 分割：将待排序的数组分成两半，直到每个子数组只包含一个元素。

? 递归排序：递归地对每个子数组进行归并排序。

? 合并：将排序好的两个子数组合并成一个有序数组。

1.1.2 算法图解

归并排序通过递归地将数组分成更小的部分，然后合并这些部分，直到整个数组被排序。

1.1.3 算法特点

? 稳定性：归并排序是一种稳定的排序算法，因为它不会改变相同元素的相对顺序。

? 时间复杂度：无论最好、最坏还是平均情况下，时间复杂度都是O(n log n)。

? 空间复杂度：O(n)，归并排序需要使用到额外的空间来存储临时的合并结果。

1.1.4 代码实现

Python
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2 # 找到中间位置
L = arr[:mid] # 左侧序列
R = arr[mid:] # 右侧序列

merge_sort(L) # 递归对左侧序列进行排序
merge_sort(R) # 递归对右侧序列进行排序

# 合并两个排序好的序列
i = j = k = 0

# 按顺序合并元素直到一个子数组为空
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1

# 将剩余的元素移到数组的末尾
while i < len(L):
arr[k] = L[i]
i += 1
k += 1

while j < len(R):
arr[k] = R[j]
j += 1
k += 1

return arr

# 示例
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Sorted array is:", sorted_arr)

1.1.5 适用场景

归并排序由于其稳定性和时间复杂度，适用于以下情况：

? 大数据集：归并排序适合处理大型数据集，因为它的性能不会受到数据规模的影响。

? 稳定性需求：当排序过程中保持元素的相对顺序很重要时，归并排序是一个合适的选择。

? 外存排序：归并排序适合于磁盘等外存上的排序，因为它可以有效地减少读取和写入的次数。

? 内存限制：尽管归并排序需要额外的内存空间，但通过优化可以实现为原地排序，从而减少内存使用。

1.2 快速排序

快速排序（Quick Sort）是一种高效的排序算法，由C. A. R. Hoare在1960年提出。它采用分治法的策略，通过选择一个“基准”元素，将数组分为两部分：一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素。然后递归地对这两部分进行快速排序。

1.2.1 算法步骤

? 选择基准：从数组中选择一个元素作为基准。

? 分区操作：重新排列数组，所有比基准小的元素放在基准的左边，所有比基准大的元素放在基准的右边。

? 递归排序：递归地对基准左边和右边的子数组进行快速排序。

? 完成：递归到基情况（数组只有一个或零个元素）时，排序完成。

1.2.2 算法图解

快速排序通过选择一个基准值，将数组分为两部分，然后递归地对这两部分进行排序。

1.2.3 算法特点

? 效率：在大多数情况下，快速排序的平均时间复杂度为O(n log n)。

? 不稳定性：快速排序是不稳定的排序算法，因为在分区过程中可能会改变相同元素的相对顺序。

? 时间复杂度：平均情况下为O(n log n)，但在最坏情况下（例如，数组已经排序或完全逆序）为O(n^2)。

? 空间复杂度：O(log n)，快速排序是原地排序算法，但递归性质导致它需要O(log n)的额外栈空间。

1.2.4 代码实现

Python
def quick_sort(arr, low, high):
if low < high:
# 分区操作
pivot_index = partition(arr, low, high)
# 递归地对基准左边和右边的子数组进行快速排序
quick_sort(arr, low, pivot_index - 1)
quick_sort(arr, pivot_index + 1, high)

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

# 示例
arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr) - 1)
print("Sorted array is:", arr)

1.2.5 适用场景

快速排序由于其高效率，适用于以下情况：

? 通用排序：快速排序是许多系统默认的排序算法，因为它在大多数情况下都表现良好。

? 大数据集：快速排序适合处理大型数据集，因为它的平均时间复杂度为O(n log n)。

? 内存限制：快速排序是原地排序算法，不需要额外的存储空间，适合内存受限的环境。

? 随机数据：快速排序在处理随机数据时通常表现很好，但在数据已经排序或完全逆序时性能会下降。在这种情况下，可以考虑使用随机化版本的快速排序，即随机选择基准，以期望获得更好的性能。