前言
归并排序算法是一个O(nlogn)级别的算法。这种算法体现了“分而治之”的算法思想,是一个可以提供使用的工具,意思是,以后遇到新的问题,可以先自问一下:分而治之能解决吗?
这一篇,我们先讨论实践这一思想的算法之一:归并排序算法。
所谓归并排序算法:
是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。 —-from 百度百科
思路分析
要了解归并排序算法,首先先要弄清楚什么是归并(正确的废话),将两个顺序序列合并成一个顺序序列的操作叫做归并。举个栗子:
A序列:2,4,6,8
B序列:1,3,5,7,9
把AB两个序列合并成C序列:123456789,这个过程就叫做归并。
这里先暂时不用去想如何实现归并的代码。
先说一点启示:我们对一个序列进行排序的时候,如果能把一个序列C,分成两部分A和B,然后每个部分进行顺序排列,然后在归并到一起,就可以完成整个数组排序工作。
那如何把A序列变成顺序的序列呢?同样道理,我们把A也分成两个部分A0和A1(如果可以分的话),然后对A0和A1两部分也进行分别排序,然后再将A0和A1归并成A,此时A就是顺序的序列了。
同理B序列也是如此。
再同理,A0也可以一样的递归操作。
wow,归并排序算是说明白了,其实就是分分合合的事情而已。
Golang代码
是时候祭出golang代码的时候了:
/************************************************************
** @Description: merge
** @Author: haodaquan
** @Date: 2018-09-02 18:16
** @Last Modified by: haodaquan
** @Last Modified time: 2018-09-02 18:16
*************************************************************/
package merge
import (
"github.com/george518/PPGo_algorithm/sort/insertion"
)
func merge(arr *[]int, l, mid, r int64) {
//计算数组长度
len := r - l + 1
//重新开辟一个数组空间,长度和arr一样,并做赋值
newArr := make([]int, len)
for i := l; i <= r; i++ {
newArr[i-l] = (*arr)[i]
}
//设定 i 为左半部分的起始索引位置
//j为右半部分的起始索引位置
var i = l
var j = mid + 1
//迭代,从l到r;
for k := l; k <= r; k++ {
//i-l表示左半部分没有处理过的下标
//j-l表示有半部分没有处理过的下标
switch {
case i > mid:
//说明左半部分已经处理完毕,处理右边剩余的
(*arr)[k] = newArr[j-l]
j++
case j > r:
//说明右半部分已经处理完毕,处理左边剩余的
(*arr)[k] = newArr[i-l]
i++
case newArr[i-l] > newArr[j-l]:
//比较两边部分的领头元素,如果右半部分领头元素小,则赋值给k索引
(*arr)[k] = newArr[j-l]
j++
default:
(*arr)[k] = newArr[j-l]
j++
}
}
}
func sort(arr *[]int, l, r int64) {
//如果数组元素小于1个,直接return
if l >= r {
return
}
//优化点2:如果元素小于15,使用插入排序法效率更高一些
if r-l <= 15 {
insertion.SortApart(arr, l, r)
return
}
//取数组中部的一个点作为分组,分别是arr[l,mid]和arr[mid+1,r]
mid := (l + r) / 2
//左边部分递归
sort(arr, l, mid)
//右边部分递归
sort(arr, mid+1, r)
//因为经过上一步的递归,左边和右边部分的数组是顺序的,
// 因此如果左边最后一个元素arr[mid],是左边数组最大的一个,而arr[mid+1]是右边数组最小的一个,
// arr[mid]<=arr[mid+1] 说明数组已经排好序,不需要merge了
if (*arr)[mid] > (*arr)[mid+1] {
merge(arr, l, mid, r)
}
}
func Sort(arr []int) []int {
len := int64(len(arr))
sort(&arr, 0, len-1)
return arr
}
优缺点:
这种排序比较稳定。特别是对于近乎有序的数组效率非常高。
Github完整代码
下面是代码的实现以及测试代码:
https://github.com/george518/PPGo_algorithm/tree/master/sort/merge
自己下载测试一下结果吧