首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

谈谈归并排序

归并排序是建立在归并操作上的一种排序算法,该算法是采用分治法的典型的应用。

若数组的元素个数为N,其排序思想为:

①、分为log2N个小组,若最终结果为浮点数,即向上取整。分组之后,每一个小组只有一个元素,默认为有序的小组。

②、将每一个小组进行两两归并,并且在归并时进行从小到大的排序。如上图所示,8个小组归并同时从小到大排序,成为4个有序的小组;4个小组归并同时从小到大排序,成为2个有序的小组;2个小组归并同时从小到大排序,成为1个有序的小组。此时,这个小组就是数组本身自己,故,这个数组的排序工作此时已经完成。

说完了总体的归并思想,说一下小组之间的归并的做法,以2个小组归并成一个小组为例。

首先应该复制一份数组的元素,要知道,虽然归并排序的时间复杂度为O(n*logn),但是其空间复杂度为O(n),也就是说数组有多大的空间,排序就需要多大的辅助空间,在内存和硬盘相对便宜的今天,执行效率的提高似乎才是我们程序员最应该关心的问题。

除此之外,我们还需要几个标志位来辅助归并操作。k表示原数组中将要被存放归并2个小数组后的元素的下标;l(left)表示第一个归并小组的最左的下标的位置,相对应的r(right)表示第二个归并小组的最右的下标的位置,可以这么理解,我们进行归并的数组的下标范围为[l,r],而m则是两个小组的中间位置,也是分隔点。

初始化i和j都等于0,此时比较arr[i]和arr[j],若arr[i]>arr[j],则arr[k]=arr[j],与此同时,k++,j++,而i却不变;否则,则arr[k]=arr[i],与此同时,k++,i++,而j却不变。

循环往复,直到i==middle,或者j==r,此时说明有一个小组的归并操作已经完成了,将另外一个小组的元素顺次存放到arr[k]中即可完成归并操作。

看看代码。

上图为归并排序可以被外界调用的函数,第一个参数为要进行归并排序的数组,第二个参数为数组的大小。而在其内部是调用了一个名为__mergeSort()的函数,那个是内部调用的函数,相信有Python编程经验的程序员也看出来了,这个函数借鉴了Python的命名方案,即在用Python编写的类中,私有方法都是要以__开头的,这取代了在C++和Java中对私有方法进行private声明的做法。

这个函数的第1个参数是要进行归并排序的数组,第2个参数是数组的排序的左起点,第3个参数是数组的排序的右终点,即这个函数是对arr[L……r]进行归并排序的。

而在其内部,当r-L

接着说内部代码,先得获取mid,即归并的两部分的中间位置,即以这个中间位置将数组分成2个部分,对着2个部分进行归并排序。这个使用递归的思想,向对左部分进行归并,将左部分分成2个部分进行归并排序,直到左部分已经排序完成;再对右部分进行归并排序,将右部分分成2个部分进行归并排序,直到右部分已经排序完成;最后将左右部分合成一个整体。但是,上图代码做了一个优化,即只有当左部分的元素大于右部分的元素,即此时顺序仍然不正确时才进行左右两部分的排序;若左部分小于右部分,而此时左右部分皆在上面几行代码排序完成,就可以认为整个数组已经是有序的了,此时就没必要进行归并排序了。

总体的 归并排序思想讲解完毕,接下来说说左右两部分的归并过程。

我们要新开辟一片空间,这个空间是要和排序的数组片段等大的,这个辅助的数组时用来进行左右两部分的比较的,然后将合适的元素写入到原数组合适的位置中。这份代码完全是将上述的合并过程做了一个实现,并且在代码中已有清晰的注释,此时不再赘述。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180326G1IXLF00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券