小编给大家分享一下web开发中如何实现归并排序,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
归并排序
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:
自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
自下而上的迭代;
和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
算法步骤
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
设定两个指针,最初位置分别为两个已经排序序列的起始位置;
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
重复步骤 3 直到某一指针达到序列尾;
将另一序列剩下的所有元素直接复制到合并序列尾。
来源:https://github.com/hustcc/JS-Sorting-Algorithm
算法演示
动画演示加载有点慢,请稍等片刻
排序动画过程解释
首先,将数字分割成两片区域
再将数字分割成两片区域
依次划分
直到每片区域只有一个元素
分割完成
接下来,将分割的每片区域进行合并组合
合并时,按照数字的升序移动,使得合并后的数字在组内按升序排列
当合并包含多个数字的组时,比较开头的数字,移动其中较小的数字
比如在动画中,比较开头的 4 和 3
其中 4 大于 3, 因此移动 3
按照同样的逻辑去比较该列剩余的头数
4 小于 7 ,所以移动 4
同样的逻辑去进行接下来的操作
递归的重复组的合并操作,直到所有数字都在一个组中。
完成 归并排序
代码实现
为了更好的让读者用自己熟悉的编程语言来理解动画,笔者将贴出多种编程语言的参考代码,代码全部来源于网上。
C++代码实现
Java代码实现
Python代码实现
JavaScript代码实现
以上是“web开发中如何实现归并排序”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注编程网行业资讯频道!