Golang排序算法-归并排序

2018-09-15 17:49:35 george518 ...

前言

归并排序算法是一个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

自己下载测试一下结果吧

相似文章