b站视频
文章目录
- #11排序介绍
- #12冒泡排序介绍
- #13冒泡排序
- #14选择排序
- #15插入排序
- #16快速排序原理介绍
- #17快速排序代码实现
- #18快速排序代码实现2
- #19堆排序前传树的基础知识
- #20堆排序前传二叉树的基础知识
博客cPen_web
#11排序介绍
# 什么是列表排序
# 常⻅排序算法介绍
# 排序算法分析
# 排序：将一组“无序”的记录序列调整为“有序”的记录序列。
# 列表排序：将无序列表变为有序列表
# 输入：列表
# 输出：有序列表 升序与降序
# 升序与降序 # 注：2个基本排序方式
# 内置排序函数：sort()
#-----------------------------------------------------------
### 常见排序算法
# ·排序Low B三人组 ·排序NB三人组 ·其他排序
# 冒泡排序 快速排序 希尔排序
# 选择排序 堆排序 计数排序
# 插入排序 归并排序 基数排序
#12冒泡排序介绍
### 冒泡排序 (Bubble Sort)
# 列表每两个相邻的数，如果前面比后面大，则交换这两个数。
# 一趟排序完成后，则无序区减少一个数，有序区增加一个数。
# 代码关键点：趟、无序区范围 (重点)
# 注：目的是为了排除来一个升序的列表
#列表 注：右边是下标
# 1 8 <-- 9 和 1比 ；9 >1 交换 9 1 9 8
# 9 7 <-- 8 和 9比 ；8 < 9 不交换 1 7 <-- 比较到倒数第二个
# 2 6 <-- 8 和 2比 ；8 > 9 交换 8 2 8 6
# 8 5 <-- 7 和 8比 ；7 < 8 不交换 2 5
# 3 4 <-- 7 和 3比 ；7 > 3 交换 7 3 7 4
# 6 3 <-- 7 和 6比 ；7 > 6 交换 7 6 3 3
# 4 2 <-- 7 和 4比 ；7 > 4 交换 7 4 6 2
# 5 1 <-- 7 和 5比 ；7 > 5 交换 4 5 4 1
# 7 0 5 0 <--
#这是冒泡排序的1趟 从小到上走一遍 最后箭头只会到倒数第2个元素 (因为不会往后比了)
#冒泡排序 就像烧开水 气开了一样
#这一趟下来 这1个最大的数上去了 这个位置肯定就是最后1个
#上面的叫有序区(已经排好了的)，下面的叫无序区
#第二趟只要对整个无序区进行排序，因为9已经排好了的
#第0趟有序区没有数
#第1趟有序区 9
#第2趟有序区 9 8
#第3趟有序区 9 8 7
#第4趟有序区 9 8 7 6
#第5趟有序区 9 8 7 6 5
#第6趟有序区 9 8 7 6 5 4 # 注：每一趟出来1个数 但是叫第6趟 因为从第0趟开始数的
#第7趟有序区 9 8 7 6 5 4 3
#第8趟有序区 9 8 7 6 5 4 3 2
#这1趟不用做了 9 8 7 6 5 4 3 2 1 #注：只剩下1个数的时候 不用做了
#注：整个排序算法排了 n - 1 趟
#注：循环1趟会出来1个最大的数
### 代码关键点：趟、无序区范围 (重点)
# 第0趟有序区没有数
# 第1趟有序区有1个数
#注：列表切片顾头不顾尾 n-2
# 第2趟 ；n长度 i第i趟 ；n - i；无序区还剩n - i个数
# 第2趟 n-i =9-2=7 还剩7个数 最上面那个数下标为6
# 但箭头不会指到 下标为6 那 因为后面没有数了 所有指到下标为5的数 ;n-i-1
#13冒泡排序
import random # 注：导入随机模块
def bubble_sort(li): # 注：传入列表
for i in range(len(li)-1): # 注：整个算法排了n - 1 趟；i表示 第 i 趟 且从0开始
#上面定义走n-1趟
# 注：每一趟里都有1个指针，箭头永远从0开始，到 n - i -1
for j in range(len(li)-i-1): # 注：实际是确定的箭头 指针顾头不顾尾
# 注：每一趟里都有1个指针，箭头永远从0开始，到 n - i -1
# 注：想想第0趟 排n-1个数 下标n-i-2 (0,n-i-1) 这代表n-i-1个
if li[j] > li[j+1]: # 注：箭头要和下一个元素 比较大小 如果这个数大于后边的数
# 注：li[j]箭头那个数 li[j+1] 箭头后面那个数
li[j], li[j+1] = li[j+1], li[j] # 注：大于就交换
# 注：Python内部实现 实际是 元组的交换
print(li)
# li = [random.randint(0,10000) for i in range(1000)] # 注：列表生成式 生成长度是1000的列表
# print(li) # 打印列表
# bubble_sort(li) # 注：调用算法
# print(li) # 打印排序后的列表
#结果为
#[6507, 6107, 1706, 4345, 3183,…………
#[8, 10, 13, 51, 53, 53, 57, ………… # 注：升序的
li = [3,2,4,6,5,9,8,7,1]
print(li)
bubble_sort(li)
#结果为
# [3, 2, 4, 6, 5, 9, 8, 7, 1] # 注：原来的列表
# [2, 3, 4, 5, 6, 8, 7, 1, 9] # 9
# [2, 3, 4, 5, 6, 7, 1, 8, 9] # 8
# [2, 3, 4, 5, 6, 1, 7, 8, 9] # 7
# [2, 3, 4, 5, 1, 6, 7, 8, 9] # 6
# [2, 3, 4, 1, 5, 6, 7, 8, 9] # 5
# [2, 3, 1, 4, 5, 6, 7, 8, 9] # 4
# [2, 1, 3, 4, 5, 6, 7, 8, 9] # 3
# [1, 2, 3, 4, 5, 6, 7, 8, 9] # 2 1自动最小了
### 注：如果想降序排序 小于的 上去就行了 改 if li[j] < li[j+1]:
# 时间复杂度：O(n**2)
# 注：n 是列表长度 算法里没有发生循环折半的过程 2层关于n的循环 所以复杂度O(n**2)
#####################################################################################
def bubble_sort2(li):
for i in range(len(li)-1):
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
# 时间复杂度：O(n2)
#####################################################################################
li = [9,8,7,1,2,3,4,5,6]
print(li)
bubble_sort(li)
#结果为
# [9, 8, 7, 1, 2, 3, 4, 5, 6]
# [8, 7, 1, 2, 3, 4, 5, 6, 9]
# [7, 1, 2, 3, 4, 5, 6, 8, 9]
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
# [1, 2, 3, 4, 5, 6, 7, 8, 9] # 注：这1趟没有任何交换
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
####################################################################
#改善：如果在1趟过程中 没有发生交换 ，我们就认为 已经排好序了
#怎样改进？ 加1个标志位 在i循环 那里 放1个标志位
# 如果冒泡排序中的一趟排序没有发生交换，则说明列表已经 有序，可以直接结束算法。
def bubble_sort_1(li):
for i in range(len(li)-1):
exchange = False # 在第i趟那加标志位
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
exchange = True # 注：如果有交换 把它识成True 交换这里也是1个标志位
if not exchange: # 注：如果每1趟结束后 exchange没有发生交换 (这个在for里面)
return # 注：就直接结束掉这个函数
#极端例子：如果传入的无序列表 是排好了的，它就只要走一趟 而原本的冒泡排序是 n - 1 趟
#14选择排序
#先从列表中遍历1遍 可以找到最小的数 拿出来
#再把剩下的元素 再遍历1遍 可以找到第2小的数 再拿出来
#再剩下的……第3小……第4小……
### 拿出来放在哪？
#可以放在1个新列表里 (这是最简单版的)
def select_sort_simple(li):
li_new = [] # 这里还需要1个新列表
for i in range(len(li)): # 注：遍历1遍出来1个数 需要遍历 n 遍
# for j in li: # j 就是元素/值 如果它是最小的就拿出来
min_val = min(li) # 注：调用内置函数
li_new.append(min_val) # 把最小值放到新列表里
li.remove(min_val) # 该值删掉
#值重复的也没关系 ，因为它会从左边找
return li_new # 返回新列表
li = [3,2,4,1,5,6,8,7,9]
print(select_sort_simple(li))
#结果为 [1, 2, 3, 4, 5, 6, 7, 8, 9]
#这个算法 是 正确的 但是不推荐写 有几点致命缺点
#1、生成2个列表，数据量大，多占内存
# 冒泡排序 叫他原地排序 不需要开辟1个新的列表 在原来的列表上
#2、复杂度 不是O(n)
# min()函数 O(n)
# remove()删除函数 也是O(n) 因为列表删除1，不能只删了，删了的话会造成空位，后面都要往前挪1步，过程是O(n)
#相当于里面有2个O(n) 但是2个O(n)记为1个O(n)
# 所以时间复杂度是O(n**2) 而不是O(n**3)
###############################################################################
# 不想开辟新列表 但想把选的数放到1个地方
# 把它放到列表的第1个位置 (它只要和第一个数交换 就可以了) 接下来找无序区最小的数 再跟无序区的第1个位置交换
# 为什么不放到最后1个位置：放到最后1个位置 代码不一样
def select_sort(li):
#还是需要n趟，每1趟出来1个最小的数
# 但n-1趟放完后 还是1个数，那个数值最大的，所有和冒泡排序1样，需要n - 1趟
for i in range(len(li) - 1): # i 是第几趟
# 遍历无序区的范围
# 第0趟从0到最后，第1趟从1到最后，第i趟从i到最后
min_loc = i # 记最小值的位置(下标)，因为后面要做交换，记无序区的第1个数为最小值
# for j in range(i,len(li)): # i->列表长度 因为前包后不包所有写列表长度
for j in range(i+1,len(li)): # 所以可以从 i + 1开始遍历
# 没必要自己和自己比
# j 是我们要从哪看到的
if li[j] < li[min_loc]: # 注：如果遍历的数 比那个数还要小
min_loc = j # 注：就min_loc继承j ；j就是最小值的下标
#for循环执行完了 min_loc就是无序区最小的那个数的下标了
li[i], li[min_loc] = li[min_loc], li[i] #最小的数和无序区的第1个值交换
# 1趟就完成了 运行 n-1趟，选出n-1个数，最后1个数 一定是最大的
print(li)
li = [3,4,2,1,5,6,8,7,9]
print(li)
select_sort(li)
print(li)
#结果为 [1, 2, 3, 4, 5, 6, 7, 8, 9]
#结果为 先排除小的
# [3, 4, 2, 1, 5, 6, 8, 7, 9]
# [1, 4, 2, 3, 5, 6, 8, 7, 9]
# [1, 2, 4, 3, 5, 6, 8, 7, 9]
# [1, 2, 3, 4, 5, 6, 8, 7, 9]
# [1, 2, 3, 4, 5, 6, 8, 7, 9]
# [1, 2, 3, 4, 5, 6, 8, 7, 9]
# [1, 2, 3, 4, 5, 6, 8, 7, 9]
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
###########################################################
def select_sort(li):
for i in range(len(li) - 1):
min_loc = i
for j in range(i+1, len(li)):
if li[j] < li[min_loc]:
min_loc = j
if min_loc != i:
li[i], li[min_loc] = li[min_loc], li[i]
# 时间复杂度：O(n**2)
#注：代码规模是n ，没有出现折半，而且代码里没有出现任何 函数 (min\remove复杂度大于O(1)的函数)
#注：所以2层循环是O(n**2)
#它暂时没有像冒泡一样的优化；也没有二分查找优化(因为二分查找前提是有序的)，暂时没有优化
###########################################################
### 选择排序 (Select Sort)
# 一趟排序记录最小的数，放到第一个位置
# 再一趟排序记录记录列表无序区最小的数，放到第二个位置
# ……
# 算法关键点：有序区和无序区、无序区最小数的位置
# 注：更注意的是无序区的位置 记录无序区里最小数的位置(默认指定无序区里第1个数，通过比较 更新)
#15插入排序
#原理类似于 玩牌的时候 摸1张牌 把7 插到 10 的左边
### 插入排序
# 初始时手里(有序区)只有一张牌
# 每次(从无序区)摸一张牌，插入到手里已 有牌的正确位置
### 过程
# 5 7 4 6 3 1 2 9 8
#手里的牌是5
# 摸到1张7 7插到5的右边
# 4 把4查到5的左边，把 5 7 的位置往右边挪 前面就空出1个位置 只需要拿1个变量把它存起来
# 457 6 3 1 2 9 8 ，6的话 插到5 7 中间 所有 7 往右 挪一挪
# 4567 3 1 2 9 8 ， 3的话 4567 全都挪 右边 3 插过来
# 34567 1 2 9 8 ， 1的话 34567 全都往右挪
# 134567 2 9 8 ， 2的话 34567后面5个数 挪一下 ，3插过来
# 1234567 9 8， 9 不变放在这
# 12345679 8， 8 把9挪一下，8 插过来
# 123456789
#弄清楚 哪些牌是手里的牌 ，哪些牌是摸到的牌
#摸多少次牌，就是我们要排序多少趟
#我们要摸 n - 1 次牌 (一共长度为n ，手里有1张牌 ，摸 n-1次)
#摸到4后 从右往左看 57 先7 后5 ，左边有比4小的数停掉循环，或者走到最左边的元素了 停掉循环
#从右边循环看
# 时间复杂度：O(n2)
def insert_sort(li):
for i in range(1, len(li)): # 最开始手里已经有1张牌
# i 表示摸到的牌的下标
tmp = li[i] # 注：把摸到的牌存起来 因为它要往后挪
#这个临时变量最后才用到，就是保存li[i]的 更形象
j = i - 1 # 注：j 指的是手里的牌的下标 (起初是最右边的牌)
# 如果j 这个牌 比 摸到的牌 小 就把摸到的牌插到j的右边
# 如果j已经到最左边了 j=0的时候 比手里摸到的牌i
# 如果j大 i小(摸到的牌) 则j往右挪一个
while j >= 0 and tmp < li[j]: # 循环里是 数往右移，j往前看下一个 ；tmp是li[i]
# j >= 0 表示 j到了-1退出
# 找到1个比只要j比摸到的牌i小的情况 退出
li[j + 1] = li[j] # 把数往右移了 (以前都理解错了，其实右边仅仅只是个值，左边被赋值)
#而且右边 一开始等于 j=i-1 j+1=i 的下标遍历不到的 不影响
j = j - 1 # j 这个箭头往左移 1 个位置 ，右边仅仅是值 左边才是
li[j + 1] = tmp # while循环结束了 li[i]摸的牌写到 j+1的位置；代表插入i的 值 在j+1
print(li)
# while循环干的事情：找插入的那个位置
li = [3,2,4,1,5,7,9,6,8]
print(li)
insert_sort(li)
# print(li)
#结果为 [1, 2, 3, 4, 5, 6, 7, 8, 9]
#结果为
# [3, 2, 4, 1, 5, 7, 9, 6, 8] # 注：原来的列表
# [2, 3, 4, 1, 5, 7, 9, 6, 8] # 注：一开始有序区只有3，摸到2，把2插到3的左边 ，有序区23
# [2, 3, 4, 1, 5, 7, 9, 6, 8] # 注：有序区23 摸到4 把4插到3右边 有序区234
# [1, 2, 3, 4, 5, 7, 9, 6, 8] # 注：234 1 插到2的左边 1234
# [1, 2, 3, 4, 5, 7, 9, 6, 8] # 注：1234 5 右边 12345
# [1, 2, 3, 4, 5, 7, 9, 6, 8] # 注：12345 7 右边 123457
# [1, 2, 3, 4, 5, 7, 9, 6, 8] # 注：123457 9 右边 1234579
# [1, 2, 3, 4, 5, 6, 7, 9, 8] # 注：1234579 6 5后边 12345679
# [1, 2, 3, 4, 5, 6, 7, 8, 9] # 注：12345679 8 把8插到7的右边 123456789
#注：排了8次
#while循环里 把数往右移 j往前看下一个
#每次都是写到j+1的位置
### while j >= 0 and tmp < li[j]的理解：退出循环的条件 1、2 (# 也可以单纯字面理解)
#情况1 注：j<i时 不用挪了 把i放到 j+1的位置
#情况2 注：4567 i=3 7、6、5比3大 往右移
# 4 还比3 大 往右移 j=-1了 ，即j<0时 ，while退出
# 这时 把这个元素 还是写在 j+1的位置(即0的位置)
######################################################################
import random
from cal_time import * # 检测1个代码的运行时间，要把打印的都注释起来或去掉
@cal_time # 注：装饰器
def insert_sort(li):
for i in range(1, len(li)):
tmp = li[i]
j = i - 1
while j >= 0 and tmp < li[j]:
li[j + 1] = li[j]
j = j - 1
li[j + 1] = tmp
li = list(range(10000)) # 注：用range方法生成1个1万的列表
random.shuffle(li) # 注：random模块的shuffle方法 打乱
insert_sort(li)
#结果为 insert_sort running time: 4.095908880233765 secs.
# 时间复杂度：O(n**2)
#不是O(n) 而是O(n**2) ，n是代表列表长度，没有折半；2层循环，这个循环跟j相关的，j是跟n相关的
#所以j是跟n 相关的
#因为插入1个的过程的，我是要移动一些元素，并不知道移动多少元素。摸来第1张牌最多移动1个元素，摸来第2张牌最多移动2个元素，摸来第n张牌最多移动n-1个元素
#每一趟最多移动n/2个元素，n趟 (n**2)/2
######################################################################
#注：冒泡排序，选择排序，插入排序 时间复杂度都是O(n**2),而且它们3个都是原地排序
#注：O(n**2)的排序算法具体效率怎么样？
# 1台电脑1s中的运行效率在10的7次方，1000万次基本操作
# n=10000,n方式10000*10000是1亿，所以需要十秒左右
#冒泡排序的效率比较慢，平时比较效率是不太能接受的
#16快速排序原理介绍
### 快速排序
# 快速排序：快
# 快速排序思路：
# 取一个元素p（第一个元素），使元素p归位；
# 列表被p分成两部分，左边都比p小，右边都比p大；
# 递归完成排序。
# 排序前：5 7 4 6 3 1 2 9 8 P为5
# p归位： 2 1 4 3 5 6 7 9 8 左边比5小右边比5大 #这个过程怎么实现的 后面会说
# 第3步递归完成 (5归位后 列表分为左右2部分 分别再调用)
# 2 1 4 3 5 6 7 9 8
#第1个元素2 2归位 1 (2) 4 3 小列表又被分成2部分
#左边的列表1 只有1个元素的时候 或者0个元素的时候 就达到了递归的终止条件
# 因为1个元素的时候是有序的
#右边的列表43 4归位 3 4 两个部分3(4) 左边部分1个元素3，右边0个元素(以4为分割)
#进而整个大列表的左边 都递归完成了
# 整个大列表的右边 6 7 9 8
#6归位后(6)798 左边零个元素(不用递归了) 右边7 9 8 三个元素
#7 9 8 7归位后(7)98 左边零个元素 右边9 8 两个元素 左边不用递归 递归右边
#98两个元素 9归位后 列表分为2部分8(9) 左1个元素8(递归完成) 右边0个元素(递归完成)
# 89递归完成 所以 789 递归完成 所以6789递归完成，所以右边递归完成，所以整个大列表递归完成
# 相当于把它分成类似二分整 每一个进行递归
# 只需要实现归位算法，排序只需要递归就行了
#-------------------------------------------------------------------------------------------def quick_sort(data, left, right): # data表示列表 left、right 列表左右 表示范围
if left < right: # 说明列表取余至少有2个元素，有2个或者2个以上的元素 递归(递归的终止条件)
# left < right 列表至少2个元素
# left == right 列表区域有1个元素
mid = partition(data, left, right) # 先用函数 算出递归后的下标位置
quick_sort(data, left, mid - 1) # 列表分成两部分，递归第1部分 (left,mid-1)
quick_sort(data, mid + 1, right) # 递归第2 部分 (mid+1,right)
# 归位函数时partition函数 data 参数1 是我们的列表，left和right是列表的一部分
# 比如 整个大列表 left是0的位置 right是n-1的位置
# 这个归位函数返回1个mid的值 (归位后 归位的数的下标)
# 返回了mid值后 列表可以被拆分成2部分 (left --> mid-1) (mid+1 --> right) 2部分
# 再对这2步进行递归
# 只要把partition函数写出来
#-------------------------------------------------------------------------------------------
# 5 7 4 6 3 1 2 9 8
# 注：5归位，先拿1个变量把5存起来 left=5下标 right=8下标
# 注：列表左边有1个空位 是给5小的数准备的，这个数从右边开始找
# 8 比5大 不对， 9 不对，2 放过来
# 2原来的位置 空位，从左边找比5大的数放过去
# 这个空置不能是5自己过去，因为左边要比5小 不满足
# 2原来的位置空位，从左边找比5大的数扔过去。7比5大，扔过去
# 2 4 6 3 1 7 9 8 7--》扔到右边
# 扔的过程是从left位置 到 right位置
# 左边有空位，从右边找比5小的数，1 放过来；从right位置放到left位置
# 右边有空位，1比5小 没问题，4比5小 没问题；6比5大，6去右边空位
# 左边有空位，6比5大 没问题，3比5小 去左边
# 接下来还应该从左边找比5大的数 放到右边去，但是 3 比5 大。到这里发现 left和right重合了
# left和right重合了说明 这个位置在中间，我们把5放过来 就可以
#17快速排序代码实现
# 快速排序-partition函数
def partition(li, left, right): #参数1列表 2、3操作的列表范围
# 存出来第一个位置
tmp = li[left] # 注：目的 把p存起来。注意不要写0，切的过程应该是left的位置，而不是0的位置
while left < right: # 注：left=right的时候结束，终止条件
# 这是右边的
while left < right and li[right] >= tmp: # 从右边找比tmp小的数。
# 如果右边都比5大 就碰上了 ，希望退出这个循环
# left < right 检测，保证 右边一直大的情况，最后结果不是right-1这种
right -= 1 # 只要这个数比tmp大，left向左移动1个
# 注：往左走1步
li[left] = li[right] #注：如果left=right极端情况，那就自己等于自己 不影响
#如果找到了 把right写到空位上 ，把right这个数写到left位上
#把右边的值写到左边空位上
# print(li) # 注：从右边找到比5小的
# 这是左边的
while left < right and li[left] <= tmp: # 如果找到了，从左边找比5大的数
# 只要左边小于等于 tmp，一直循环；一旦找到比它大的数 终止循环
# left=right 没有找到时，检测一下 left < right 不执行left+=1
# 只要left和right碰上就退出
left += 1
li[right] = li[left] # 把左边的值写到右边空位上
#如果找到了，把left的值 写到 右边的空位上 right
#它们两个碰上了 也没关系 ，自己等于自己
# print(li) # 注：从左边找到比5大的
# 两个小循环一直执行，不管在哪只要left和ritht等了，某个循环不执行了
# 那么等了之后，触发外面的大条件，跳出循环。把原来的值写到空位上
li[left] = tmp # 把tmp归位
return left # 返回mid的值 left和right都行，因为碰上了
# 返回值 为的是 嵌套小循环
li = [5,7,4,6,3,1,2,9,8]
print(li)
partition(li,0,len(li)-1)
print(li)
#结果为
# [5, 7, 4, 6, 3, 1, 2, 9, 8]
# [2, 7, 4, 6, 3, 1, 2, 9, 8]
# [2, 7, 4, 6, 3, 1, 7, 9, 8]
# [2, 1, 4, 6, 3, 1, 7, 9, 8]
# [2, 1, 4, 6, 3, 6, 7, 9, 8]
# [2, 1, 4, 3, 3, 6, 7, 9, 8]
# [2, 1, 4, 3, 3, 6, 7, 9, 8]
# [2, 1, 4, 3, 5, 6, 7, 9, 8] # 注：5归位
####################################################################
#逻辑复杂 代码对称
# 开始 tmp = li[left]
# 最后 li[left] = tmp 写出去写回来
# 中间1个大while
# 2个小while，每个while都是 1个赋值
# 开始是右边，然后是左边的。先右后左，碰头或者找到一个数，就切换循环
####################################################################
# 快速排序-partition函数
def partition(li, left, right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp: # 从右边找比tmp小的数
right -= 1 # 往右走一步
li[left] = li[right] # 把右边的值写到左边空位上
while left < right and li[left] <= tmp:
left += 1
li[right] = li[left] # 把左边的值写到右边空位上
li[left] = tmp # 把tmp归位
return left # mid 是 这个函数返回left值的目的
# 快速排序-框架
def quick_sort(li, left, right):
if left < right: # 至少2个元素
mid = partition(li, left, right) # 这个函数返回left值的目的
quick_sort(li, left, mid - 1) # 左边部分
quick_sort(li, mid + 1, right) # 右边部分
li = [5,7,4,6,3,1,2,9,8]
quick_sort(li, 0, len(li)-1)
print(li)
# [1,2,3,4,5,6,7,8,9]
#新理解
li[right] = li[left] # 注：右边仅仅是值，而左边的值的变化和下标、值 2者都有关
#18快速排序代码实现2
### 快速排序
# 快速排序的效率：
# 快速排序的时间复杂度 O(nlogn)
# 快速排序的问题：
# 最坏情况
# 递归
##################################################################
#注：假设一开始有16个数，n=16，一次partition 把它分成2部分
16 partition的过程 (每1层都做了一次partition) partition 是16 O(n)
8 8 partition的过程 (每1层都做了一次partition) partition 是8+8 16
4 4 4 4 partition的过程 (每1层都做了一次partition) 是16 O(n)
2 2 2 2 …………………… 是16 O(n)
# 1次partition的 复杂度:
# left 一边 right一般；left从右往左边撒，right从右往左边撒，最后碰上了
# 相当于 从两边 往中间 把整个列表扫描了一边，所以1个长度为n的列表，它的实际复杂度是O(n)
#每一层都是O(n)
#一共logn层 log16层
# 所以这个时间复杂度是 O(nlogn)
#装饰器不能放在递归函数上，装饰器也会递归，会打印很多次
# 解决方法：套一层马甲
import random
from cal_time import *
import copy # copy模块做li深拷贝，为了一块执行
import sys # 注：修改递归最大深度
sys.setrecursionlimit(10000) # 注：修改递归最大深度
@cal_time
def bubble_sort(li):
for i in range(len(li)-1):
exchange = False
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
exchange = True
if not exchange:
return
def partition(li, left, right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp:
right -= 1
li[left] = li[right]
while left < right and li[left] <= tmp:
left += 1
li[right] = li[left]
li[left] = tmp
return left
def _quick_sort(li, left, right): # 注：改个名
if left < right:
mid = partition(li, left, right)
_quick_sort(li, left, mid - 1)
_quick_sort(li, mid + 1, right)
@cal_time
def quick_sort(li): # 指接收1个li参数
_quick_sort(li, 0, len(li)-1) # 调用这个函数
li = list(range(10000))
random.shuffle(li) # 乱序
li1 = copy.deepcopy(li) # copy模块做li深拷贝，为了一块执行 复制成2个一样的列表
li2 = copy.deepcopy(li) # copy模块做li深拷贝，为了一块执行 复制成2个一样的列表
quick_sort(li1) # 快速排序 传入li1
bubble_sort(li2) # 冒泡排序 传入li2
print(li1)
print(li2)
#结果为
# quick_sort running time: 0.02394270896911621 secs.
# bubble_sort running time: 8.118826389312744 secs.
#举例 n = 1024 时，冒泡排序 n**2 大概在100万 1024*1024
# 快速排序 nlogn 1024*log1024 = 1024*10 = 1万
#数越大差的越多 比如 n = 2的32次方 大概42亿，冒泡排序42亿*42亿 亿亿级别
# 快排 42亿*log42亿 = 42亿*32 也就几百亿 差很多倍
# 所以 快排的效率 比冒泡高很多
#####################################################################
# ### 快速排序
# # 快速排序的效率：
# # 快速排序的时间复杂度 O(nlogn)
# # 快速排序的问题：
# # 最坏情况
# # 递归
#
# ##################################################################
# 快排的问题存在：
# 1、递归的写法：Python有一个递归最大深度999 可以改
# 递归消耗相当一部分的系统资源 (不好的地方)
# 2、快速排序有一个最大不好的地方存在，当列表是 9 8 7 6 5 4 3 2 1 时
# 这种最坏的情况 冒泡每次至少一个数 ，而不是每次大概劈成一半，就不会出现nlogn了，复杂度是n**2
# 9,8,7,6,5,4,3,2,1
# 1,8,7,6,5,4,3,2,9 右边没有
# 1,8,7,6,5,4,3,2 左边没有
# 2,7,6,5,4,3,8 右边没有
# 2,7,6,5,4,3
# ………………
# 示例
li = list(range(10000,0,-1)) # 倒序的列表
quick_sort(li)
#结果为 RecursionError: maximum recursion depth exceeded in comparison
#达到了递归最大深度，因为每次少1个数，会递归n层，递归了1000层，超过了最大线程
#修改递归最大深度后 sys.setrecursionlimit(100000)
#结果为 5s左右
#如何解决？随机化版本的快速排序
#随机找1个值，而不是找第1个值。把第1个数和随机选的数交换一下，再按照之前的partition函数交换一下
#只需要加一步
#这样倒序的例子，时间复杂度不会特别高，只不过还是会出现最坏情况，只不过最坏情况你不能设计出来了。最坏的情况就不需要考虑，快排没有问题
#算法有正常复杂度和最坏复杂度。最好情况时间复杂度、一般情况时间复杂度、最坏情况时间复杂度
# 一般看的是一般情况 和 最坏情况
#快速排序的最坏情况是 n**2 只不过最坏情况的可能性非常小
#快速排序一般情况是 n*logn
# 最好排序 相当于只走一次
#改进之后，冒泡的最好情况是O(n),但是最好情况只有1个，它的最好情况太少了
#19堆排序前传树的基础知识
# 树是一种数据结构 比如：目录结构
# 树是一种可以递归定义的数据结构
# 树是由n个节点组成的集合： #注：这是递归定义的方式，节点就是元素
# 如果n=0，那这是一棵空树；
# 如果n>0，那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树。
# 一些概念
# 根节点、叶子节点
# 树的深度（高度）
# 树的度
# 孩子节点/父节点 子树
#-------------------------------------------------------
#注：根节点：A
#注：叶子节点：不能分叉的节点 [最后一个，下面没有孩子了](叶子已经到了树的最末端，不能分叉)
#-------------------------------------------------------
#注：树的深度(高度)：看它最深有几层 。1层2层3层4层
#-------------------------------------------------------
#注：节点的度：F节点往下分了3个叉，度是3。分了几个叉，就有几个度 看往下的叉
#注：树的度就是整个树里 最大的那个节点的度
#注：树的度就是 这个树最多分了几叉。A分了6个叉，这个树的度就是6
#-------------------------------------------------------
#注：孩子节点/父节点：E叫做I的父节点，I叫做E的孩子节点
# A叫做B的父节点，B叫做A的孩子节点
# 树在上面的 辈分比较高，生下来孩子
#-------------------------------------------------------
#注：子树：大树里 把一个树枝掰下来，这个树枝代表很多小树杈，那么它是1棵子树
#20堆排序前传二叉树的基础知识
# 二叉树：度不超过2的树 # 注：每个节点往下 最多分2个叉
#
# 每个节点最多有两个孩子节点
# 两个孩子节点被区分为左孩子节 点和右孩子节点
#--------------------------------------------
#注：二叉树 度不超过2的树
#注：B是A的左孩子节点，C是A的右孩子节点
#--------------------------------------------
# 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。
# 完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
#--------------------------------------------
#注：满二叉树：对称，每个叉 该有的都有，最后一层是满的
#注：完全二叉树：简单理解 从满二叉树 最后 拿走几个节点
#注：完全二叉树：从上到下，从左到右，顺序不少 ，最后一层从左往右 少了也没关系
#--------------------------------------------
#注：堆是特殊的完全二叉树
### 二叉树的存储方式（表示方式）
# 链式存储方式
# 顺序存储方式 #注：堆排序中讲顺序存储方式
#注：顺序存储方式 简答来说是 用列表存
#注：按树的顺序 存进去，是一一对应的
#注：写二叉树 最常见的操作：父亲找孩子，孩子找父亲。一层一层往下找，不能跳
#注：列表里父节点和孩子节点，下标的关系
### 父节点和左孩子节点的编号下标有什么关系？
# 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的0次方个节点
#第2层2的1次方个节点
#第3层2的2次方个节点
#注：假设孩子的节点是i ，那么父亲的节点是 (i-1)//2 注：这是整除
#注：比如 4-9 4-10。父节点是4 ,(9-1)//2 = 4 ,(10-1)//2 = 4
#注：可以用顺序存储方式存储二叉树，就是列表。一个一个挨个存
#注：父亲找孩子 i 2i+1 2i+2
#注：孩子找父亲 i (i-1)//2
本文地址：https://blog.csdn.net/cPen_web/article/details/110219644
黄山市民网：https://www.huangshanshimin.com/
