写在前面：常见的几种排序的思路以及代码要直接背下来，烂熟于心的程度，形成自己的东西并复刻在脑海里面。其中快速排序、归并排序以及堆排序是高级排序。冒泡、选择、插入都是常用的一些排序，需要知晓原理和相应的代码细节。算是第二次全面的回顾了，所以下一次如果要写，应该是十分的熟悉才对。
- 冒泡排列(Bubble sort)
- 简单选择排序(Selection sort)
- 插入排序(Insertion sort)
- 快速排序(Quick sort) **
- 计数排序
- 归并排序(Merge Sort) **
- 堆排序(Heap Sort) **
常见排序的一个算法效率的分析，总体来说堆排序时流皮的，时间复杂度：O(nlogn),空间复杂度：O(1)
1、冒泡排列(Bubble sort)：
这种应该是最常见，也是最好理解的，是一种相对很暴力的过程：从左到右不断交换相邻逆序的元素，需要深入理解
- 类别：基于交换的排序算法
- 多次遍历待排序的数组
- 每轮遍历，依次比较两个相邻的元素，如果顺序错误，将这两个元素交换，使得较小的元素放在较大的元素前面，这样，一轮遍历之后，最大的元素被交换到了序列尾部
- 外层循环需要遍历的次数，n个元素的排列，需要n-1次遍历
- 内层循环需要n-i-1次遍历，代表i次循环中比较的次数
def bubble_sort(arr):
for i in range(len(arr)):
for j in range(len(arr)-i-1):
if arr[j]>arr[j+1]:
arr[j],arr[j+1]=arr[j+1],arr[j]
return arr
arr=[3, 5, 6, 7, 11, 3, 22, 44, 99]
res=bubble_sort(arr)
print(res)
# [3, 3, 5, 6, 7, 11, 22, 44, 99]
**增加一种计数的功能：**
def bubble_sort2(arr):
#相邻两个元素进行比较，如果发现位置错误则进行交换
n=len(arr)
for i in range(n):
count=0
for j in range(n-i-1):
if arr[j]>arr[j+1]:
arr[j],arr[j+1]=arr[j+1],arr[j]
count+=1
#判断count的值是否等于0，如果等于0说明没有交换
if count == 0:
break
2、简单选择排序(Selection sort)：
附上这张动图进行理解
选择排序的思想：每一趟（第i趟）在后面n-i+1个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素只剩1个，就不用再选了。
- 多次遍历待排序的数组
- 每轮遍历，从待排序序列种选出最小的元素，存放到已排序序列的末尾，即和待排序序列中的开始元素进行交换
- 外层循环寻找最小元素的次数，n个元素的排序，需要进行n-1次选择
- 内层循环需要n-i-1次，代表第i次循环中比较的次数
[7, 5, 3, 6, 44, 22, 99, 11]
[3, 5, 7, 6, 44, 22, 99, 11] #第一次
[3, 5, 7, 6, 44, 22, 99, 11] #第二次
[3, 5, 6, 7, 44, 22, 99, 11] #第三次
[3, 5, 6, 7, 44, 22, 99, 11] #第四次
[3, 5, 6, 7, 11, 22, 99, 44] #第五次
[3, 5, 6, 7, 11, 22, 99, 44] #第六次
[3, 5, 6, 7, 11, 22, 44, 99] #第七次
[7, 5,(99,1), 3, 6, 44, 22, (99,2), 11]
[7, 5, 11,3, 6, 44, 22, (99,2),(99,1)]
#从列表中选择最大的元素放到最后一个位置
def select_sort(arr):
n=len(arr)
for i in range(n-1): # 0 n-1 O(n) 一共进行n-1趟的
#剩余列表中最小值的索引
min_index=i
for j in range(i+1,n): #O(n) #在剩下的i+1~n-1中去寻找最小的元素
if arr[min_index]>arr[j]:
min_index=j #更新最小元素的位置
if min_index!=i:
arr[i],arr[min_index]=arr[min_index],arr[i] #如果需要更新就需要进行相应的交换操作
return arr
#arr=[5, 1, 3, 4, 2]
arr=[7, 5, 3, 6, 44, 22, 99, 11]
print('原数组：')
print(arr)
print('排序后数组：')
select_sort(arr)
print(arr)
3、插入排序(Insertion sort)：
- 多次遍历待排序的数组
- 首先将数组的第一个元素看作是包含1个元素的已排序数组（将待排序的第一个元素当作已排序序列，第二个~最后一共而元素当作 未排序序列）
- 接着，按顺序把待排序数组中的元素插入到已排序数组的正确位置（将未排序的第一个数据与已排序的最后一个数进行比较）
总结原理：通过构建有序序列，对于未排序的数据，在已排序的序列中从后向前扫描，找到相应的位置并插入（语言很精炼），元素集合越接近有序，直接插入排序算法的时间效率越高。
常见的几种插入排序：
直接插入排序：适用于顺序存储和链式存储的线性表
折半插入排序
希尔插入排序
[54, 226, 93, 17, 77, 31, 44, 55, 20] #升序排序
[54, 226, 93, 17, 77, 31, 44, 55, 20]
[54, 93,226, 17, 77, 31, 44, 55, 20]
[54, 93,17,226, 77, 31, 44, 55, 20]
[54,17, 93,226, 77, 31, 44, 55, 20]
[17,54, 93,226, 77, 31, 44, 55, 20]
[17,54, 93,77,226, 31, 44, 55, 20]
[17,54,77, 93,226, 31, 44, 55, 20]
# .....
[17,31, 44,54,55,77,93,226, 15]
#最坏时间复杂度 n*n=O(n^2)
#最优时间复杂度 n*1=O(n)
[17, 20, 31, 44, 54, 55, 77, 93, 226, 1000]
#稳定性 :稳定的
[17, 20, 31, 44, 54, 55, 77, 93, 77, 226]
[17, 20, 31, 44, 54, 55, 77, 77, 93, 226]
def insert_sort(arr):
n=len(arr)
# i表示列表中索引为i的数据进行插入排序（相当于抓牌的过程）
# 每次进行一轮插入之后，已排序序列的长度+1
for i in range(1,n): #n-1 n 对序号为1~n-1的数组进行排序
# 使用j标记待插入数据向前移动时的索引，知道不需要再移动（相当于将新抓的牌放入到已有的牌中）
j=i
while j>0: #和有序列表中每个元素进行比较 （从有序序列的最后一个开始，一直到第一个元素）
if arr[j]<arr[j-1]: #如果当前元素比前一个元素小，则进行交换
arr[j],arr[j-1],=arr[j-1],arr[j]
else:#否则已经是有序列表，不需要交换了，则退出循环，进行下一轮的判断
break
# 每次进行一轮插入之后，未排序序列的长度-1
j-=1
if __name__ == '__main__':
#arr=[54, 226, 93, 17, 77, 31, 44, 55, 20]
arr=[5, 1, 3, 4, 2]
print('原数组：')
print(arr)
print('排序后：')
insert_sort(arr)
print(arr)
4、快速排序(Quick sort)
类别：基于交换的排序算法
基本思想：基于分治法的思想，让两个索引不断的向中间靠拢
- 首先设定一个分界值pivot,通过该分界值将数组分成左右两个部分
- 将大于或等于分界值的数据集中到数组右边，小于或等于分界值的数组集中到数组的左边
- 左右和右边的数据可以分别进行排序，左侧的数据也取分界值分成左右两个部分左边放小，右边放大，右边的同理
- 重复上述的操作
具体的那部分：
将第一个数值作为分界值
附上一个自己写的例子如下：（形成相应的肌肉记忆）
注意事项：循环的时候需要先从右边往左边开始
参考资料：https://yshblog.com/blog/170
def quick_sort(arr,left,right):
#递归退出条件
# left=right ,证明要处理的数据只有一个
# left>right ,证明右边没有数据
if left>=right:
return
# 定义两个游标分别指向0和末尾的位置,选择基准点为该调整范围的第一个值
start = left
end = right
pivot = arr[left]
#循环判断，直到遍历全部，left和right两个变量值一直在变化，直到两个相遇说明遍历完全部的数据点
#递归相当于循环，即无需继续处理返回结果
while left < right:
# 从右向左 arr[right]>pivot 则right-=1（从右开始查找大于基准点的值）
while left < right and arr[right] >= pivot:
right -= 1
# 将right索引对应的元素赋值给left（这个位置的值先移动到左边）
arr[left] = arr[right]
# 从左往右 arr[left]<pivot 则left+=1（从左开始查找小于基准点的值）
while left < right and arr[left] < pivot:
left += 1
# 将left索引对应的元素赋值给right（这个位置的值先移动到右边）
arr[right] = arr[left]
#将基准数放置到对应的位置（写回改成的值）
arr[left]=pivot
#比基准数小的即左边的数据 要重复调用quick_sort()
quick_sort(arr,start,left-1)
#比基准数大的即右边的数据 要重复调用quick_sort()
quick_sort(arr,left+1,end)
if __name__ == '__main__':
arr=[4, 3, 5, 7, 6, 1, 2, 4]
print('原数组：')
print(arr)
print('排序后数组：')
quick_sort(arr,0,len(arr)-1)
print(arr)
有一个注意的地方，将分治的方法用函数来写，这样可以使得代码比较的简洁，这里也将代码贴在这里，作为熟悉用。用的变量的名字没有太大的关系，主要是熟悉里面的相关逻辑才是最重要的。其实这也很好的对二分法做了一个回顾了。 化成一种标准的形式比较好处理也是，为后面熟练写打下基础。
# 首先写一个分治的函数
def partition(arr,left,right):
pivot=arr[left]
i = left
j = right
while i < j:
while i < j and arr[j] >= pivot:
j -= 1
arr[i] = arr[j]
while i < j and arr[i] <pivot:
i += 1
arr[j] = arr[i]
arr[i]=pivot
return i
# 再写排序函数
def quick_sort(arr, left, right):
if left < right:
mid = partition(arr,left,right)
quick_sort(arr, left, mid-1)
quick_sort(arr, mid+1, right)
if __name__ == '__main__':
arr=[4, 3, 5, 7, 6, 1, 2, 4]
print('原数组：')
print(arr)
print('排序后数组：')
quick_sort(arr,0,len(arr)-1)
print(arr)
5、计数排序：
找出原数组中元素的最大值，记为max
创建一个新的数组，记为count，其长度为max +1 ,元素的默认值都是0
遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中元素出现的次数作为count数组的元素值
创建结果数组result,起始索引index
遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素填充到result数组中去，每处理依次，count中的元素值减1，直到该元素值不大于0，依次处理count中剩下的元素
返回结果数组result
6、归并排序(Merge Sort)：
分解（divide）：将n个元素分成含n/2个元素的子序列
解决(conquer)：用合并排序法对两个子序列递归的排序
合并(combine)：合并两个已排序的子序列已得到排序结果
- 按拆分顺序一层一层反向合并，在拆分过程中原来在一个子序列的，合并后还在子序列，合并时需要保证按序合并；最底层的合并：两个值，比较大小，小值在前
- 再往上，需要为合并的两个子序列配置两个指针（姑且称之为left和right），初始分别指向序列的起始位置，较两个指针指向值，取较小值加入合并序列，较小值指针后移，再比较、加入较小值、较小值指针后移……直到合并完成
视频链接：https://www.algomooc.com/1280.html
写代码的过程中有很多的细节是需要注意的，需要不停的反复写才能够发现真正的问题所在。甚至还有一些语法的问题在里面。有几个十分需要注意的点如下：
- 递归的终止条件
- 定义的两个左右排序区间的问题：分治法
- 将归并排序和快速排序要区分开来，两者也是有相似的地方
- 双指针的思想（双指针用到的情况有很多，这里运用的具体步骤要非常清晰才行）
- 一个区间遍历完毕之后，将另一个区间加入的过程
实际代码如下：
[54, 26, 93, 17, 77, 31, 44, 55] #升序排序
#分解 n//2
[54, 26, 93, 17] [77, 31, 44, 55]
[54, 26] [93, 17] [77, 31] [44, 55]
[54] [26] [93] [17] [77] [31] [44] [55]
#合并
[26,54] [17,93] [31,77] [44,55]
[17,26,(54,1),93] [31,44,(54,2),55,77]
[17,26,31,44,54,55,77,93]
def merg_sort(arr):
#1. 分解
n=len(arr)
#递归的出口： 分解到最小
if n<=1:
return arr
#取拆分的中间位置（递归拆分，取整）
mid=n//2
#拆分后左右两侧子串，并且是不断的进行调用，一直到只有一个元素为止
left_li=merg_sort(arr[0:mid]) #左边
right_li=merg_sort(arr[mid:]) #右边
#2.合并
#排序结果列表，比较传过来的两个序列，返回一个排好的序列
result=[]
#定义左右指针
left_pointer,right_pointer=0,0
#利用两个指针归并当前两个左右子序列
while left_pointer<len(left_li) and right_pointer<len(right_li):
#比较最小集合中的元素，将最小元素添加到result列表中
if left_li[left_pointer] <=right_li[right_pointer]:
result.append(left_li[left_pointer])
left_pointer += 1
else:
result.append(right_li[right_pointer])
right_pointer += 1
# 其中一个指针到头之后（pointer指在最后，[pointer:]就是一个空列表），也即比较大小结束
# 退出循环后，将不为空的列表剩余元素添加到result中
# result+=left_li[left_pointer:]
result.extend(left_li[left_pointer:])
result.extend(right_li[right_pointer:])
#将最后排序的结果列表返回
return result
if __name__ =='__main__':
arr=[8, 4, 5, 7, 1, 3, 6, 2]
#arr=[54, 26, 93, 17, 77, 31, 44, 55]
print('原来的数组：')
print(arr)
result=merg_sort(arr)
print('排序后：')
print(result)
##如果硬要按照三部分拆分开来写的话
def merg_sort(arr):
n=len(arr)
if n<=1:
return arr
mid=n//2
left_li=merg_sort(arr[0:mid])
right_li=merg_sort(arr[mid:])
return merge(left_li, right_li)
def merge(left_li , right_li):
result=[]
left_pointer,right_pointer=0,0
while left_pointer<len(left_li) and right_pointer<len(right_li):
if left_li[left_pointer] <=right_li[right_pointer]:
result.append(left_li[left_pointer])
left_pointer += 1
else:
result.append(right_li[right_pointer])
right_pointer += 1
result.extend(left_li[left_pointer:])
result.extend(right_li[right_pointer:])
return result
if __name__ =='__main__':
arr=[8, 4, 5, 7, 1, 3, 6, 2]
print('原来的数组：')
print(arr)
result=merg_sort(arr)
print('排序后：')
print(result)
堆排序(Heap Sort)：
类别：基于选择排序+堆的思想（一种利用堆的概念来排序的选择排序）
参考链接：
- https://www.algomooc.com/2747.html
子所以是一个排序，是因为每次的操作都是发生在一个数组中的（表面上有一个堆，但是这个堆始终是在数组中进行体现的）
基础知识：
- 堆是一种完全二叉树（是按照顺序存储方式，从上至下，从左至右进行元素的添加，需要结合完全二叉树从数学上更好的去理解）
- 大顶堆：每个父结点的值都大于等于左右孩子结点（用于升序排列）
- 小顶堆：每一个父子结点都小于或等于其左右孩子结点的值 （用于降序排列）
- 时间复杂度：平均O(nlogn), 最坏O(nlogn), 最好O(nlogn)
- 空间复杂度：O(1)
- 适用场景：想得到一个序列中第k个最小元素之前的部分排序序列，最好采用堆排序（Topk系列问题）
- 算法稳定性：不稳定
- 该算法的核心：堆结点的调整
基本步骤如下：
下面的步骤也是辅助图片加深理解，属于是二次回顾的问题了
- 将无序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆（利用大顶堆可以迅速找出最大的节点）
- 从最后一个非叶子结点开始
- 第一个非叶子节点arr.length/2-1=5/2-1=1
- 从左至右，从上至下进行调整
- 将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端，此时数组末端储存了当前区间最大的元素
- 每次将堆顶元素与末尾元素交换，使末尾元素最大，去掉最后一个元素，然后将剩下的堆部分继续构造大顶堆，再将堆顶元素与末尾元素交换，得到第二大元素
- 如此反复进行交换、重建、交换（直到堆只剩下一个元素：大顶堆的长度为1）
# 仿照吴师兄的代码贴了一个比较好懂的版本，之后以这个版本为基础和原型
# 构建维护大顶堆的函数
# 传入的参数分别是数组\父节点、数组的最大小标
# 整个函数的实现过程就是在讨论父节点应该放置在哪个位置的问题，只是针对一个小堆的情况
def KeepHeap(arr,parent,high):
# 左子树节点
child = 2 *parent +1
# 用临时数组保存当前的父节点的值
temp=arr[parent]
# 遍历child后面的节点，把temp放入合理位置的过程
while child <high:
# 如果发现左子树的值小于右子树的值，将child切换到右子树的位置
# 否则就证明左子树的值是大于右子树的值，不需要进行切换
# if child +1<high,确保得有左右子节点才会进行相应的比较
if child +1< high and arr[child] <arr[child+1]:
# 将左节点切换到右节点
child+=1
# 当父节点的值是大于左右子节点的，说明parent就在正确的位置上面，直接退出
if temp>arr[child]:
break
# 父节点的值是小于左子节点的，需要进行交换(将最大值赋值给父节点)
else:
arr[parent]=arr[child]
# 记录此时的parent的位置（实际上如果是数组的话就是相应的下标）
parent=child
# 此时子节点已经发生变化，从它的左子节点开始(如果是数组就是需要更新现在的左子节点的下标)
child=2*parent+1
# 循环结束之后，将temp放在正确的位置
arr[parent]=temp
# 以下为堆排序的过程
def Heap_Sort(arr):
# 1.建堆（用到了完全二叉树的定义）
# 根据升序，这里选择的是大顶堆
# 先找到最后一个非叶子节点的根节点
# 向上循环根节点，从小到大
n=len(arr)
for i in range(n//2,-1,-1):
# 调用维护大顶堆的函数
KeepHeap(arr,i,n)
# 为了理解的方便，这里打印一行,这里打印的结果应该是所有的子节点为根的堆都是大顶堆
print('arr of heap',arr)
# 2. 挨个的出数，按照升序进行排列
# 一开始最大元素是[0],被换到最后一个，数组末端存储了当前区间的最大元素
# 从n-0,不断的和[0]元素进行交换，重新排序（n把第2，3...n的数翻转到最下面）
# i表示数组的序列，从0~n-1，因为是倒序的，所以写范围的时候就需要特别注意
for i in range(n-1,-1,-1):
# 交换元素
arr[0],arr[i]=arr[i],arr[0]
# 交换之后调用维护最大堆的函数
# 始终是从下标为0父节点开始的，并且在当前的调用过程中，一直到第i下标
KeepHeap(arr,0,i)
# 写主函数
if __name__=='__main__':
numbers = [54, 26, 93, 17, 77, 31, 44, 55, 20, 13]
Heap_Sort(numbers)
print(numbers)
# 排序之后的结果
[13, 17, 20, 26, 31, 44, 54, 55, 77, 93]