快速排序

快排

描述:

　　基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

我的理解:

　    1. 在列表内, 设置一个基准值, 找到该基准值的正确位置, 该位置的左侧部分,都比该位置的元素小, 右侧部分都比该位置的元素大

　　2. 第1步结束后, 列表被分为两部分, 左侧与右侧

　　3. 将这两部分都执行快速排序, 此时左部分被分为两半, 右部分被分为两半

　　4. 循环执行1-3步

　　5. 起始传递进来的列表, 按照二叉树的规则一直分, 直到被分之后的列表只有一个元素, 即该列表的起始下标等于终止下标

　　6. 第5步结束后, 起始列表已经被排好序, 将该列表返回

时间复杂度

　　最优时间复杂度：O(nlogn)

　　 情况描述:

　　　　  每次设定的基准值, 经排序后, 该基准值恰巧为列表的中间值

　　 时间复杂度: 得分两种情况: 1: 分叉 2: 排序

　　　　  分叉: 列表以完全二叉树的情况, 进行分叉, 每次一分为二, 被分了n次

　　　　　　即: 步骤为 log2^n

　　　　  排序: 每次排序都要对列表内所有的元素进行判断

　　　　　　即: 步骤为 n

　　　　由此得出时间复杂度为: O(T) = O(n * log2^n) = O(nlogn)

　　最坏时间复杂度：O(n2)

　　  1. 情况描述:

　　　　每次设定的基准值, 经排序后, 在列表的最左侧, 或 最右侧

　　  2. 时间复杂度得分两种情况: 分叉和排序

　　　　  分叉: 因为基准值一直在左侧, 或者右侧, 所以列表被分了n次

　　　　　　即: 步骤为 n

　　　　  排序: 每次排序都要对列表内所有的元素进行判断

　　　　　　步骤为 n

　　　　由此得出时间复杂度为: O(T) = O(n * n) = O(n^2)

稳定性:不稳定

　　 快速排序是从头和尾开始对元素进行比较,有可能把关键值相同的两个元素调换了位置,所有说是不稳定的,

　　例如:

　　　　   对  2 4 1 3 1  进行排序,第一趟就把后面的1换到前面去,形成了不稳定排序

代码:

简洁版:

def quick_sort(Li, first, last):
    if first >= last:
        return
    mid_value = Li[first]
    low = first
    high = last
    while low < high:
        while low < high and Li[high] >= mid_value:
            high -= 1
        Li[low] = Li[high]
        while low < high and Li[low] < mid_value:
            low += 1
        Li[high] = Li[low]
    Li[low] = mid_value
    quick_sort(Li, first, low)
    quick_sort(Li, low+1, last)

注释版:

def quick_sort(Li, first, last):
    if first >= last:
        # first和last分别为传递进来列表的起始下标与终止下标
        # 如果, 起始下标小于终止下标, 则进行快排
        # 反之, 将引用返回
        return
    # 下面为快排代码
    mid_value = Li[first]
    # 先设置一个基准值, 一般都以列表的起始元素为基准值, 找到这个基准值的正确位置
    low = first
    high = last
    # 设置两个游标, low从列表左侧开始, high从列表右侧开始
    while low < high:
        # 如果low跟high不相遇, 则一直循环, 直到相遇, 即: 找到了基准值的正确位置
        while low < high and Li[high] >= mid_value:
            # 如果high指向的值, 比基准值大, 则向左移
            high -= 1
        Li[low] = Li[high]
        # 结束上面循环后, 代表high游标指向的值, 比基准值小, 将这个high元素与左侧的值进行交换
        while low < high and Li[low] < mid_value:
            # 如果high指向的值, 比基准值小, 则向右移
            low += 1
        Li[high] = Li[low]
        # 结束上面循环后, 代表low指向的值, 比基准值大, 将这个low元素与右侧的值进行交换
    Li[low] = mid_value
    # 上面大循环结束后代表找到了该列表基准值的正确位置, 也代表low游标与high游标相撞, 即: low=high
    # 将基准值 插入到正确的位置, low=high 所以: Li[low] = mid_value 或 Li[high] = mid_value  都可以
    # 将该列表的基准值, 插入到正确位置后, 此时, 列表分为两部分, 左侧部分都比它小, 右侧部分都比它大
    quick_sort(Li, first, low)
    # 将该列表的左侧部分, 进行快速排序
    quick_sort(Li, low+1, last)
    # 将该列表的右侧部分, 进行快速排序
    # 循此往复, 直到该列表所有元素都找到正确位置

    # ==================================

    # 快速排序,
    # 1. 在列表内, 设置一个基准值, 找到该基准值的正确位置, 该位置的左侧部分,都比该位置的元素小, 右侧部分都比该位置的元素大
    # 2. 第1步结束后, 列表被分为两部分, 左侧与右侧
    # 3. 将这两部分都执行快速排序, 此时左部分被分为两半, 右部分被分为两半
    # 4. 起始传递进来的列表, 按照二叉树的规则一直分, 直到被分之后的列表只有一个元素, 即该列表的起始下标等于终止下标
    # 5. 第4步结束后, 起始列表已经被排好序, 将该列表返回



if __name__ == "__main__":
    l = list(i for i in range(0, 10000))
    print("洗牌之前的列表:" + str(l))
    random.shuffle(l)
    print("洗牌之后的列表:" + str(l))
    quick_sort(l, 0, len(l)-1)
    print(l)