快速排序

快速排序是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。

• 时间复杂度 O(N*logN) 最坏情况 O(n*n)

基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
说实话，这个代码是最简单的了，看了感觉很优雅，但是效率嘛

def quicksort(array):
    if len(array) < 2:
        return array
    pivot = array[0]    # 基准值
    less = [i for i in array[1:] if i < pivot]
    great = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(great)

快速排序的种类很多，包括随机快排，平衡快排等，这些优化还是很不错的。
上面的写法其实只有那种思想而已，真实不会那样写：

def quickSort(nums, left, right):
    if left > len(nums):
        return
    low, high = left, right
    key = nums[0]    
    while left < right:
        while left < right and nums[right] > key:
            right -= 1
        nums[left] = nums[right]
        while left < right and nums[left] <= key:
            left += 1
        nums[right] = nums[left]
    nums[right] = key
    quickSort(nums, low, left -1)
    quickSort(nums, left + 1, high)    

相关联的一道题：
如何找到一个数组的中位数？
利用快排思想使得左边的值都比 key 小，右边的值都比 key 大，然后保证 key 的下标为 size // 2 即可

def partion(arr, start, end):
    left, right = start, end
    key = arr[start]
    while left < right:
        while left < right and arr[right] >= key:
            right -= 1
        arr[left] = arr[right]
        while left < right and arr[left] <= key:
            left += 1
        arr[right] = arr[left]

    arr[left] = key
    return left

def getmidnumber(nums):
    start, end = 0, len(nums) - 1
    mid = (end) // 2
    div = partion(nums, start, end)
    while div != mid:
        if div < mid:
            div = partion(nums, start, div - 1)
        else:
            div = partion(nums, div + 1, end)
    return nums[mid]

另一种思路：取数组的前半部分元素建最小堆，然后遍历数组的后半部分，遇到小于堆顶的跳过，大于堆顶的更新堆。最后堆中存放的是数组中一半较大元素。

# ☕
def getmidnums(nums):
    if not nums:
        return
    import heapq
    tmp = nums[:len(nums)//2+1]
    print(tmp)
    heapq.heapify(tmp)
    for i in nums[len(nums)//2+1:]:
        if i > tmp[0]:
            heapq.heappushpop(tmp, i)
    print(tmp)
    return tmp[0]

a = [2,1,4,5,3,6,7]
print(getmidnums(a))