快速排序算法的思路分兩部分：
1：在一個線性表中，找到一個基準(zhǔn)數(shù)據(jù)用tmp表示，然后將比tmp大的數(shù)據(jù)全部放在它的右邊，比tmp小的數(shù)據(jù)放在 它的左邊，其實就是快速找出tmp在線性表中正確的下標(biāo)位置:。
2：將線性表以tmp的下標(biāo) 分為左右兩部分，再分別找出左右兩部分的第一個位置的元素的正確的下標(biāo)，重復(fù)上面的分而治之的思路，最終線性表所有元素都找到其正確的位置，那么也就實現(xiàn)了排序

package ds

import "log"

//將線性表s中，i下標(biāo)的值s[i]按照從從小到大的順序放到正確的位置
//尋找s[i]在線性表s中按照一定順序(由小到大)所對應(yīng)的正確的位置,并返回排序后新的基準(zhǔn)下標(biāo)值
//r表示線性表的最大下標(biāo)的分界線
func ajustLinear(s []int, i, r int) int {

    //用tmp代表s[i]的值
    tmp := s[i]

    for i < r {
        //從線性表右邊向左尋找比tmp小的數(shù)據(jù)，存放到位置i后，基準(zhǔn)點 i++
        for i < r && s[r] > tmp {
            r--
        }
        if i < r {
            s[i] = s[r]
            i++
        }
        //從線性表左邊向右邊尋找比tmp大的數(shù)據(jù)，存放到r位置，r--
        for i < r && s[i] < tmp {
            i++
        }
        if i < r {
            s[r] = s[i]
            r--
        }

    }
    //當(dāng)i向右移動，r向左移動滿足 i==r時候，tmp基準(zhǔn)值在s的正確下標(biāo)就是i，將tmp賦值給s[i]，并返回新的基準(zhǔn)點i

    s[i] = tmp

    log.Printf("排序后的線性表:%v",s)
    return i

}

//分治算法實現(xiàn)快速排序,
func QuickSort(s []int,i,r int)  {

    if i<r {
        //首次找到基準(zhǔn)數(shù)據(jù)的正確位置后
        t := ajustLinear(s, i, r)
        //將線性表分為左右兩半，繼續(xù)遞歸查找基準(zhǔn)數(shù)據(jù)的正確位置
        QuickSort(s,i,t-1)
        QuickSort(s,t+1,r)
    }

}

以下是測試結(jié)果:

微信圖片_20200701105057.png

ps:類似這種分治的算法也可以用在二叉樹的遍歷上，重在干凈整潔一目了然的演示算法，不嚴(yán)謹(jǐn)?shù)牡胤綍簳r忽略