quick sort

分治思想，每次選中一個基準，然后為此基準找到合適位置，使得左邊全部小于此基準，右邊全部大于此基準。然后對左右兩邊的數(shù)組重復以上步驟。

如何為基準找到合適位置？同時從左往右、從右往左用下標掃描數(shù)組，如果分別掃描到<基準，>基準的樹，就交換他們位置，如果掃描過程中下標交叉，說明交叉點就是基準應該放置的位置。

go代碼

func portition(slice *[]int, start, end int) int {

    left := start + 1

    right := end

    for left <= right {

        for left <= right && (*slice)[left] <= (*slice)[start] {

            left++

        }

        for left <= right && (*slice)[right] >= (*slice)[start] {

            right--

        }

        if right <= left {

            break

        }

        tmp := (*slice)[left]

        (*slice)[left] = (*slice)[right]

        (*slice)[right] = tmp

    }

    log.Println(start, end, left, right)

    tmp := (*slice)[start]

    (*slice)[start] = (*slice)[right]

    (*slice)[right] = tmp

    return right

}

func sortInt(unsort *[]int, s, e int) {

    if s >= e {

        return

    }

    log.Println(unsort)

    mid := portition(unsort, s, e)

    sortInt(unsort, s, mid-1)

    sortInt(unsort, mid+1, e)

}

heap sort

有點類似冒泡，每次選出最大值放到最右邊，然后迭代。只不過采用完全二叉樹的形式去找最大值。

二叉樹：每個節(jié)點最多2個子元素

滿二叉樹 full binary tree：每個節(jié)點0或2個子元素

完全二叉樹 complete binary tree：剛好可以用數(shù)組完整表示的二叉樹。

步驟：

1.根據(jù)數(shù)組初始化heap，使得最大值在對頂，max-heap

2.將堆頂值與末尾值交換位置，然后再次構造max-heap

3.對步驟2迭代

java代碼
參考此連接
https://www.programiz.com/dsa/heap-sort