排序
归并排序
归并排序介绍与代码
大体思路：归并排序总体思路是，先把一串待排序数列分为前后两组，把这两组分别排为顺序数组，再将两组顺序数组合为一整个大的顺序数组。
objection1：分组后分别排好序？用选择排序吗？递归的思路是什么？
- 并非选择排序，而是递归的方式。可以看到，第一次“将一串待排序数列分为两组”后，显然不是有序的，这就轮到递归出场了：通过递归，将已经分好的再分为两组，然后，再分为两组……直到只剩两个为一组
- 两个为一组，再进行最后一次分组，然后遇到递归出口：返回小于等于单个数值的组。于是就返回了这两个单个值的数组。
- 再通过比较大小将这两个值，按顺序放到数组里，返回。这样就返回了2个数的顺序数组。思考一下其他分支在干什么……也返回了两个数的顺序数组，于是开始一层层返回，2到4，4到8，最终得到全部排好值的顺序数组。
objection2：具体怎么操作？
- 假设此时已经有了两个排好的数列left和right，为二者设置index分别为i和j。
①比较left【i和right【2
②循环以下两步
③若left【i的数值较小，则将left【i写入temp-list列表中，i自增1。若i超出索引范围，跳出循环。
④若right【j的数值较小，则将right【j写入temp-list列表中，j自增1。若j超出索引范围，跳出循环。
⑤将未超出索引范围的数列全部写入temp-list中（因为是排好顺序的，所以可以直接全部放入）。
def merge_sort(arr)
#出口
if len(arr)<=1:
return arr
#mid = len(arr)除以2后向下取整：若len（arr）=3，则mid = 【1.5】 = 1
mid = len(arr) // 2
#以下是将未排序数列分为两组，使用切片。
#因为切片是前闭后开原则，所以使用[:mid]和[mid:]不会导致漏项
#所以如果要做到不重不漏，一定要两句的结尾和开头的index相同
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left,right)
def merge(left,right):
temp = [] #提前做的列表，用于接收排序好的数
i = j = 0 #两个数值表的索引index
#两个数列left和right中，总会有一个先耗完
#与此同时两者的index（i、j）也会随之增加
#跳出循环后，将余下的数列放入temp-list即可
while i<len(left) and j < len(right):
#单个进行比较，较小的放到temp-list中。
if left[i] < right[j]
temp.append(left[i])
#注意，i和j自增的条件要确定好
#只有放入temp-list的数的index（i、j）才可以自增
i += 1
else:
temp.append(right[j])
j += 1
#将余下的数组全部放入temp-list中
#无需设定条件，耗完的数列什么都不会向temp-list中写入
temp.extend(left[i:])
temp.extend(right[j:])
return temp
arr = [1,23,4,54,3,2,7,65,9]
print("排序后为：",merge_sort(arr))
归并排序-练习-小和问题
题目:
在一个数组中每一个数左边比当前数小的数累加起来,叫做这个数的小和,给定数组[1,3,8,2,6,3,9,1],求这个数组的小和
例:[1,3,6,2,5]
1的小和=0:左边没有比他小的数
3的小和=1:左边比他小的数1
6的小和=4:左边比他小的数1,3
2的小和=1:左边比他小的数1
5的小和=18:左边比他小的数1,3,6,2,5
[!IMPORTANT]
我在思考中钻了牛角尖，在递归中想要采用返回排序好的数组作为小和计算载体，可是这样也导致了需要两个返回值的问题，给我的编码带来了很大阻碍。而用排序后的结果对原数组更新，并只返回小和的做法更简单。
这里与原归并算法不同的是，排序操作通过寻找数据的index进行排序，排序后对原始数组arr进行覆盖更新。
举个例子就是说，10个数的数组甲（Y、D、A、B、C、H、R、T、L、P），对第3-5个数（A、B、C）进行了排序，结果为（C、A、B），则需要对原数组甲进行覆盖更新为（Y、D、C、A、B、H、R、T、L、P）
[!NOTE]
疑问：有时会出现
msum += arr[l] * (right - r + 1) if arr[l]<arr[r] else 0 ^^^^^^^^^^^^ IndexError: list index out of range的情况，但是对余下数据填入部分修改后（加=，或者方法二改成方法一），错误消失。不知为何。
# 数据清洗函数，防止错误数据被执行，可以通过调用merge函数再调用process函数
# def merge(arr):
# if arr is None or len(arr)<2:
# return 0
# return process(arr,0,len(arr)-1)
def process(arr,left,right):
if left == right: #此时说明到了单个数据为一组的步骤
return 0 #没有小和，故返回0
#接下来要将整个数组传入，每进行一次排序都会对这整个数组的部分进行修改
#所以这条语句是计算数组的index来确定目的数据位置。
mid = left + ((right-left) // 2)
#一口气全部计算相加并返回
#在每一次排序中都会产生小和，所以每一次调用process都要计算上其产生的小和
return process(arr,left,mid)+process(arr,mid+1,right)+sml_sum(arr,left,mid,right)
def sml_sum(arr,left,mid,right):
msum = 0
l = left
r = mid+1
temp = []
while l<=mid and r<=right:
#右组某数A比左组某数B大，所以一定有小和的值B
#A的右边的数一定比A要大，且A的右边有C个数（包括A）
#那么B这个数产生的小和总值=B*C
#如果A比B小或者等于B，那么小和值=0
msum += arr[l] * (right - r + 1) if arr[l]<arr[r] else 0
#正常的归并步骤
if arr[l]<arr[r]:
temp.append(arr[l])
l+=1
else:
temp.append(arr[r])
r+=1
#方法一：将余下的数据放入temp中
#与原始归并中的代码不同的是，这里的arr是全部的数，所以填入余下部分需要设定界限
temp.extend(arr[l:mid+1])
temp.extend(arr[r:right+1])
#方法二：将余下的数据放入temp中
# while l<=mid:
# temp.append(arr[l])
# l+=1
# while r<=right:
# temp.append(arr[r])
# r+=1
arr[left:right+1] = temp #一定要记得更新排序后整个数组的内容
return msum #然后返回小和
arr = [1,3,8,2,6,3,9,1]
#不进行数据清理，直接开始递归
print(process(arr,0,len(arr)-1))
#数据清理后，再递归
print(merge(arr))
快速排序
快速排序介绍与代码
大体思路：①在数组中，随机挑选一个n，小于n的放在左边，大于n的放在右边，等于n的放在中间，再将n放在大于区最左边的位置，由此便分出了三个区域，小于区、大于区和等于区。②在小于区和大于区分别挑选一个n，重复第①步的内容，直到所有数据都排好。
注意1：在quicksort函数中，partition函数返回的是（大于区、小于区）和等于区的边缘
注意2：如果partition返回的是l_dom 和 r_dom-1的话，在下一次递归调用quicksort的时候edge[x]就不用加一或者减一了呢？答案是不能，根据我的经验来说，会导致索引溢出
注意3：扩张小于区时，不能单纯将小于区扩张，仍需要将小于区最后一个与下标为cur的互换。因为当arr[cur] == arr[std_idx]时，cur会加一，由此略过arr[cur]，小于区再次扩张时，若不互换则会将与标准数相等的数引入小于区。
import random
def quicksort(arr,left,std_idx):
if left < std_idx:
#return two-edge of equal-domination
#注意1
edge = []
edge = partition(arr,left,std_idx)
#注意2
quicksort(arr,left,edge[0]-1)
quicksort(arr,edge[1]+1,std_idx)
return arr
def partition(arr,cur,std_idx):
# add random element,imporve the worst situation speed
piovt = random.randint(cur,std_idx)
arr[std_idx],arr[piovt] = arr[piovt],arr[std_idx]
l_dom = cur - 1 #l_dom是左边界的界限,当arr[cur]<arr[std_idx]时，l++，小于区右扩
r_dom = std_idx #r_dom是右边界的界限，当arr[cur]>arr[std_idx]时，r--，大于区左扩
#cur是当前数的current_index，传入时，是数组的左边界
#与cur的左边数字交换数值时，右移一位，其他情况不动
#std_idx是标准数n的下标（位于数组最右端），永远不动，作为标准
while cur < r_dom :
#小于区扩张
if arr[cur]<arr[std_idx]:
l_dom += 1
arr[cur],arr[l_dom] = arr[l_dom],arr[cur]
cur += 1
#大于区扩张
elif arr[cur] > arr[std_idx]:
r_dom -= 1
arr[cur],arr[r_dom] = arr[r_dom],arr[cur]
#等于区增加
else: cur += 1
#将标准数放到大于区与等于区临近的位置
arr[r_dom],arr[std_idx] = arr[std_idx],arr[r_dom]
return l_dom + 1,r_dom #返回左边界+1作为接下来的右边界、和右边界作为接下来的左边界
#但是如果返回[l_dom,r_dom-1]的话，返回后调用quicksort函数，会在第30行提示arr[cur] out of range
# return l_dom,r_dom - 1
arr = [1,3,8,2,9,6,6,4,9,0,76254,73846,13498,4546,123423,6767,34352,32235468,46745,4,5,3,67,23,12,78,12,45,67,23,98,45,23,5,643,3,256]
print(quicksort(arr,0,len(arr)-1))
快速排序练习-第K个最大数
题目：
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
例：若数组为：num = [3,5,21,8,4,7,3,18], k = 2, 则第k个最大数为18
代码链接：https://zhuanlan.zhihu.com/p/91142297
思路：
- 此题非常简单，唯二难点一是对partition部分性质把握；二是如何确定基准值左边的数正好是k-1个
- partition性质："比基准值大的在左边，比基准值小的在右边"
- 也就是说，当基准值左边的数有k-1个时，num[index]就是要找到的数，根本不用把数排号
- partition返回index时，index > k-1说明大于区中数的个数比k-1个多，说明大于区中有小于咱们要找的数的数，所以边界high要以index为基准 -1
- index < k-1，大于区中的数不够k-1个，说明大于区之外有数比要找的数大，所以边界high要以index为基准 +1
- index == k-1，此时正好有k-1个数比num[index]大，说明num[index]就是我们要找的数
代码中变量与数组的对照与流程：
| b_dom(大于区) | high+1 | |||||||
|---|---|---|---|---|---|---|---|---|
| 3 | 10 | 345 | 2323 | 25 | 7 | 3 | 67 | |
| cur(标准值) && i (索引) |
| | b_dom(大于区) | | | | | | | high+1 |
| :---------: | :-----------: | :------: | :--: | :--: | :--: | :--: | :--: | ------ | :: |
| 3 | 345 | 10 | 2323 | 25 | 7 | 3 | 67 | | |
| cur(标准值) | | i (索引) | | | | | | | |
| b_dom(大于区) | high+1 | |||||||
|---|---|---|---|---|---|---|---|---|
| 3 | 345 | 2323 | 10 | 25 | 7 | 3 | 67 | |
| cur(标准值) | i (索引) |
| b_dom(大于区) | high+1 | |||||||
|---|---|---|---|---|---|---|---|---|
| 3 | 345 | 2323 | 25 | 10 | 7 | 3 | 67 | |
| cur(标准值) | i (索引) |
| b_dom(大于区) | high+1 | |||||||
|---|---|---|---|---|---|---|---|---|
| 3 | 345 | 2323 | 25 | 10 | 7 | 3 | 67 | |
| cur(标准值) | i (索引) |
| b_dom(大于区) | high+1 | |||||||
|---|---|---|---|---|---|---|---|---|
| 3 | 345 | 2323 | 25 | 10 | 7 | 3 | 67 | |
| cur(标准值) | i (索引) |
| b_dom(大于区) | high+1 | |||||||
|---|---|---|---|---|---|---|---|---|
| 3 | 345 | 2323 | 25 | 10 | 7 | 67 | 3 | |
| cur(标准值) | i (索引) |
| b_dom(大于区) | high+1 | |||||||
|---|---|---|---|---|---|---|---|---|
| 67 | 345 | 2323 | 25 | 10 | 7 | 3 | 3 | |
| cur(标准值) | i (索引) |
def partition(num,cur,high):
b_dom = cur
pivot = num[cur]
for i in range(cur+1,high+1):
if num[i] > pivot:
b_dom += 1
num[b_dom],num[i] = num[i],num[b_dom]
num[cur],num[b_dom] = num[b_dom],num[cur]
return b_dom
def main():
num = [3,1,345,2323,25,7,3,67]
k = 4
high = len(num)-1
cur = 0
while True:
#把所有大于标准数的都放到左边来，然后返回大于区的右边界值
#也就是说，右边界值+1就是大于区有几个数
index = partition(num,cur,high)
#看看大于区中的数够不够k个
#为什么当 index == k-1 时，num[index] 就是我们要找的数呢？此处涉及到快速排序的特点
#当 partition 函数返回时，基准值所在的位置 index 意味着在它左边有 index 个元素是大于它的。
#当 index == k-1 时，这意味着在基准值左边恰好有 k-1 个元素比它大，所以基准值是第 k 个最大的元素
if index == k - 1:
return num[index]
#比k个多，说明大于区中有小于咱们要找的数的数
elif index > k - 1:
#所以再执行partition的时候，去掉那个小的数
high = index - 1
else:
#其他情况下，就是不够k个数
#有一个或多个大于或等于目标数的数再大于区外
#再次执行partition的时候，多给一个大于区名额
cur = index + 1
if __name__ == "__main__":
print(main())
堆排序
堆排序基本介绍与代码
大体思路：就是使用堆的基本操作“堆化”成大顶堆或小顶堆，再将最顶点的父节点和最右边的子节点交换值，在执行“堆化”操作。
- 堆化？：堆化就是将堆整理成父节点大于子节点的形式的操作
- 操作流程：
- 拿到一个父节点，记录父节点的索引为max
- 找到他的两个（或一个）孩子
- 比较大小
- 若左孩子比父节点大，则交换值，更新父节点索引max为左孩子节点的索引值
- 再次比较交换后的父节点与其两个孩子的值的大小并交换，一直到两个孩子都比父节点大
- 若没有发生交换，则跳出循环
- 操作流程：
def sift_down(num,dad,n):
while True:
#本循环中参与堆化的是：以索引i为父节点和他的两个孩子
#n是数组长度，防止溢出
left = dad * 2 + 1 #左孩left
right = dad * 2 + 2 #右孩right
max = dad #默认三者中最大节点是父节点dad
# 在不超出索引范围之内，使max = 更大的子节点索引
if left < n and num[left]>num[dad]:
max = left
# num[left],num[dad] = num[dad],num[left]
if right < n and num[right]>num[n]:
max = right
# num[right],num[dad] = num[dad],num[right]
#若下方if成立，则说明初始父节点就是最大节点，无需继续堆化
if max == dad:
break
#父子节点交换
num[max],num[dad] = num[dad],num[max]
dad = max #为什么向下：因为运行一次本函数只对一个节点的大小、相对位置进行交换等操作
#所以在本循环中，循环一次就会让选中的节点交换一次位置
#若在一次循环里没有交换位置，就会跳出循环，结束函数调用
'''
关于堆的性质：
假设完全二叉树的节点数量为n，
则叶节点数量为(n+1)/2 ，
其中 // 为向下整除。
因此需要堆化的父节点数量为(n-1)//2
'''
def heap_sort(num):
#按照数组索引来查找对应堆的位置
#第一个要堆化的父节点是len(num) // 2,是最后一个父节点
#因为堆化是从下向上的，所以倒序堆化
#一次循环只对一个父节点进行位置确定（确保父比子大）
#运行完下方for循环后，该堆变为一个大顶堆
for i in range(len(num) // 2 - 1,-1,-1):
sift_down(num,i,len(num)-1)
#堆化完成，现在开始一步一步将顶点节点与最右叶子节点做交换
for i in range(len(num)-1,0,-1):
#交换最顶节点与最右叶子节点
num[i],num[0] = num[0],num[i]
#不符合堆的要求，进行堆化
sift_down(num,0,i)
def main():
num = [3,5,8,4,2,7,6]
heap_sort(num)
print(num)
if __name__ == "__main__":
main()
堆排序练习-出现频率前K高的元素
描述：给定一个数组num，和一个整数k，返回出现频率前k高的元素
若给出num=[1,1,1,2,2,3,4,5], k=2
输出为：[1, 2]
问题分析：
桶排序
大体思路：按照数据，分出几个范围，每一个范围称之为一个桶。在遍历数组时，按照不同范围放到不同的桶里。再对每一个桶内进行排序。最后进行整合。桶排序也是分治法的应用之一
分析：
- 平均时间复杂度为O(N+K),K is the number of bucket
- 最坏情况时间复杂度：O(N2) 所有元素都放到同一个桶里的情况
- 空间复杂度：O(N+K),K is the number of bucket
'''
桶排序，也是分治法的应用
将数字按照范围放到不同的桶里
在桶中进行排序
再将所有桶合并
'''
def bucket_sort(num):
#这里先进行一次遍历，增加了时间复杂度，但是这样比较简单
max_num = max(num)
#设置一半数组长度的桶数量
#无疑会增加空间复杂度
bucket = [[] for _ in range(len(num) // 2)]
for i in num:
bucket[int(i/max_num)].append(i)
#对各桶内数据进行排序
for buc in bucket:
#这里使用python自带的排序函数
buc.sort()
#重新写入num数组
i = 0
for buc in bucket:
for bu in buc:
num[i] = bu
i+=1
return num
print(bucket_sort([2,4,1,5,9]))