一点点排序
排序
归并排序
归并排序介绍与代码
大体思路：归并排序整体思路是，先把一串待排序数列分为前后两组，把这两组别离排为次序数组，再将两组次序数组合为一整个大的次序数组。
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]))
