快排

重新整理了一下快排的思路

快速排序的思想就是先指定列表的第一个元素为目标元素mid_value

我们用一个low指针和一个high指针

使得low指针前面的元素都小于mid_value

high指针后面的元素都大于mid_value

由于我们最后当low和high重合时使得list[low] = mid_value

所以先将high从后往前遍历，当碰到第一个小于mid_value的元素的时候，把它放在low当前的位置，此时mid_value就消失了

直到最后low和high重合时再把mid_value放进去

我们模拟下这个过程

mid_value = 54

54    26    93    17    77    31    44    55    20

low                                            high

先从high开始，检查到list[high] < mid_value的时候就停止    while low < high and list[high] < mid_value

然后把high所在位置的元素放在low所在位置，此时mid_value就消失了，直到最后low和high重合的时候才会重新将它替换回来

也就是在将mid_value替换之后以及mid_value重新出现之前列表中都是有一个重复的元素的

20    26    93    17    77    31    44    55    20

low                                            high

20    26    93    17    77    31    44    55    20

            low                                high

这一步list[low] > mid_value，然后把low当前的元素放到high上面

20    26    93    17    77    31    44    55    93

            low                                high

后面过程类似

20    26    44    17    77    31    44    55    93

            low                    high

20    26    44    17    77    31    77    55    93

                        low        high

20    26    44    17    31    31    77    55    93

                        low  high

20    26    44    17    31    31    77    55    93

                            lowhigh

到这一步重合了，就让mid_value重新出现

20    26    44    17    31    54    77    55    93

                            lowhigh

这样一来54就出现在了它应该出现的位置

然后我们再用递归对54左边的部分和右边的部分进行相同的操作

我们希望在原列表上操作，因此我们定义的变量应该传入以下几个参数

def quick_sort(list,first,last)

最后应该执行

quick(list,first,low-1)

quick(list,low+1,last)

总而言之，总结起来就是几句话

1.把第一个元素作为目标元素

2.从后往前遍历，当list[high] < mid_value时，把list[high]丢到low的位置上

3.从前往后遍历，当list[low] > mid_value时，把list[low]丢到high的位置上

4.当low和high重合后，将mid_value放在low的位置上，当然low < high 既是循环遍历的中止条件也是递归中止的条件，当只有一个元素的时候就不需要进行任何操作

5.当mid_value找到它应该出现的位置之后，再对前后两部分进行遍历

6.递归的过程总共要用到O(logn),每一次遍历的过程中要用到O(n)，所以最优时间复杂度是O(nlogn)

7.当数组完全逆序时，则相当于O(n)嵌套O(n)，即最坏时间复杂度为O(n^2)

```

def quick_sort(list,first,last):

    mid_value = list[first]

    low,high = first,last

    while low < high:

        while low < high and list[high] > mid_value:

            high -= 1

        list[low] = list[high]

        while low < high and list[low] < mid_value:

            low += 1

        list[high] = list[low]

    list[low] = mid_value

    quick_sort(list,first,low-1)

    quick_sort(list,low+1,last)

```