采用哨兵投石法理解简单快速排序，这是理解双轴排序的基础，双轴排序表面简单，但根据java工业程序来看，发展历次更迭，已经有些难以理解了，之后我又添加一些逻辑可能会导致逻辑判断过多，失去算法的本真。所以先采用最简单的基准值选取思路，就是开头结尾选基准值。

 

# -*- coding: utf-8 -*-
"""
-------------------------------------------------
   开发人员：Edwin
   开发日期：
   开发工具：PyCharm
   功能描述：
   
-------------------------------------------------
"""
def quick_sort(alist: []) -> []:
    '''
    抓住了简单快速排序的精要，也就是占位，但有空间浪费,快速排序法的初衷是不开辟更多的空间。
    :param alist:
    :return: 排序后的数组
    '''
    n = len(alist)
    if n <= 1:
        return alist
    pivot = alist[0]
    lesser = [item for item in alist[1:] if item <= pivot]
    greater = [item for item in alist[1:] if item > pivot]
    return quick_sort(lesser) + [pivot] + quick_sort(greater)

def quick_sort(alist: [], start, end) -> None:
    '''
    采用哨兵巡逻方式，A在开头往后搜索，B从结尾往前搜索，A代表比基准值小的阵营，B代表比基准值大或者相等的阵营
    那谁来先丢石头呢，我们给B，因为基准值取了第一个元素，这个元素留了一个坑。
    B发现小号的石头，停下脚步，把这个小石头丢给了A阵营，然后等待A阵营丢过来大石头把小石头留下的坑填平。
    A发现大号的石头，停下脚步，把这个大石头丢给了B阵营，然后等待B阵营丢过来小石头把大石头留下的坑填平。
    此时AB都停下了脚步，长官发现AB都没碰面，唤醒AB继续巡逻，直到他们碰面。
    当AB相遇就完成了一次巡逻，AB的位置就是基准值的位置，此时的基准值把序列分成左右两个序列，然后分别对这两个序列进行递归调用。
    :param alist: 待排序数组
    :param start: 起始下标
    :param end: 结束下标
    :return: None
    '''
    if start >= end:
        return
    low, high, pivot = start, end, alist[start]
    while low < high:
        while low < high and alist[high] >= pivot:
            high -= 1
        alist[low] = alist[high]
        while low < high and alist[low] < pivot:
            low += 1
        alist[high] = alist[low]
    alist[low] = pivot
    quick_sort(alist, start, low - 1)
    quick_sort(alist, low + 1, end)

def ds_quick_sort(alist: []) -> None:
    '''
    士兵投石法
    :param alist:
    :return:
    '''
    quick_sort(alist, 0, len(alist) - 1)

def is_sorted(alist):
    prev = alist[0]
    for i in range(1, len(alist)):
        if prev > alist[i]:
            print('Sort ascending failed.')
            return False
        prev = alist[i]
    print('Sort ascending succeed.')
    return True

def test():
    import random
    alist = [random.randint(1, 1000000) for i in range(1000000)]
    # alist = [8, 8]
    # print('Before: ', alist)
    ds_quick_sort(alist)
    print('After: ', alist)
    is_sorted(alist)

if __name__ == '__main__':
    test()