三种常见的快速的排序方法介绍。
快速排序取一个元素p(可以直接指定为第一个元素)，使元素p归位置，左边的数都比p小，右边的数都比p大。通过递归完成排序。（最常用的排序，效率高）
时间复杂度：O(nlogn)
快排问题：
最坏情况：O(n2) 例如(9,8,7,6,5,4,3,2,1) 加入随机化初始p(随机数选取index,和最左边的数交换位置，人为重组一下数组，尽量避免最坏情况)
递归最大深度问题(默认为9999)
import sys sys.setrecursionlimit(1000000) 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) def partition(data, left, right): p = data[left] while left < right: while left < right and data[right] >= p: # 找小于p的值 right -= 1 # 往左走一步 data[left] = data[right] # 把右边的值放到左边位置上 print(data) while left < right and data[left] <= p: # 找大于p的值 left += 1 # 往右走一步 data[right] = data[left] # 把左边的值放到右边位置上 print(data) data[left] = p # 把p归位 print(data) return left堆排序
堆是一种特殊的完全二叉树结构。
大根堆：一个完全二叉树，满足任一节点都比其子节点都大。
小根堆：一个完全二叉树，满足任一节点都比其子节点都小。
堆的向下调整性质：假设根节点的左右子树都是堆，但自身不是堆，可以通过一次向下的调整来将其编程一个堆。
堆排序过程（大根堆）(1) 堆建立。（从最后一个子树开始调整）
(2) 堆顶是最大元素。
(3) 去掉堆顶，将堆最后一个元素放到堆顶，此时通过一侧调整重新使堆有序。
(4) 堆顶元素为第二大元素。
(5) 重复步骤3，直到堆变空。
时间复杂度：O(nlogn), 实际表现略慢于堆排序。
python 内置堆排序模块(小根堆)
def sift(li, low, high): # 堆最后一个元素位置high, low堆顶位置 i = low # 根节点位置 j = 2 * i + 1 # 左节点 temp = li[i] # 堆顶存起来 while j <= high: # 只要j位置有节点就一直循环 if j+1 <= hight and li[j+1] > li[j]: # 如果右节点存在并且比左节点大 j = j + 1 # j指向右节点 if li[j] > temp: li[i] = li[j] i = j # i j 位置替换 j = 2 * i + 1 # j网下继续调整 else: li[i] = temp # 把temp放到父节点的位置 break else: li[i] = temp # 把temp放到叶子节点 def heap_sort(li): n = len(li) for i in range((n-1-1)//2, -1, -1): # 从最后一个节点的父节点的位置网前遍历 # i 表示建堆的时候调整的部分的根的下标 sift(li, i, n-1) # 建堆完成 for i in range(n-1, -1, -1): # i 指当前堆的最后一个元素的位置 li[0], li[i] = li[i], li[0] sift(li, 0, i-1) # i-1是新的high # python内置模块使用 import heapq import random li = list(range(100)) random.shuffle(li) print(li) heapq.heapify(li) # 建小根堆 print(li) n = len(li) new_li = list() for i in range(n): value = heapq.heappop(li) # 弹出最小的元素 new_li.append(value) print(li)归并排序
归并： 假设一个列表两段分别有序，将其合成一个有序列表的操作。
归并排序过程：
(1) 分解： 将列表越分越小，直至分成一个元素。
(2) 终止条件： 一个元素是有序的。
(3) 合并： 将两个有序列表归并，列表越来越大。
关键点：递归
时间复杂度：O(nlogn) 空间复杂度： O(n)
# 归并 def merge(li, low, mid, high): i = low j = mid + 1 temp_list = list() while i <= mid and j <= high: # 只要左右两边都有数就循环 if li[i] < li[j]: temp_list.append(li[i]) i += 1 else: temp_list.append(li[j]) j += 1 # while执行完，肯定有一部分没有数了 while i <= mid: # 如果左边还有数 temp_list.append(li[i]) i += 1 while j <= high: # 如果右边还有数 temp_list.append(li[j]) j += 1 li[low:high+1] = temp_list def merge_sort(li, low, high): if low < high: # 列表至少有两个元素 mid = (low + high) // 2 merge_sort(li, low, mid) # 左边部分排序 merge_sort(li, mid+1, high) # 右边部分排序 merge(li, low, mid, high)总结
- 三种排序时间复杂度都是O(nlogn)
- 一般情况下，就运行时间而言： 快排 < 归并 < 堆
- 缺点：（1）快排：极端情况下 效率低。（2）归并：需要二外的内存开销。 （3）堆排序： 在三种排序中速度相对慢一些。
