网站域名续费怎么做,成都锦江区网站建设公司,网站开发项目报告,网站建设需要步骤1、基本思想
归并排序采用分治法 (Divide and Conquer) 的一个非常典型的应。归并排序的思想就是先递归分解数组#xff0c;再合并数组。归并排序是一种稳定的排序方法。
将数组分解最小之后#xff08;数组中只有一个元素#xff0c;数组有序#xff09;#xff1b;然后…1、基本思想
归并排序采用分治法 (Divide and Conquer) 的一个非常典型的应。归并排序的思想就是先递归分解数组再合并数组。归并排序是一种稳定的排序方法。
将数组分解最小之后数组中只有一个元素数组有序然后合并两个有序数组基本思路是比较两个数组的最前面的数谁小就先取谁然后相应的指针就往后移一位然后再比较直至一个数组为空最后把另一个数组的剩余部分复制过来即可。
和选择排序一样归并排序的性能不受输入数据的影响但表现比选择排序好的多因为始终都是 O(nlogn) 的时间复杂度代价是需要额外的内存空间。
2、算法分析
归并排序算法是一个递归过程边界条件为当输入序列仅有一个元素时直接返回具体过程如下
如果输入内只有一个元素则直接返回否则将长度为 n 的输入序列分成两个长度为 n/2 的子序列分别对这两个子序列进行归并排序使子序列变为有序状态设定两个指针分别指向两个已经排序子序列的起始位置比较两个指针所指向的元素选择相对小的元素放入到合并空间用于存放排序结果并移动指针到下一位置重复步骤 3 ~ 4 直到某一指针达到序列尾将另一序列剩下的所有元素直接复制到合并序列尾
3、代码实现
1python实现
#!/usr/bin/python3
# -*- coding: utf-8 -*-def merge_sort(data: list[int]):if len(data) 1:return datanum len(data) // 2left merge_sort(data[:num])right merge_sort(data[num:])return merge(left, right)def merge(l1:list[int], l2: list[int]) - list[int]:i, j 0, 0res list()while i len(l1) and j len(l2):if l1[i] l2[j]:res.append(l1[i])i 1else:res.append(l2[j])j 1# 左边元素遍历结束if i len(l1):res l2[j:]# 右边元素遍历结束if j len(l2) :res l1[i:]return resdef main():data [54, 26, 93, 17, 77, 31, 45, 55, 20]# data [3,1,5,2,1,0]# data [7, 31, 23, 13, 35, 3]print(f排序前{data})res merge_sort(data)print(f排序后{res})if __name__ __main__:main()排序前[54, 26, 93, 17, 77, 31, 45, 55, 20] 排序后[17, 20, 26, 31, 45, 54, 55, 77, 93]
