快速排序：通过基准数，把小于它的数放在它的左边，大于它的放在它的右边。
也可以称为 “挖坑转移分治” 排序：
1、坑的理解
对于需要进行排序的列表，我们假设在地上有 n 个连续的坑，每个坑中都放了一个数字，我们需要把数字调整成从小到大的顺序
2、挖坑（找基准数）的理解
从这些坑中，选出一个基准数，就相当于从坑中挖出数字，此时坑里是空的，这里我们通常选第一个坑中的数字
3、高位坑、低位坑、高位数、低位数
低位数：比基准数小的数
高位数：比基准数大的数
如果是从小到大的顺序排列的话，那么我们认为左边的坑是低位坑，应该存放的是低位数，
同理，右边的坑是高位坑，应该存放的是高位数
因此，我们要做的是 把 高位坑中的低位数 挖出来并转移到 低位坑中，
把 低位坑中的高位数，转移到 高位坑中
4、转移的理解
定义： i = 0, j = n - 1
从2中得知，我们已经有一个坑是空的，这个坑是低位坑，应该存放的是低位数,
因此，从右边, j 开始反向遍历（j–）寻找低位数，当寻找到低位数，则把这个低位数填到我们挖出的低位坑中, i++
这样， 低位坑就被填上了，但相应的，右边又出现了高位坑，
因此，从左边，i 开始正向遍历（i++）寻找高位数，填到新的高位坑中， j–
循环上面的过程。
总结：
在 j-- 过程中，干了两件事：
· 找出低位数并转移至低位坑
· 产生高位坑
在 i++ 过程中：
· 找出高位数并转移至高位坑
· 产生低位坑
如此往复填坑的过程中， i++, j–, 最终，i 会等于 j,
在 i++ 的过程中, 已经把所有 高位数，都转移到了高位坑中，
在 j-- 的过程中，已经把所有 低位数，都转移到了低位坑中
把基准数填到最后空坑中（i），此时，左边的数都比它要小，右边的数都比它要大，这个基准数的位置就确定了
5、分治处理
4中已经确定了一个基准，那么接下来得到两个列表：
[0, i-1], [i+1, n-1]
对这两个列表分别进行2~5的操作
6、完成快速排序
# coding=utf8
list_datas = [6,2,9,4,3,7,8,1,23,54,12]
def quick_sort(datas):
def _adjust(start_index, end_index):
if start_index >= end_index:
return
i = start_index
j = end_index
base = datas[i]
while i != j:
while i != j:
if datas[j] <= base:
datas[i] = datas[j]
i += 1
break
j -= 1
while i != j:
if datas[i] > base:
datas[j] = datas[i]
j -= 1
break
i += 1
datas[i] = base
_adjust(i+1, end_index)
_adjust(start_index, i-1)
_adjust(0, len(datas) - 1)
return datas
if __name__ == "__main__":
quick_sort(list_datas)
快速排序非递归实现：
def quick_sort_not_recursion3(datas):
op_stack = [(0, len(datas) - 1)]
while op_stack:
start_index, end_index = op_stack.pop(-1)
i, j, base = start_index, end_index, datas[start_index]
while i != j:
while i != j:
if datas[j] <= base:
datas[i] = datas[j]
i += 1
break
j -= 1
while i != j:
if datas[i] > base:
datas[j] = datas[i]
j -= 1
break
i += 1
datas[i] = base
if start_index < i:
op_stack.append((start_index, i))
if i+1 < end_index:
op_stack.append((i+1, end_index))
return datas