排序算法

—— by golang

排序被认为是算法研究中最基础的问题，也是被应用最为广泛的算法之一。本文结合Golang语法特性实践几种最经典的排序算法： 1）归并排序 2）堆排序 3）快速排序

注：拆解算法为一个或几个最小化步骤，然后通过递归调用组装起来，是算法中常用策略；递归过程中，很重要的一点是要有完备的收敛条件；

归并排序

归并排序是利用分治策略的代表性排序算法；（注：归并排序不是原址的，需要额外空间成本） 算法思想：将数组一分为二，左右两个数组分别递归进行归并排序，当某个数组只有一个元素时天然有序（收敛），然后合并两个小的有序数组得到一个大的有序数组；该算法时间复杂度为：O(nlgn)；

package algo

// SortMerge
func SortMerge(s []int) []int {
    idx := len(s) / 2
    if idx <= 0 {
        return s
    }
    // recursion
    return merge(SortMerge(s[:idx]), SortMerge(s[idx:]))
}

// merge left & right
func merge(l, r []int) []int {
    ss := []int{}
    for i, j := 0, 0; ; {
        if i >= len(l) {
            if j >= len(r) {
                break
            } else {
                ss = append(ss, r[j])
                j++
            }
        } else {
            if j >= len(r) || l[i] < r[j] {
                ss = append(ss, l[i])
                i++
            } else {
                ss = append(ss, r[j])
                j++
            }
        }
    }
    return ss
}

堆排序

堆排序是借助二叉堆特性的排序算法；二叉堆可以理解为近似二叉树的数组，而最大堆是二叉堆两种形式之一（另一为最小堆），它保持根节点大于叶节点； 算法思想：通过一个维持最大堆特性的方法校正数组为最大堆，然后交换根节点到堆的最后（注意不是整个数组的最后），如此递归进行，直到堆空（收敛）；该算法时间复杂度为：O(nlgn)；

package algo

// SortHeap
func SortHeap(s []int) {
    heapsize := buildMaxHeap(s)
    for i := len(s) - 1; i > 0; i-- {
        s[0], s[i] = s[i], s[0]
        heapsize--
        maxHeapify(s, heapsize, 0)
    }
}

func parent(i int) int {
    return (i - 1) / 2
}

func left(i int) int {
    return i*2 + 1
}

func right(i int) int {
    return i*2 + 2
}

func maxHeapify(s []int, heapsize, i int) {
    li := left(i)
    ri := right(i)

    largest := i
    if li < heapsize && s[li] > s[i] {
        largest = li
    }

    if ri < heapsize && s[ri] > s[largest] {
        largest = ri
    }

    if largest != i {
        s[i], s[largest] = s[largest], s[i]
        maxHeapify(s, heapsize, largest)
    }
}

func buildMaxHeap(s []int) int {
    heapsize := len(s)
    for i := len(s) / 2; i >= 0; i-- {
        maxHeapify(s, heapsize, i)
    }
    return heapsize
}

快速排序

快速排序也是利用分治策略的排序算法；与归并排序不一样，快排算法是原址的（无需额外空间成本）； 算法思想：以数组中某个元素为参照，小于该元素的交换到数组前面（大于该元素的自然就全在后面）；然后对该元素前后两个数组递归进行快排，当数组中只有一个元素时天然有序（收敛）；该算法时间复杂度期望值为：O(nlgn)；

注：参照的选择具有一定随机性，故而快排不是稳定复杂度的排序算法；最坏复杂度为n^2；

package algo

// SortQuick
func SortQuick(s []int) {
    if len(s) > 0 {
        q := partition(s)
        SortQuick(s[:q])
        SortQuick(s[q+1:])
    }
}

func partition(s []int) int {
    i := 0
    r := len(s) - 1
    for j := i; j < r; j++ {
        if s[j] < s[r] {
            if j != i {
                s[i], s[j] = s[j], s[i]
                // fmt.Printf("%+v %d <= %d, %d \n", s, i, j, r)
            }
            i++
        }
    }
    if i != r {
        s[i], s[r] = s[r], s[i]
        // fmt.Printf("%+v %d <= %d \n", s, i, r)
    }
    return i
}