九大排序算法 一、直接插入排序 二、希尔排序 三、冒泡排序 四、快速排序 五、简单选择排序 六、堆排序 大顶堆：父节点比子节点大，堆顶元素必为最大值 小顶堆：子节点比父节点大，堆顶元素必为最小值 七、归并排序 八、基数排序 九、Timsort
每次选择一个元素，并且将这个元素和已经排好序的数组的所有元素进行比较，然后插入到合适的位置
举例： 38,65,97,76,13,27,49
[38],65,97,76,13,27,49
[38,65],97,76,13,27,49
[38,65,97],76,13,27,49
[38,65,76,97],13,27,49
[13,38,65,76,97],27,49
...
[13,27,38,49,65,76,97]
最好O(N),最坏/平均时间复杂度O(N^2)
空间复杂度O(1)
代码如下：
def insertion_sort(arr):
len_ = len(arr)
for i in range(1,len_):
tmp = arr[i]
j = i - 1
while j >= 0:
if arr[j] > tmp:#逆序遍历已排好序的数，如果当前的数比要插入的数大，就将要插入的数前移
arr[j+1] = arr[j]
arr[j] = tmp
j -= 1
print(arr)
二、希尔排序
这个是插入排序的修改版，根据步长由长到短分组，进行排序，直到步长为1为止，属于插入排序的一种。
基本原理：首先将待排序的元素分成多个子序列，使得每个子序列的元素个数相对较少，对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序后”再进行一次直接插入排序
平均时间复杂度O(NlogN),最差O(N^s)
空间复杂度O(1)
代码如下：
# 希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
# 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
# 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
# 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
# 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
def shell_sort(arr):
step = len(arr) // 2 #设定步长
while step > 0:
for i in range(step,len(arr)):
while i >= step and arr[i-step] > arr[i]: #类似插入排序,当前值与指定步长之前的值比较,符合条件则交换位置
arr[i],arr[i-step] = arr[i-step],arr[i]
i -= step
step = step // 2
return arr
三、冒泡排序
最好O(N),最坏/平均O(N^2)
空间复杂度O(1)
代码如下：
def bubble_sort(arr):
len_ = len(arr)
for i in range(len_):
j = i
while j < len_-1:
if arr[j] > arr[j+1]: #先冒大的
arr[j],arr[j+1] = arr[j+1],arr[j]
j += 1
print(arr)
def bubble_sort1(arr):
len_ = len(arr)
for i in range(0,len_):
for j in range(i+1,len_):
if arr[i] > arr[j]: #先冒小的
arr[i],arr[j] = arr[j],arr[i]
print(arr)
return arr
res= bubble_sort1(arr=[36,25,48,12,25,65,43,57])
# print(res)
四、快速排序
原理：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前部分的所有记录均比后部分的所有记录小，然后再一次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。
最好O(NlogN)：每次都恰好五五分,一次递归共需要比较n次，递归深度为lgn；
最坏O(N^2)：已排序数组，比较次数为
平均O(NlogN)：
快排在所有平均时间复杂度为O(NlogN)的算法中，平均性能最好
空间复杂度O(logN)
当初始序列整体或局部有序时，快排的会退化为冒泡排序。
代码如下：
#分治法
def quick_sort(arr,left,right):
if left >= right:
return arr
pivot = arr[left] #取第一个元素为哨兵
low = left #保留初始的left和right的值，后面要用
high = right
while left < right:
while left < right and arr[right] >= pivot: #从右向左,找到第一个比pivot小的元素
right -= 1
arr[left] = arr[right] #把该右边值放到左边位置上
while left < right and arr[left] < pivot: #从左向右，找到第一个比pivot大的元素
left += 1
arr[right] = arr[left] #把该左边值放到右边位置上
arr[right] = pivot #此时，left和right指向同一个位置
quick_sort(arr,low,left-1)
quick_sort(arr,right+1,high)
return arr
arr = [3,4,2,8,9,5,1]
left,right = 0,len(arr)-1
res = quick_sort(arr,left,right)
print(res)
【快排的优化】三数取中（median-of-three）
引入的原因：虽然随机选取枢轴时，减少出现不好分割的几率，但是还是最坏情况下还是O(n2），要缓解这种情况，就引入了三数取中选取枢轴
分析：最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是第N/2个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的不好情形，并且减少快排大约14%的比较次数
举例：待排序序列为：8 1 4 9 6 3 5 2 7 0
左边为：8，右边为0，中间为6.
我们这里取三个数排序后，中间那个数作为枢轴，则枢轴为6
注意：在选取中轴值时，可以从由左中右三个中选取扩大到五个元素中或者更多元素中选取，一般的，会有（2t＋1）平均分区法（median-of-(2t+1)，三平均分区法英文为median-of-three）。
具体思想：对待排序序列中low、mid、high三个位置上数据进行排序，取他们中间的那个数据作为枢轴，并用0下标元素存储枢轴。
即：采用三数取中，并用0下标元素存储枢轴。
取中枢的代码如下：
#三数取中
#取待排序序列中low、mid、high三个位置上数据，选取他们中间的那个数据作为枢轴
def findMedian(arr,low,high):
mid = low + (high-low) >> 1
if arr[mid] > arr[high]: #目标: arr[mid] <= arr[high]
arr[mid],arr[high] = arr[high],arr[mid]
if arr[low] > arr[high]: #目标: arr[low] <= arr[high]
arr[low],arr[high] = arr[high],arr[low]
if arr[mid] > arr[low]: #目标: arr[low] >= arr[mid]
arr[low], arr[mid] = arr[mid], arr[low]
print(arr)
return arr[low] #low的位置上保存这三个位置中间的值
arr = [1,3,2]
res = findMedian(arr,0,2)
print(res)
测试数据分析：使用三数取中选择枢轴优势还是很明显的，但是还是处理不了重复数组
五、简单选择排序
原理：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录进行交换；接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有1个时为止。
举例： 38,65,97,76,13,27,49
13,[65,97,76,38,27,49]
13,27,[97,76,38,65,49]
...
13,27,38,49,65,76,97
最好最坏时间复杂度O(N^2)
空间复杂度O(1）
代码如下：
def select_sort(arr):
len_ = len(arr)
for i in range(len_):
min = i
for j in range(i+1,len_):
if arr[j] < arr[min]:
min = j
arr[min],arr[i] = arr[i],arr[min] #一轮结束再交换
# print (arr)
return arr
res = select_sort(arr=[38,65,97,76,13,27,49])
print(res)
六、堆排序
1.堆排序
大顶堆：父节点比子节点大，堆顶元素必为最大值
小顶堆：子节点比父节点大，堆顶元素必为最小值
原理：
对于给定的n个记录，初始时把这些记录看作为一棵顺序存储的二叉树，然后将其调整为一个大顶堆，然后将堆的最后一个元素与堆顶元素（二叉树根节点）
进行交换后，堆的最后一个元素即为最大记录;接着将前(n-1)个元素(不包括最大记录)重新调整为一个大顶堆，再将堆顶元素与当前堆的最后一个元素进行交
换后得到次大的记录，重复该过程直到调整的堆中只剩下一个元素时为止，该元素即为最小记录，此时可得到一个有序序列。
两过程：（1）建堆，自下(最后一个非叶子节点)而上(第一个非叶子节点)，自右向左
（2）交换堆顶元素与最后一个元素的位置
---------->>
堆排序过程：
建堆时间复杂度O(n)
假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；高层也是这样逐渐递归。
那么总的时间计算为：s = 2^( i - 1 ) * ( k - i )；其中 i 表示第几层，2^( i - 1) 表示该层上有多少个元素，( k - i) 表示子树上要下调比较的次数。
S = 2^(k-2) * 1 + 2^(k-3)2…..+2(k-2)+2^(0)*(k-1) ===> 因为叶子层不用交换，所以i从 k-1 开始到 1；
S = 2^k -k -1；又因为k为完全二叉树的深度，而log(n) =k，把此式带入；
得到：S = n - log(n) -1，所以时间复杂度为：O(n)
-------------------------------------------------------------------------------------------------------
在取出堆顶点放到对应位置并把原堆的最后一个节点填充到堆顶点之后，需要对堆进行重建，只需要对堆的顶点调用adjustheap()函数。
每次重建意味着有一个节点出堆，所以需要将堆的容量减一。adjustheap()函数的时间复杂度k=log(n)，k为堆的层数。所以在每次重建时，随着堆的容量的减小，层数会下降，函数时间复杂度会变化。重建堆一共需要n-1次循环，每次循环的比较次数为log(i)，则相加为：log2+log3+…+log(n-1)+log(n)≈log(n!)。可以证明log(n!)和nlog(n)是同阶函数：
初始化建堆的时间复杂度为O(n)，排序重建堆的时间复杂度为nlog(n)，所以总的时间复杂度为O(n+nlogn)=O(nlogn)。另外堆排序的比较次数和序列的初始状态有关，但只是在序列初始状态为堆的情况下比较次数显著减少，在序列有序或逆序的情况下比较次数不会发生明显变化。
代码如下：
#!user/bin/env python3
# -*- coding: gbk -*-
import time
import heapq
def adjust_heap(arr,i,len_):
# 在堆中做结构调整使得父节点的值大于子节点
lchild = 2 * i + 1 #左节点
rchild = 2 * i + 2 #右节点
maxs = i
if i < len_ / 2:
if lchild < len_ and arr[lchild] > arr[maxs]:
maxs = lchild
if rchild < len_ and arr[rchild] > arr[maxs]:
maxs = rchild
if maxs != i:
arr[maxs],arr[i] = arr[i],arr[maxs]
adjust_heap(arr,maxs,len_) #调整maxs下面的子堆
def build_heap(arr,len_):
for i in range(len_//2,-1,-1): #从最后一个非叶子节点开始到第一个非叶子节点结束
adjust_heap(arr,i,len_)
def heap_sort(arr):
len_ = len(arr)
#step1 建堆
build_heap(arr,len_) #将原始数组构建成一个堆
#step2 对堆进行排序
for i in range(len_-1,-1,-1):
arr[i],arr[0] = arr[0],arr[i]#将大顶堆的顶点值与最后一个叶子节点交换，这样，就能得到一个从小到大的排序
adjust_heap(arr,0,i) #继续对剩下的元素进行堆排序，此时，最大值在数组的末尾
return arr
import random
arr = [random.randint(1, 2000) for i in range(1000)]
start1_time = time.time()
res1 = heap_sort(arr)
# print(res1)
end1_time = time.time()
print('my method',end1_time-start1_time)
start2_time = time.time()
heapq.heapify(arr)
end2_time = time.time()
print('inner method',end2_time-start2_time)
#可以看到，我们实现的排序算法在时间上不如内置的heapq.heapify()
2.n个数组找topk
有n个数组，每个数组中有m个元素，并且是有序排列好的，现在如何在这n*m个数中找出排名前500的数？
思路1：快排partition，缺点会改变数组顺序
思路2：堆排序，速度快，不改变数组顺序
（1）首先建立大顶堆，堆的大小为数组的个数，即n，把每个数组最大的值（数组第一个值）存放到堆中。Python中heapq是小顶堆，通过对输入和输出的元素分别取相反数来实现大顶堆的功能
（2）接着删除堆顶元素，保存到另外一个大小为500的数组中，然后向大顶堆插入删除的元素所在数组的下一个元素。
（3）重复第（1）、（2）个步骤，直到删除个数为最大的k个数，这里为500。
import heapq
def getTop(data):
rowSize = len(data)
columnSize = len(data[0])
result = [None] * columnSize #保持一个最小堆,这个堆存放来自20个数组的最大数
heap = []
i = 0
while i < rowSize:
#数值,数值来源的数组,数值在数组中的次序index
arr = (-data[i][0],i,0)
heapq.heappush(heap,arr)
i += 1
num = 0
while num < columnSize:
d = heapq.heappop(heap)
result[num] = -d[0]
num += 1
if num >= columnSize:
break
arr = (-data[d[1]][d[2]+1],d[1],d[2]+1)
heapq.heappush(heap,arr)
return result
#3个数组,每个数组有5个元素且有序,找出排名前5的值
data = [[29,17,14,2,1],[19,17,16,15,6],[30,25,20,14,5]]
print(getTop(data))
七、归并排序
关键两步骤：（1）划分子表（2）合并半子表
原理（归并排序相比较之前的排序算法而言加入了分治法的思想）：
1.如果给的数组只有一个元素的话，直接返回（也就是递归到最底层的一个情况）
2.把整个数组分为尽可能相等的两个部分（分）
3.对于两个被分开的两个部分进行整个归并排序（治）
4.把两个被分开且排好序的数组拼接在一起
最好/最坏/平均O(NlogN)
空间复杂度O(1)
代码如下：
def merge(left,right):
'''将两个长度之和为n的有序子序列合并为一个有序序列，最多执行n-1次关键字值间的比较，时间复杂度为O(n)'''
i,j = 0,0
result = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
#循环结束之后可能有一个列表有剩余元素，直接加到result后面
result += left[i:]
result += right[j:]
return result
def merge_sort(arr):#归并排序
if len(arr) <= 1:
return arr
m = len(arr) // 2
#分
left = merge_sort(arr[:m])
right = merge_sort(arr[m:])
#合并
return merge(left,right)
arr = [3,4,2,8,9,5,1]
res = merge_sort(arr)
print(res)
八、基数排序
原理：将最低位优先法用于单关键字的情况,个位-十位-百位,依此类推
时间复杂度O(Nlog(r)m)
代码如下：
def radix_sort(arr,radix=10):
#求最大数的位数
k = len(str(max(arr)))
bucket = [[] for i in range(radix)]
tmp = 0
for i in range(1,k+1):#遍历k位，从低位到高位
for j in arr:#遍历每个数
tmp = j%(radix**i)//radix**(i-1)
bucket[tmp].append(j)#计算j在第k位上的数
del arr[:]#清空原arr
for z in bucket:
arr += z#按照桶内元素的顺序依次加入arr
del z[:]#清空该桶内的元素
return arr
arr = [33,24,2,8,19,5,1]
res = radix_sort(arr)
print(res)
九、Timsort
Timsort是结合了合并排序（merge sort）和插入排序（insertion sort）而得出的排序算法，它在现实中有很好的效率。
参考文献：
【3】手撕九大经典排序算法
【5】Timsort原理介绍 - 微信公众号：猴子聊人物 - CSDN博客