快速排序大白话解释

今天给人说了一下这个快速排序，说一下这个过程，通俗易懂。这里都以递增排序为例
这个算法就是先选一个数，一般是第一个，将他放到正确的位置，同时，将其他数据比他小的放在他左边，比他大的放在他右边。这样这个数就把总的数据集分成左右两部分（不包括自己这个数），然后左右两部分分别在执行上面的过程，直到这个区间只剩一个数。由于经过排序后的数，左边都比中间值小，右边都比中间值大，所以当区间分到只有一个值的时候，所有的数都已经完成排序

实际例子数据演示：

数据源(上方圆括号标识作用域，就是需要排序的区域)：
三角形标识本次基准数，波浪线标识将要交换的值

2，3，0，1，4

image.png

第一次，拿第一个2为基准，从后向前找第一个比他小的交换，这里与1交换，这里数值4本来就符合比他大，就跳过，一直找到第一个符合比他小的数值，得

image.png

执行过交换的动作，比较就换成从前向后找比他大的值，交换。这里注意看他的作用域。刚开始是整个区间，经过一次交换，他经过的（比较过或者交换过）区间都已经是符合要求的，这个需要比较的区间就越来越小。
这里第一个比他大的值是3，进行交换得：

image.png

再次交换，0和2，直到作用域区间只剩自己，这时候，已经符合2左边的数都比他小，右边都比他大

image.png

这就完成了一次排序

注意，都是以最开始的那个基本值为基准去交换

本次排序达到的效果是：一开始选的2，左边都比他小，右边都比他大。也就是说选择的那个数经过交换达到正确的位置，这时候2是正确的位置

后续操作解释：

现在以2为基本，把他左边看作新的一个区间，右边也看成一个区间，不包括自己。
左边是【1，0】，右边是【3，4】

image.png

再次用上面相同的方法进行排序，选择一个基准进行排序，不断细分，就可以完成排序，不管多长的数，经过这样分割后，直到一个数就完成，实际的代码通过逻辑自己定义。

这里写一个长一点的例子：0到9的排序

第一步，以3为基准，从后向前，3和0交换

image.png
第二步，以3为基准，从前向后，3和9交换
image.png
第三步，以3为基准，从后向前，3和1交换
image.png
第四步，以3为基准，从前向后，3和4交换
image.png
第五步，交换后，以及达到3左边比他小，右边比他大，将其分成左右两个区间，重复上述操作
image.png

第六步，左侧排序，左侧已经符合，不用排序
第七步，右侧排序，以7为基准

image.png image.png image.png image.png

第八步，出现新的区间，分别左右排序

image.png
image.png

最后，将左右的所有排列好的小区间拼凑起来就是完整区间

0，1，2
3
45
6
7
8，9
用区间显示就是{0，1，2}，3，{  {4，5，6}，7，{8，9}}  }
得出：0，1，2，3，4，5，6，7，8，9

时间复杂度和空间复杂度就不说了，说不明白，实际的官方解释百度一大堆

实际得代码，效率不必他们网上得低：

func querySort(list []int) {
    if len(list) < 2 {
        return
    }
    start, stop := 0, len(list)-1
    flag := true //标识中间值在前还是在后
    for start != stop {
        for list[start] <= list[stop] && start != stop {
            if flag {
                stop--
            } else {
                start++
            }
        }
        if start == stop {
            break
        }
        list[start], list[stop] = list[stop], list[start]
        flag = !flag //交换过一次后，不是标识的位置需要去除
        if flag {
            stop--
        } else {
            start++
        }
        if start == stop {
            break
        }
    }
    querySort(list[:start])
    querySort(list[start+1:])
}