快速排序是对冒泡排序的一种改进。
快速排序由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))
