算法012_快速排序

快速排序思路

• 任意取一个元素 p（比如第一个元素），使元素 p 归位
• 列表被 p 分成两部分，左边都比 p 小，右边都比 p 大
• 递归完成排序（两边都进行递归）

快速排序图解
（1）原始列表

原始列表

此时的 left 和 right 指向列表的头部和尾部

left和right初始位置

（2）把5取出来，位置留给从右边开始找，找比5小的数

然后移动right，先找到 2 比 5 小，然后把 2 放到 left

此时右边有空位，从左边找比 5 大的数，找到 7 ，然后放到 right 处

然后右边找到比5小的1，放到 left 处

接着从左边找比5大的数，找到的是 6 放到 right 上

然后从右边找比5小的数，找到的是 3 ，放到 left

然后再从左边找，left 继续向右移动，和right重合，说明位置在中间，然后就把 5 放在这里

只要实现排序算法，然后递归调用即可

def quick_sort(data, left, right):
    if left < right:
        mid = partition(data, left, right)
        quick_sort(data, left, mid - 1)
        quick_sort(data, mid + 1, right)

left = right 说明有一个元素，left < right 说明至少有一个元素。有两个或者两个以上的元素才进行递归，0个或1个元素不需要递归

代码

def partition(target_list, left, right):
    temp = target_list[left]  # 取左侧的元素，但不一定是0号元素
    while left < right:
        # 从右边找数放到左边
        # 从右面找出比 temp 小的数
        while (left < right) and (target_list[right] >= temp):
            right -= 1  # 往左走一步
        # 找到了，把右边的数写到左边空位上去
        target_list[left] = target_list[right]
        while (left < right) and (target_list[left] <= temp):
            left += 1
        # 把左边的值写到右边空位上
        target_list[right] = target_list[left]

    # 循环结束，把最初的值给写入到列表当中。temp 归位
    target_list[left] = temp
    # 返回中间值，将整个列表分为两部分的地方。因为left和right碰上，所以都行
    return left


def quick_sort(target_list, left, right):
    if left < right:  # 至少两个元素
        mid = partition(target_list, left, right)
        quick_sort(target_list, left, mid - 1)  # 递归排序左边的部分
        quick_sort(target_list, mid + 1, right) # 递归排序右边的部分


test_list = [5, 7, 4, 6, 3, 1, 2, 9, 8]
quick_sort(test_list, 0, len(test_list) - 1)
print(test_list)

快速排序分析

• 快速排序的效率
  • 快速排序的时间复杂度：
• 快速排序的问题
  • 最坏情况：在倒序列表的情况下，每次只移动一个数（每次只少1个数，而不是把列表分成两半）
  • 递归：python 有递归最大次数的限制，并且递归会消耗很多系统资源
• 解决思路
  • 解决最坏情况，随机找值，和第一个值交换，解决最坏的数