手把手教媳妇-复习快速排序算法

快速排序算法的思路分两部分：
1：在一个线性表中，找到一个基准数据用tmp表示，然后将比tmp大的数据全部放在它的右边，比tmp小的数据放在 它的左边，其实就是快速找出tmp在线性表中正确的下标位置:。
2：将线性表以tmp的下标 分为左右两部分，再分别找出左右两部分的第一个位置的元素的正确的下标，重复上面的分而治之的思路，最终线性表所有元素都找到其正确的位置，那么也就实现了排序

package ds

import "log"

//将线性表s中，i下标的值s[i]按照从从小到大的顺序放到正确的位置
//寻找s[i]在线性表s中按照一定顺序(由小到大)所对应的正确的位置,并返回排序后新的基准下标值
//r表示线性表的最大下标的分界线
func ajustLinear(s []int, i, r int) int {

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

    for i < r {
        //从线性表右边向左寻找比tmp小的数据，存放到位置i后，基准点 i++
        for i < r && s[r] > tmp {
            r--
        }
        if i < r {
            s[i] = s[r]
            i++
        }
        //从线性表左边向右边寻找比tmp大的数据，存放到r位置，r--
        for i < r && s[i] < tmp {
            i++
        }
        if i < r {
            s[r] = s[i]
            r--
        }

    }
    //当i向右移动，r向左移动满足 i==r时候，tmp基准值在s的正确下标就是i，将tmp赋值给s[i]，并返回新的基准点i

    s[i] = tmp

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

}

//分治算法实现快速排序,
func QuickSort(s []int,i,r int)  {

    if i<r {
        //首次找到基准数据的正确位置后
        t := ajustLinear(s, i, r)
        //将线性表分为左右两半，继续递归查找基准数据的正确位置
        QuickSort(s,i,t-1)
        QuickSort(s,t+1,r)
    }

}

以下是测试结果:

微信图片_20200701105057.png

ps:类似这种分治的算法也可以用在二叉树的遍历上，重在干净整洁一目了然的演示算法，不严谨的地方暂时忽略