算法----(4)快速排序

从图中我们可以看到：

left指针，right指针，base参照数。

其实思想是蛮简单的，就是通过第一遍的遍历（让left和right指针重合）来找到数组的切割点。

第一步：首先我们从数组的left位置取出该数（20）作为基准（base）参照物。

第二步：从数组的right位置向前找，一直找到比（base）小的数，

如果找到，将此数赋给left位置（也就是将10赋给20）

此时数组为：10，40，50，10，60，

left和right指针分别为前后的10。

第三步：从数组的left位置向后找，一直找到比（base）大的数，

如果找到，将此数赋给right的位置（也就是40赋给10），

此时数组为：10，40，50，40，60，

left和right指针分别为前后的40。

第四步：重复“第二,第三“步骤，直到left和right指针重合，

最后将（base）插入到40的位置，

此时数组值为： 10，20，50，40，60，至此完成一次排序。

第五步：此时20已经潜入到数组的内部，20的左侧一组数都比20小，20的右侧作为一组数都比20大，

以20为切入点对左右两边数按照"第一，第二，第三，第四"步骤进行，最终快排大功告成。

 1 def partion(nums, left, right):
 2     key = nums[left]
 3     while left < right:
 4         # right下标位置开始，向左边遍历，查找不大于基准数的元素
 5         while left < right and nums[right] >= key:
 6             right -= 1
 7         if left < right:  # 找到小于准基数key的元素,然后交换nums[left],nums[right]
 8             nums[left], nums[right] = nums[right], nums[left]
 9         else:   # left〉=right 跳出循环
10             break
11         # left下标位置开始，向右边遍历，查找不小于基准数的元素
12         while left < right and nums[left] < key:
13             left += 1
14         if left < right:  # 找到比基准数大的元素，然后交换nums[left],nums[right]
15             nums[right],nums[left] = nums[left],nums[right]
16         else:  # left〉=right 跳出循环
17             break
18     return left  #此时left==right 所以返回right也是可以的
19 
20 
21 def quick_sort_standord(nums, left, right):
22     if left < right:
23         key_index = partion(nums, left, right)
24         quick_sort_standord(nums, left, key_index)
25         quick_sort_standord(nums, key_index+1, right)
26 
27 
28 if __name__ == '__main__':
29     nums = [5, 6, 4, 2, 3, 1]
30     print(nums)
31     quick_sort_standord(nums, 0, len(nums)-1)
32     print(nums)