企业官网建设流程全解析

东莞好的网站建设公司,咸阳网站开发公司,wordpress猜你喜欢插件,关键词怎么优化到百度首页归并排序的核心逻辑是基于分治法的思想#xff0c;将一个大问题分解为若干个相同结构的小问题来解决。具体流程如下#xff1a; 分解阶段#xff1a;将待排序数组不断二分#xff0c;直到每个子数组只包含一个元素#xff08;单个元素天然有序#xff09;#xff1b;合并…归并排序的核心逻辑是基于分治法的思想将一个大问题分解为若干个相同结构的小问题来解决。具体流程如下分解阶段将待排序数组不断二分直到每个子数组只包含一个元素单个元素天然有序合并阶段通过Merge函数将两个有序的子数组合并成一个新的有序数组递归回溯随着递归返回较小的有序段被逐步合并为更大的有序段最终形成整个有序数组。核心操作Merge函数以两路归并为例defmerge(arr,left,mid,right):# 创建临时数组存储左右两部分left_arrarr[left:mid1]right_arrarr[mid1:right1]ij0# 左右子数组的指针kleft# 原数组中的位置# 按升序将元素复制回原数组whileilen(left_arr)andjlen(right_arr):ifleft_arr[i]right_arr[j]:arr[k]left_arr[i]i1else:arr[k]right_arr[j]j1k1# 复制剩余元素whileilen(left_arr):arr[k]left_arr[i]i1k1whilejlen(right_arr):arr[k]right_arr[j]j1k1递归实现MSort函数defmsort(arr,left,right):ifleftright:mid(leftright)//2msort(arr,left,mid)# 递归排序左半部分msort(arr,mid1,right)# 递归排序右半部分merge(arr,left,mid,right)# 合并已排序的两部分归并排序性能分析时间复杂度始终为 $ O(n \log n) $无论最好、最坏或平均情况空间复杂度$ O(n) $需要额外的辅助空间用于合并过程稳定性稳定排序算法相等元素的相对位置不会改变是否原地非原地排序需要额外内存适用场景适合对稳定性有要求且数据量较大的排序任务如外部排序。非递归版本的归并排序也称自底向上的归并排序不使用递归来分解数组而是从最小粒度长度为1的子数组开始逐步合并成更大的有序段直到整个数组有序。实现思路初始时将每个元素看作一个长度为1的有序子数组每次将相邻的两个有序子数组进行两路归并形成长度为2、4、8……的有序段使用循环控制当前要合并的子数组长度size每次翻倍在每一趟中遍历整个数组对每一对相邻子数组调用merge函数合并。Python代码实现非递归归并排序defmerge(arr,left,mid,right):# 辅助函数合并 arr[left..mid] 和 arr[mid1..right]temp[]i,jleft,mid1# 双指针合并两个有序部分whileimidandjright:ifarr[i]arr[j]:temp.append(arr[i])i1else:temp.append(arr[j])j1# 复制剩余元素whileimid:temp.append(arr[i])i1whilejright:temp.append(arr[j])j1# 回写到原数组foridx,valinenumerate(temp):arr[leftidx]valdefmerge_sort_iterative(arr):nlen(arr)size1# 当前子数组的长度从1开始逐步翻倍whilesizen:# 对每一对长度为 size 的子数组进行合并forleftinrange(0,n,2*size):midmin(leftsize-1,n-1)rightmin(left2*size-1,n-1)# 如果 mid right说明有两个子数组可以合并ifmidright:merge(arr,left,mid,right)size*2# 子数组长度翻倍示例演示data[38,27,43,3,9,82,10]merge_sort_iterative(data)print(data)# 输出: [3, 9, 10, 27, 38, 43, 82]特点分析无需递归栈避免了递归带来的函数调用开销和栈溢出风险时间复杂度仍为 $ O(n \log n) $共需 $ \lceil \log_2 n \rceil $ 趟归并每趟耗时 $ O(n) $空间复杂度$ O(n) $用于临时数组适用场景适合栈空间受限或需要完全可控迭代过程的系统中。