详解快速排序

冒泡排序是在每一轮中只把1个元素冒泡到数列的一段，而快速排序则在每一轮挑选一个基准元素，并让其他比他大的元素移动到数列一边，比他小的元素移动到数列的另一边。从而不断地进行着在那个已经被分出来地一边和另一边中进行着上述地操作，直至都为一个元素，然后再把他们组合起来就成了个有序地数列。这就是分治法地思想。那么他的时间复杂度是O(nlogn)，原因是，他需要把数组中的全部元素都需要遍历一遍，时间复杂度是O(n)，这样一共需要遍历几遍呢？假设元素个数是n,那么平均情况下需要logn轮(一般在程序上一分为2的操作都是logn)
这里主要地问题是
基准元素地选择,基准元素一般选择第一个即可，但数列的第一个若是最小值或者最大值，这样数列就无法一分为二了，时间复杂度就退化成了O(n).
解决方案是
我们可以随机选取一个元素作为基准元素，并且让基准元素和数列首元素交换位置。这样就有很大概率避免基准元素是数列的最大值或最小值了。

总结

所以快速排序的平均时间复杂度是O(nlogn)，最坏情况下的时间复杂度是O(n*n)
这里采用双边循环法和单边循环法来实现快速排序;当然这里均使用了递归

双边循环法

文字描述(待补)

def quick_sort(start_index, end_index, array=[]):
    # 递归结束条件：startIndex大等于endIndex的时候
    if start_index >= end_index:
        return
    # 得到基准元素位置
    pivot_index = partition_v1(start_index, end_index, array)
    # 根据基准元素，分成两部分递归排序
    quick_sort(start_index, pivot_index - 1, array)
    quick_sort(pivot_index + 1, end_index, array)


def partition_v1(start_index, end_index, array=[]):
    # 取第一个位置的元素作为基准元素（也可以选择随机位置）
    pivot = array[start_index]
    left = start_index
    right = end_index
    while left != right:
        # 控制right指针比较并左移
        while left < right and array[right] > pivot:
            right -= 1
        # 控制left指针比较并右移
        while left < right and array[left] <= pivot:
            left += 1
        # 交换left和right指向的元素
        if left < right:
            p = array[left]
            array[left] = array[right]
            array[right] = p
    # pivot和指针重合点交换
    array[start_index] = array[left]
    array[left] = pivot
    return left

单边循环法

单边循环法实现（待补）

def quick_sort(start_index, end_index, array=[]):
    # 递归结束条件：startIndex大等于endIndex的时候
    if start_index >= end_index:
        return
    # 得到基准元素位置
    pivot_index = partition_v1(start_index, end_index, array)
    # 根据基准元素，分成两部分递归排序
    quick_sort(start_index, pivot_index - 1, array)
    quick_sort(pivot_index + 1, end_index, array)

def partition_v2(start_index, end_index, array=[]):
    # 取第一个位置的元素作为基准元素（也可以选择随机位置）
    pivot = array[start_index]
    mark = start_index
    for i in range(start_index+1, end_index+1):
        if array[i] < pivot:
            mark += 1
            p = array[mark]
            array[mark] = array[i]
            array[i] = p
    array[start_index] = array[mark]
    array[mark] = pivot
    return mark

采用非递归来实现

递归：
代码中一层一层的方法调用，本身就使用了一个方法调用栈。每次进入一个新方法，相当于入栈；每次有方法返回，就相当于出栈。
递归四要素：返回值，函数的分拆，终止条件，参数
非递归文字实现（待补）

def quick_sort(start_index, end_index, array=[]):
        # 用一个集合栈来代替递归的函数栈
        quick_sort_stack = []
        # 整个数列的起止下标，以哈希的形式入栈
        root_param = {"startIndex": start_index, "endIndex": end_index}
        quick_sort_stack.append(root_param)

        # 循环结束条件：栈为空时结束
        while len(quick_sort_stack) > 0:
            # 栈顶元素出栈，得到起止下标
            param = quick_sort_stack.pop()
            # 得到基准元素位置
            pivot_index = partition(param.get("startIndex"), param.get("endIndex"), array)
            # 根据基准元素分成两部分, 把每一部分的起止下标入栈
            if param.get("startIndex") < pivot_index - 1:
                left_param = {"startIndex": param.get("startIndex"), "endIndex": pivot_index - 1}
                quick_sort_stack.append(left_param)
            if pivot_index + 1 < param.get("endIndex"):
                right_param = {"startIndex": pivot_index + 1, "endIndex": param.get("endIndex")}
                quick_sort_stack.append(right_param)


def partition(start_index, end_index, array=[]):
    # 取第一个位置的元素作为基准元素（也可以选择随机位置）
    pivot = array[start_index]
    mark = start_index
    for i in range(start_index+1, end_index+1):
        if array[i] < pivot:
            mark += 1
            p = array[mark]
            array[mark] = array[i]
            array[i] = p
    array[start_index] = array[mark]
    array[mark] = pivot
    return mark


my_array = list([3, 4, 14, 1, 5, 6, 7, 8, 1, -1, 0, 9, 11])
quick_sort(0, len(my_array)-1, my_array)
print(my_array)