合并排序

合并排序

合并排序是基于分治思想的:
1. 如果数组足够小,直接对数组进行排序。
2. 否则,把数组划分为两个子数组,分别进行合并排序,然后合并两个有序的子数组为有序数组。

进行合并操作的复杂度为O(n),由于每次把数组分为2个子数组,需要进行lg(n)次合并,所以时间复杂度为O(n*lg(n)),。

每次合并都需要与两个子数组长度和 大小的数组,所以空间复杂度为O(n)。

实现


func MergeSort(arr []int) []int {
    length := len(arr)
    if length < 2 {
        return arr
    }

    mid := length >> 1
    //mid := length / 2
    larr := MergeSort(arr[0:mid])
    rarr := MergeSort(arr[mid:length])

    return merge(larr, rarr, asc)
}

func merge(larr []int, rarr []int, compare func(int, int) bool) []int {
    lLen, rLen := len(larr), len(rarr)
    arr := make([]int, lLen+rLen)

    l, r, i := 0, 0, 0
    for ; l < lLen && r < rLen; i++ {
        if compare(larr[l], rarr[r]) {
            arr[i] = rarr[r]
            r++
        } else {
            arr[i] = larr[l]
            l++
        }
    }

    if l >= lLen {
        util.ArrayCopy(rarr, r, arr, i, rLen-r)
    } else {
        util.ArrayCopy(larr, l, arr, i, lLen-l)
    }

    return arr
}

func asc(l int, r int) bool {
    return l > r
}

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据