做ppt到哪个网站找图片,东莞网络营销,陕西省西安市网站建设公司,德阳网站网站建设一、是什么
归并排序#xff08;Merge Sort#xff09;是建立归并操作上的一种有效#xff0c;稳定的排序算法#xff0c;该算法是采用分治法的一个非常典型的应用
将已有序的子序列合并#xff0c;得到完全有序的序列#xff0c;即先使每个子序列有序#xff0c;再使…一、是什么
归并排序Merge Sort是建立归并操作上的一种有效稳定的排序算法该算法是采用分治法的一个非常典型的应用
将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序
例如对于含有 n 个记录的无序表首先默认表中每个记录各为一个有序表只不过表的长度都为 1
然后进行两两合并使 n 个有序表变为n/2 个长度为 2 或者 1 的有序表例如 4 个小有序表合并为 2 个大的有序表
通过不断地进行两两合并直到得到一个长度为 n 的有序表为止
例如对无序表{49386597761327}进行归并排序分成了分、合两部分
如下图所示 归并合过程中每次得到的新的子表本身有序所以最终得到有序表
上述分成两部分则称为二路归并如果分成三个部分则称为三路归并以此类推
二、如何实现
关于归并排序的算法思路如下 分把数组分成两半再递归对子数组进行分操作直至到一个个单独数字 合把两个数合成有序数组再对有序数组进行合并操作直到全部子数组合成一个完整的数组 合并操作可以新建一个数组用于存放排序后的数组比较两个有序数组的头部较小者出队并且推入到上述新建的数组中如果两个数组还有值则重复上述第二步如果只有一个数组有值则将该数组的值出队并推入到上述新建的数组中 用代码表示则如下图所示
function mergeSort(arr) { // 采用自上而下的递归方法const len arr.length;if(len 2) {return arr;}let middle Math.floor(len / 2),left arr.slice(0, middle),right arr.slice(middle);return merge(mergeSort(left), mergeSort(right));
}function merge(left, right)
{const result [];while (left.length right.length) {if (left[0] right[0]) {result.push(left.shift());} else {result.push(right.shift());}}while (left.length)result.push(left.shift());while (right.length)result.push(right.shift());return result;
}上述归并分成了分、合两部分在处理分过程中递归调用两个分的操作所花费的时间为2乘T(n/2)合的操作时间复杂度则为O(n)因此可以得到以下公式
总的执行时间 2 × 输入长度为n/2的sort函数的执行时间 merge函数的执行时间O(n)
当只有一个元素时T(1) O(1)
如果对T(n) 2 * T(n/2) O(n) 进行左右 / n的操作得到 T(n) / n (n / 2) * T(n/2) O(1)
现在令 S(n) T(n)/n则S(1) O(1)然后利用表达式带入得到S(n) S(n/2) O(1)
所以可以得到S(n) S(n/2) O(1) S(n/4) O(2) S(n/8) O(3) S(n/2^k) O(k) S(1) O(logn) O(logn)
综上可得T(n) n * log(n) nlogn
关于归并排序的稳定性在进行合并过程在1个或2个元素时1个元素不会交换2个元素如果大小相等也不会交换由此可见归并排序是稳定的排序算法
三、应用场景
在外排序中通常使用排序-归并的策略外排序是指处理超过内存限度的数据的排序算法通常将中间结果放在读写较慢的外存储器如下分成两个阶段
排序阶段读入能够放进内存中的数据量将其排序输出到临时文件一次进行将带排序数据组织为多个有序的临时文件归并阶段将这些临时文件组合为大的有序文件
例如使用100m内存对900m的数据进行排序过程如下
读入100m数据内存用常规方式排序将排序后的数据写入磁盘重复前两个步骤得到9个100m的临时文件将100m的内存划分为10份将9份为输入缓冲区第10份为输出缓冲区进行九路归并排序将结果输出到缓冲区 若输出缓冲区满将数据写到目标文件清空缓冲区若缓冲区空读入相应文件的下一份数据
参考文献
https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/1639015https://chowdera.com/2021/09/20210920201630258d.html#_127https://juejin.cn/post/6844904007899561998
更多前端资源 GitHub
