归并排序 介绍

大致

介绍直接照抄百度上的

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

 

粗略

归并排序的核心思想是分治,若要将一个整的数列排序,可以将其分为两个小的数列分别排序,得到两个有序的小数列,再将这两个排好序的小数列合并,得到原来数列排序。并且,我们可以在 O(n) 的时间内完成合并。顺带一提,归并排序是稳定排序。更加详细的介绍可以看百度百科

 

复杂度

归并排序的复杂度是 O(nlogn),怎么证明也挺有趣的。就是根据 T(n)\ =\ 2T(n/2)\ +\ O(n)T(n)

 

闲话

在以前学会快排之后就再也没有关心过其他排序是怎么写,遇到排序题就喜欢直接用快排,最多写个随机化快排。如果有人卡快排,那么。。。(夭寿辣,卡快排辣!这破题不写辣!
这次突然会对归并排序感兴趣,完全是因为在百度百科中看到了归并排序的Go语言写法,不禁感叹一下。

 

Golang代码

Go写归并排序十分的简洁易懂,也许跟它的语言特性有关。
下面的代码中,Merge() 为合并, MergeSort() 为归并排序递归的本体。
至于 r[:mid] r[mid:] 这种奇怪的写法,可以去看看Go语言中的切片。
这也是Go的神奇之处吧。当然我对Go语言的认识非常肤浅!

 

未完结

发表评论

电子邮件地址不会被公开。 必填项已用*标注