快速排序

快速排序用到的是分治思想。
实现方法是，在序列中先确定一个比较值k，左边部分的值比k小，右边部分的值比k大，然后对左边和右边两部分继续获取各自的比较值k，依次递归，直到都排列完成，从而整个数列都变得有序。
退出条件是，左边增长的角标大于右边缩小的角标。
如果选取的比较值k为最左边一个，则需要从右边优先开始比较；如果选取的比较值为k最右边第一个，则需要从左边优先开始比较。

排序基本思路

给定一个数组，比如[3，6，1，7，2，4，8]。
先选定一个k，作为比较值，比如选取数组第一个数值，3，最左边作为比较值。
从右边开始，同3比较，右边第一个数值8，因为8>3,所以8不需要动，此时还是[3，6，1，7，2，4，8]。
接着比较倒数第二位4，4>3，也不需要动，此时还是[3，6，1，7，2，4，8]。
接着倒数第三位2，2<3，则将2放入3的位置，变成[2,6,1,7,2,4,8]，此时右边角标为4。
触发了右边的变换，所以这次开始从左边，2<3，则不需要动，[2,6,1,7,2,4,8]。
左边继续走，第二个为6，6>3，则需要变换[2,6,1,7,6,4,8]，此时左边角标为1
左边触发了交换，下面轮到右边，右边7，7>3，不变，[2,6,1,7,6,4,8]。
右边继续，右边1，1<3，则交换，变成[2,1,1,7,6,4,8]，此时右边角标为1。
轮到左边，左边继续，为1，依旧是[2,1,1,7,6,4,8]，此时左边角标为2。
继续轮到左边，此时左边发现自己角标大于右边角标，则停止，将k的值赋予当前左边角标，数组也就成了[2,1,3,7,6,4,8]。
之后出现左右两个子数组，继续递归，直到全部完成。

代码实现

https://www.jianshu.com/p/2b2f1f79984e

quicklist = [3,6,1,7,2,4,8]


def quick_sort(arr):
    return q_sort(arr, 0, len(arr) - 1)

def q_sort(arr, left, right):
    if left < right:
        pos = get_pos(arr,left,right)
        # 递归左边排序，第一次left为0，pos-1的值为get_pos排序一次后的pos位置左移一位。
        q_sort(arr,left,pos-1)
        # 递归右边排序，pos+1的值为get_pos排序一次后的pos位置右移一位。
        q_sort(arr,pos+1,right)
    # 得到最终排序完的列表
    return arr

def get_pos(arr,left,right):
    # 左边第一位作为pos值
    pos = arr[left]

    # 判断左右位置角标是否相遇
    while left < right:
        while left < right and arr[right] >= pos:
            # 右边角标缩小
            right -=1
        # 将右边的换到左边
        arr[left] = arr[right]

        while left < right and arr[left] <= pos:
            # 左边角标放大
            left +=1
        # 将左边的换到右边
        arr[right] = arr[left]
    # 当左边和右边位置碰到的时候，让此时左边的位置成为pos值，因为pos值当时是被抠出来的。
    arr[left] = pos
    # 获取此时的left位置
    return left

print(quick_sort(quicklist))

总结

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是 O(N2)，它的平均时间复杂度为 O(NlogN)。

refer

https://wiki.jikexueyuan.com/project/easy-learn-algorithm/fast-sort.html
https://www.jianshu.com/p/2b2f1f79984e