快速排序

• [ ] 快速排序：快
• [ ] 快排思路：
  - 取一个元素p(第一个元素)，使元素p归位
  - 列表被p分成两部分，左边都比p小，右边都比p大；
  - 递归完成排序。

例如：
选择5作为基准数。从右向左扫描，寻找比基准数小的数字为1，交换5和1的位置，[1,3,4,6,2,9,8,5,7]，接着从左向右扫描，寻找比基准数大的数字为6，交换5和6的位置，[1,3,4,5,2,9,8,6,7]。重复上述过程，直到基准数左边的数字都比其小，右边的数字都比其大。然后分别对基准数左边和右边的序列递归进行上述方法。

排序前：[5,3,4,6,2,9,8,1,7]

p归位：[3,4,2,1,5,6,9,8,7]

目标：[1,2,3,4,5,6,7,8,9]

关键点

1. 归位
2. 递归

代码实现：

import sys
import random
from timewrap import exe_time

sys.setrecursionlimit(10000) # 设置递归深度

def partition(data,left,right):
    tmp = data[left]
    while left < right:
        while left < right and data[right] >= tmp:
            right -= 1
        data[left] = data[right]
        while left < right and data[left] <= tmp:
            left += 1 # 你比我小，那么你就往我前面放，我往后走一个
        data[right] = data[left]
    print('data[left]===',data[left])
    print('data[right]===',data[right])
    data[left] = tmp  # 最后的时候，它左边是比他小的，右边是比它大的。
    return left

# 归位完成
# 归位完成后，左边和左边比，右边和右边比。
# 所以才会有下面quick_sort(data,left,mid-1)意指从0开始到定位完-1的位置比，也就是左边比
#             quick_sor(data,mid+1,right)则就是大的排序
# 递归排序
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)


@exe_time
def quick_sort(li):
    return _quick_sort(li,0,len(li)-1)

@exe_time
def sys_sort(li):
    li.sort()

li = list(range(10000))

random.shuffle(li)

quick_sort(li)   # quick_sort running time：-0.06963086128234863 secs.

# sys_sort(li)  # sys_sort running time：-0.003387928009033203 secs.