快排

快排思路：

给定一个无需的列表，对列表里的数据进行排序，一般选取最左边或者最右边的元素的作为标杆，选取左边的为升序，右边为降序。

最左边的的数据，list[i] = 5j = 9.

列表的长度 len(list) = 10 .

最右边的下标    j = 9.

步骤：

①从右边遍历数组，把array[ j ]比5小的放在5的左边, j--；

交换位置后i = 0,j = 7：

②从左边遍历数组，把array[ i ]比5大的放在5的右边, i++；

交换位置后i = 5,j = 7：

③回到①②步骤循环执行：

循环执行后，比5小的都放在了5的左边，比5大的都放在了5的右边；

④此时5左边和右边部分还是乱序的，这就需要做递归操作，把0 2 3 1 4和 7 8 6 9 部分继续执行述排序步骤。

递归执行后：

python实现快排的代码：

def quick_sort(li, start, end):
    # 分治 一分为二
    # start=end ,证明要处理的数据只有一个
    # start>end ,证明右边没有数据
    if start >= end:
        return
    # 定义两个游标，分别指向0和末尾位置
    left = start
    right = end
    # 把0位置的数据，认为是中间值
    mid = li[left]
    while left < right:
        # 让右边游标往左移动，目的是找到小于mid的值，放到left游标位置
        while left < right and li[right] >= mid:
            right -= 1
        li[left] = li[right]
        # 让左边游标往右移动，目的是找到大于mid的值，放到right游标位置
        while left < right and li[left] < mid:
            left += 1
        li[right] = li[left]
    # while结束后，把mid放到中间位置，left=right
    li[left] = mid
    # 递归处理左边的数据
    quick_sort(li, start, left-1)
    # 递归处理右边的数据
    quick_sort(li, left+1, end)
 
if __name__ == '__main__':
    l = [6,5,4,3,2,1]
    # l = 3 [2,1,5,6,5,4]
    # [2, 1, 5, 6, 5, 4]
    quick_sort(l,0,len(l)-1)
    print(l)
    # 稳定性：不稳定
    # 最优时间复杂度：O(nlogn)
    # 最坏时间复杂度：O(n^2)

def quick(list):
    if len(list) < 2:
        return list

    tmp = list[0]  # 临时变量 可以取随机值

    left = [x for x in list[1:] if x <= tmp]  # 左列表
    right = [x for x in list[1:] if x > tmp]  # 右列表

    return quick(left) + [tmp] + quick(right)

def quick_sort(arr):

    # 模拟栈操作实现非递归的快速排序
    if len(arr) < 2:
        return arr
    stack = []
    stack.append(len(arr)-1)
    stack.append(0)
    while stack:
        l = stack.pop()
        r = stack.pop()
        index = partition(arr, l, r)
        if l < index - 1:
            stack.append(index - 1)
            stack.append(l)
        if r > index + 1:
            stack.append(r)
            stack.append(index + 1)


def partition(arr, start, end):
    # 分区操作，返回基准线下标
    pivot = arr[start]
    while start < end:
        while start < end and arr[end] >= pivot:
            end -= 1
        arr[start] = arr[end]
        while start < end and arr[start] <= pivot:
            start += 1
        arr[end] = arr[start]
    # 此时start = end
    arr[start] = pivot
    return start