快速排序的主要原理是设置一个基准值，利用游标将比基准值小的数移到数组左边，比基准值大的数移到数组右边，再将基准值放在中间。将基准值左右两边的数组利用迭代，分别进行相同操作，最后得到完整序列
假设一个数组为 array=[4,2,8,7,1,3,9]
选定基准值为4，mid_value=4，游标 low = 0，high = 6
first 从左向右移动，low 从右向左移动，采用填坑的思路，先移动 high
high= 6，array[high]= 9，满足条件，继续移动；
high= 5，array[high]= 3，不满足条件，将 array[high] 的值赋给 array[low]，将数组变为：array=[3,2,8,7,1,3,9]，之后考察 low 游标：
low= 0，array[low]= 4，满足条件，继续移动；
low= 1，array[low]= 2，满足条件，继续移动；
low= 2，array[low]= 8，不满足条件，将 array[low] 的值赋给 array[high]
将数组变为：array=[3,2,8,7,1,8,9]；
high= 4，array[high]= 1，不满足条件，执行同上操作，array=[3,2,1,7,1,8,9]
low= 2，array[low]= 1，满足条件，继续移动；
low= 3，array[low]= 7，不满足条件，执行操作，array=[3,2,1,7,7,8,9]
high= 3，high=low，达到结束条件， array[high] = array[low] = mid_value = 4
array=[3,2,1,4,7,8,9]
上述过程的参考代码：
while (low < high):while array[high] >= mid_value and low < high:high = high - 1array[low] = array[high]while array[low] <= mid_value and low < high:low = low + 1array[high] = array[low]array[low] = mid_value
第一次的排序结束，之后将mid_value左右两边的数组 [3,2,1] 和 [7,8,9] 分别按照上述的规则迭代。
完整程序如下：
def quick_sort(array, first, last):if first >= last: #空列表或无效列表returnlow = firsthigh = lastmid_value = array[low]while (low < high):while array[high] >= mid_value and low < high:high = high - 1array[low] = array[high]while array[low] <= mid_value and low < high:low = low + 1array[high] = array[low]array[low] = mid_valuequick_sort(array, first, low - 1)quick_sort(array, high + 1, last)return array
- 迭代思想要多理解
- 使用迭代的时候不可以使用数组切片的方式，即 array[0 : low] 这种方法，因为数组切片是生成了一个新的对象，并不是对一开始的数组进行操作。