目录
快速排序
快速排序 —— 快
快速排序思路：
取一个元素（第一个元素），使元素p归位；
列表被p分成两部分，左边都比p小，右边都比p大
递归完成排序
快速排序的效率：
时间复杂度：O(nlogn)
最坏时间复杂度：O(n2)
import random
from cal_time import *
import copy # 做深拷贝
import sys # 设置递归最大深度
sys.setrecursionlimit(100000)
# 实现将小的数放左边，大的放右边你
def partition(li, left, right):
temp = li[left]
while left < right:
while left < right and li[right] >= temp: # 从右边找比temp小的数
right -= 1 # 往左走一步
li[left] = li[right] # 把右边值写到左边空位上
while left < right and li[left] <= temp:
left += 1
li[right] = li[left] # 把左边值写到右边空位上
li[left] = temp # 把temp归位
return left
# 排序
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)
@cal_time
def quick_sort(li):
_quick_sort(li, 0, len(li) - 1)
li = list(range(10000))
li1 = copy.deepcopy(li)
quick_sort(li)
print(li)堆排序
前置知识一：树与二叉树
树
树是一种数据结构
树是一种可以递归定义的数据结构
树是由n个结点组成的集合
如果n=0，那这是一棵空树
如果n>0，那存在一个结点作为树的根结点，其他结点可以分为m个集合，每个集合本身又是一棵树
一些概念：
根结点、叶子结点
树的深度/高度
树的度
孩子结点、父结点
子树
二叉树
二叉树就是度不超过2的树
每个结点最多有两个孩子结点
两个孩子结点被区分为左孩子结点和右孩子结点
完全二叉树
满二叉树：一个二叉树，如果一个层的节点数都达到最大值，则这个二叉树就是满二叉树
完全二叉树：叶子节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
二叉树的存储方式（表示方式）
链式存储方式
顺序存储方式（堆排序用这个）——用列表来存
父结点和左孩子结点的编号下标的关系
0-1 1-3 2-5 3-7 4-9
i -> 2i+1
父结点和右孩子结点的编号下标的关系
0-2 1-4 2-6 3-8 4-10
i -> 2i+2
前置知识二：堆
堆：一种特殊的完全二叉树结构
大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大
小根堆：一颗完全二叉树，满足任一节点都比其孩子节点小
操作：
堆的向下调整：当根节点的左右子树都是堆时，可以通过一次向下调整来将其变换成一个堆
堆排序过程：
1、建立堆
从最后一个节点的父节点开始进行堆的建立
2、得到堆顶元素，为最大元素
3、去掉堆顶，将堆的最后一个元素放到堆顶，此时可以通过一次向下调整使堆重新有序
4、堆顶元素为第二大元素
5、重复步骤3，直到堆变空
堆排序实现
时间复杂度：O(nlogn)
# 堆的向下调整：当根节点的左右子树都是堆时，可以通过一次向下调整来将其变换成一个堆
# 时间复杂度O(logn)
def sift(li, low, high):
"""
li:列表
low:堆的根节点位置
high:堆的最后一个元素位置
"""
i = low # i&j用来记录当前检查的位置（层数），开始时指向根节点
j = 2 * i + 1 # j开始是左孩子
tmp = li[low] # 把堆顶存起来
while j <= high: # 只要j位置有数
if j + 1 <= high and li[j+1] > li[j]: # 如果有右孩子并且比较大
j = j + 1 # j指向右孩子
if li[j] > tmp:
li[i] = li[j]
i = j # 往下走一层
j = 2 * i + 1
else: # tmp更大，把tmp放到i的位置上
#li[i] = tmp # 把tmp放到某一集领导的位置上
break
li[i] = tmp # 把tmp放到叶子节点上（越界了）
def heap_sort(li):
n = len(li)
for i in range((n-2)//2, -1, -1): # 建立堆，从最后一个带有子节点的小树开始，不管是左孩子还是右孩子，找父节点都是（下标-1）//2
# 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
li = [i for i in range(10)]
import random
random.shuffle(li)
print(li)
heap_sort(li)
print(li)堆的内置函数
python内置模块——heapq
常用函数：
heapify(x)
heappush(heap, item) 加元素
heappop(heap)
import heapq #q->queue 优先队列
import random
li = list(range(100))
random.shuffle(li)
# print(li)
heapq.heapify(li) # 建一个小根堆
n = len(li)
for i in range(n):
print(heapq.heappop(li), end=" ") # 弹出最小的元素归并排序
归并排序：递归
时间复杂度：O(nlogn)
空间复杂度：T(n)：需要另外一个列表
步骤：
分解：将列表越分越小，直至分成一个元素
终止条件：一个元素是有序的
合并：将两个有序列表归并，列表越来越大
# 归并
def merge(li, low, mid, high):
'''
2 5 7 8 9 | 1 3 4 6
^ ^ ^
low mid high
'''
i = low
j = mid + 1
ltmp = []
while i <= mid and j <= high: # 只要左右两边都有数，比较谁大
if li[i] < li[j]:
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
# while执行完毕，肯定有一部分没有数
while i <= mid: # 如果前一部分有数
ltmp.append(li[i])
i += 1
while j <= high: # 如果后一部分有数
ltmp.append(li[j])
j += 1
li[low:high+1] = ltmp
# 排序
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)
li = [i for i in range(1000)]
random.shuffle(li)
merge_sort(li, 0, len(li)-1)
print(li)六种排序算法比较
三种排序算法时间复杂度都是O(nlogn)
一般情况下，就运行时间而言：
快速排序 < 归并排序 < 堆排序
三种排序方法的缺点：
快速排序：极端情况下排序效率低
归并排序：需要额外的内存开销
堆排序：在快的排序算法中相对较慢
稳定的排序：排完序后，相同元素的相对位置不变
| 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | 代码复杂度 | ||
|---|---|---|---|---|---|---|
| 最坏 | 平均 | 最好 | ||||
冒泡排序 |
O(n2) | O(n2) | O(n) | O(1) | 稳定 | 简单 |
| 直接排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 | 简单 |
| 直接插入 | O(n2) | O(n2) | O(n2) | O(1) | 稳定 | i简单 |
| 快速排序 | O(n2) | O(nlogn) | O(nlogn) | 平均O(logn) 最坏O(n) |
不稳定 | 较复杂 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | 复杂 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | 较复杂 |
sorted()和sort()函数
sort()是列表对象的方法，会直接修改原列表，而sorted()是一个内置函数，会返回一个新的已排序的列表，原列表不会被修改。
sort()方法没有返回值，它会直接对原列表进行排序操作，而sorted()函数会返回一个新的已排序的列表，原列表保持不变。
下面分别介绍它们的使用方法：
sort()
# 对列表进行原地排序
list1 = [3, 1, 4, 1, 5, 9, 2, 6]
list1.sort()
print(list1) # 输出：[1, 1, 2, 3, 4, 5, 6, 9]
sorted()
# 对列表进行排序，并返回一个新的已排序的列表
list2 = [3, 1, 4, 1, 5, 9, 2, 6]
new_list = sorted(list2)
print(new_list) # 输出：[1, 1, 2, 3, 4, 5, 6, 9]
print(list2) # 输出：[3, 1, 4, 1, 5, 9, 2, 6]，原列表不变
sort()和sorted()的高级用法
# 对列表进行降序排序
list3 = [3, 1, 4, 1, 5, 9, 2, 6]
list3.sort(reverse=True)
print(list3) # 输出：[9, 6, 5, 4, 3, 2, 1, 1]
# 使用sorted()函数对列表进行自定义排序
list4 = [3, -1, 4, -1, 5, -9, 2, -6]
new_list = sorted(list4, key=lambda x: abs(x))
print(new_list) # 输出：[1, -1, 1, -1, 2, 2, 3, 4]
代码自己手动敲一遍理解更深哦！
