排序（二）

归并排序

归并排序使用分治思想，分支算法一般都是用递归来实现的。
归并排序是一个稳定的排序算法，在merge过程中可以保证值相同的元素在合并前后顺序不变；
归并排序的时间复杂度是O(nlogn)，他的执行效率和排序的原始数组的有序成都是无关的，任何情况的时间复杂度都是O(nlogn)
但是归并排序在合并的时候需要借助额外的存储空间，空间复杂度为O(n)，所以不是原地排序算法；

快速排序

如果快排的partition函数不使用额外内存空间来进行，则可以做到原地排序；
快排是不稳定的；
虽然快速排序最坏情况的时间复杂度是O(n2)，但是平均时间复杂度为O(nlogn)，而且最坏情况的概率很小，可以通过合理地选择pivot来避免这种情况；

代码实现（Golang）

type Sort struct {
    data []int
}

func (s Sort) Merge_sort() {
    merge_sort_c(s.data)
}

func merge_sort_c(a []int) {
    if len(a) <= 1 {
        return
    }
    mid := len(a) / 2
    merge_sort_c(a[:mid])
    merge_sort_c(a[mid:])
    merge(a, mid)
}

func merge(a []int, mid int) {
    leftArray := make([]int, len(a[:mid]))
    copy(leftArray, a[:mid])
    rightArray := make([]int, len(a[mid:]))
    copy(rightArray, a[mid:])
    i, j := 0, 0
    key := 0
    for ; key < len(a); key++ {
        if i < len(leftArray) && j < len(rightArray) {
            if leftArray[i] <= rightArray[j] {
                a[key] = leftArray[i]
                i++
            } else {
                a[key] = rightArray[j]
                j++
            }
        } else {
            break
        }
    }
    if i < len(leftArray) {
        for ; i < len(leftArray); i++ {
            a[key] = leftArray[i]
            key++
        }
    }
    if j < len(rightArray) {
        for ; j < len(rightArray); j++ {
            a[key] = rightArray[j]
            key++
        }
    }
}

func (s Sort) Quick_sort() {
    quick_sort_c(s.data)
}

func quick_sort_c(a []int) {
    if len(a) <= 1 {
        return
    }
    q := partition(a)
    quick_sort_c(a[:q])
    quick_sort_c(a[q:])
}

func partition(a []int) int {
    pivot := a[len(a)-1]
    i, j := 0, 0
    for ; i < len(a)-1; i++ {
        if a[i] < pivot {
            change(a, i, j)
            j++
        }
    }
    change(a, j, len(a)-1)
    return j
}
func change(a []int, left, right int) {
    temp := a[left]
    a[left] = a[right]
    a[right] = temp
}

有疑问加站长微信联系（非本文作者）