八大排序算法的Python实现__4__快速排序

环境

Python 3.5.2

原理

  • 在列表中挑选出一个基准值
  • 将列表中的其它元素与基准值对比,比基准值大的放在基准值右侧,比基准值小的放在基准值左侧
  • 以此类推

源码

def quick_sort(l, start, end):
    if start >= end:
        return

    low = start
    high = end
    mid_value = l[low]

    while low < high:
        # low<high这个条件必须在这里再次体现,避免出现循环过程中low>high的情况
        while low < high and l[high] >= mid_value:
            high -= 1
        # 当中间值右侧的值小于中间值时,将该值赋值于l[low](原来的值已保存至mid_value变量)
        l[low] = l[high]

        # low<high这个条件必须在这里再次体现,避免出现循环过程中low>high的情况
        while low < high and l[low] <= mid_value:
            low += 1
        # 当中间值左侧的值大于中间值时,将该值赋值于l[high](原来的值已保存至l[low])
        l[high] = l[low]

    # 退出循环时,说明low==high,则可以将mid_value的值赋予它
    l[low] = mid_value

    quick_sort(l, start, low-1)
    quick_sort(l, low+1, end)


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    quick_sort(l, 0, len(l)-1)
    print(l)

时间复杂度

  • 最优时间复杂度:O(nlogn)
  • 最坏时间复杂度:O(n2)
  • 稳定性(多个元素等值的情况下是否会破坏原有顺序):不稳定

说点什么

  Subscribe  
提醒