数据结构与算法之美 | 排序（2）

归并排序（Merge Sort）

基本思想：

如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

def merge_sort(array):'''使用归并排序算法对数组进行排序参数:array(list): 待排序数组返回值:array(list): 已排序数组'''if array is None:return []if len(array) == 1:return array# 检查数组长度是否大于1if len(array) > 1:# 将数组分成两半mid = len(array) // 2right_array = array[mid:]left_array = array[:mid]# 递归调用归并排序对左右两半进行排序merge_sort(right_array)merge_sort(left_array)# 初始化左子数组、右子数组和合并后的数组的索引位置left_index = right_index = merge_index = 0# 合并左右两个有序数组while left_index < len(left_array) and right_index < len(right_array):if left_array[left_index] < right_array[right_index]:array[merge_index] = left_array[left_index]left_index += 1else:array[merge_index] = right_array[right_index]right_index += 1merge_index += 1# 在合并排序过程中，左右两个子数组已经是有序的，而剩余的元素必然是较大（或较小）的元素，# 我们需要将它们放入原数组的正确位置以保持整体有序    # 首先，将左侧剩余元素复制到原数组中while left_index < len(left_array):array[merge_index] = left_array[left_index]left_index += 1merge_index += 1# 将右侧剩余元素复制到原数组中while right_index < len(right_array):array[merge_index] = right_array[right_index]right_index += 1merge_index += 1return arrayarray = [6, 5, 12, 10, 9, 1]
print(merge_sort(array)) # Output: [1, 5, 6, 9, 10, 12]

归并排序算法评价：

• 执行效率：最好情况时间复杂度为$O(nlogn)$，最坏情况时间复杂度为$O(nlogn)$，平均情况时间复杂度为$O(nlogn)$

• 内存消耗：不是一个原地排序算法，空间复杂度为$O(n)$

• 稳定性：是一个稳定的排序算法

快速排序（Quick Sort）

基本思想：

• 如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。
• 我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。
• 经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
• 根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。

使用Python代码实现：

def partition(arr, low, high):"""将数组划分为两部分，左侧的元素小于等于基准点，右侧的元素大于基准点。参数:arr (list): 待划分的数组low (int): 划分区间的起始索引high (int): 划分区间的结束索引返回:pivot_idx(int): 基准点的索引"""i = low - 1pivot = arr[high]  # 选择最后一个元素作为基准点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]pivot_idx = i + 1return pivot_idxdef quick_sort(arr, low, high):"""实现一个原地快速排序算法参数:arr (list): 待排序列表low (int): 列表的起始索引high (int): 列表的结束索引返回:None"""if low < high:pivot_index = partition(arr, low, high)quick_sort(arr, low, pivot_index - 1)quick_sort(arr, pivot_index + 1, high)# 测试用例
arr = [6, 5, 12, 10, 9, 1]
quick_sort(arr, 0, len(arr) - 1)
print(arr)

快速排序算法评价：

• 执行效率：最好情况时间复杂度为$O(nlogn)$，最坏情况时间复杂度为$O(n^2)$，平均情况时间复杂度为$O(nlogn)$

• 内存消耗：是一个原地排序算法，空间复杂度为$O(logn)$

• 稳定性：不是一个稳定的排序算法

参考文献

• 王争. 排序（下）：如何用快排思想在O(n)内查找第K大元素？极客时间. 2018