西安市阎良区建设局网站,软件开发平台下载,搜索优化公司,苏中建设网站归并排序#xff08;Merge Sort#xff09;
基本思想#xff1a;
如果要排序一个数组#xff0c;我们先把数组从中间分成前后两部分#xff0c;然后对前后两部分分别排序#xff0c;再将排好序的两部分合并在一起#xff0c;这样整个数组就都有序了。
def merge_sort…归并排序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 ( n l o g n ) O(nlogn) O(nlogn)最坏情况时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)平均情况时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn) 内存消耗不是一个原地排序算法空间复杂度为 O ( n ) O(n) O(n) 稳定性是一个稳定的排序算法
快速排序Quick Sort
基本思想
如果要排序数组中下标从 p 到 r 之间的一组数据我们选择 p 到 r 之间的任意一个数据作为 pivot分区点。我们遍历 p 到 r 之间的数据将小于 pivot 的放到左边将大于 pivot 的放到右边将 pivot 放到中间。经过这一步骤之后数组 p 到 r 之间的数据就被分成了三个部分前面 p 到 q-1 之间都是小于 pivot 的中间是 pivot后面的 q1 到 r 之间是大于 pivot 的。根据分治、递归的处理思想我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q1 到 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): 列表的结束索引返回:Noneif 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 ( n l o g n ) O(nlogn) O(nlogn)最坏情况时间复杂度为 O ( n 2 ) O(n^2) O(n2)平均情况时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn) 内存消耗是一个原地排序算法空间复杂度为 O ( l o g n ) O(logn) O(logn) 稳定性不是一个稳定的排序算法
参考文献
王争. 排序下如何用快排思想在O(n)内查找第K大元素极客时间. 2018
