排序算法(六)---快速排序（交换排序）

直接排序属于交换排序

基本思想：
1：选1个基准元素（通常是第一个元素或最后一个元素），将待排数列分成两部分，一部分比基准元素小，一部分比基准元素大
2：再对这两部分数列重复步骤1

时间复杂度：
最好情况：O(n*logn)
最坏情况，退化为冒泡排序 O(n*n)

稳定性：不稳定

python代码实现：quick_sort.py

def swap(l, i, j):
    tmp = l[i]
    l[i] = l[j]
    l[j] = tmp

def partition(l, low, high):
    pivo = l[low]               #基准元素选取
    while(low != high):         #从数列两端交替扫描
        while(low < high and l[high] >= pivo): #从high位置向前搜索，将比基准元素小的交换到低端
            high -= 1
        swap(l, low, high)
        while(low < high and l[low] <= pivo):#从low位置向后搜索，将比基准元素大的交换到高端
            low += 1
        swap(l, low, high)
    return low

def quick_sort(l, low, high):
    if low < high:
        pivokey = partition(l, low, high)
        quick_sort(l, low, pivokey-1)  #递归对低端数列排序
        quick_sort(l, pivokey+1, high) #递归对高端数列排序

if __name__ == '__main__':
    l = [57,12,63,29,37,18,34,46,92,87]
    quick_sort(l, 0, 9)
    print('result:' + str(l))