归并排序
本文最后更新于:2021年3月31日 上午
代码模板
1 |
|
代码原理
扫描
归并排序的本质是将一长段数据分为两个部分,然后通过两个指针一起从头开始对比,将更小的数字放入一个临时数组中,在数组一和数组二对比完毕以后,临时数组里面的数据理论上来说就是从小到大(或者按照需求改为从大到小)排好了。
首先通过位运算划分中间点mid
,其中以最小的数组为单位划分为A和B两个数组,这两个数组在分治的”最小单位“下理论上应该是从小到大依次分布的,只不过A、B两个数组相互独立。这个时候利用两个指针i
和j
对两个数组进行分别扫描,大致示意图如下
1 |
|
填入临时数组
定义一个临时数组tmp,在扫描的过程中,以上示例来说,由于A
的1
要比B
的2
更小,所以1
被采用
,定义一个计数器cnt
,将tmp[cnt++]
定义为1(更小的数字)
然后依次进行填充,直到两个数组都被扫描并且使用完毕
写入原数组
这个时候通过一个简单的for
循环将排序好的tmp
填入需要排序的q
数组对应的位置即可。
时间复杂度
O(nlogn)
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!