发布时间：2023-12-22 09:51:16来源：网络阅读（598）
重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换。
*实现步骤:
（1）比较相邻的元素。如果第一个比第二个大，就交换它们两个；
（2）对每一对相邻元素作同样的工作，从开始第一对到最后一对，这样在最后的元素应该会是最大的数；
（3）针对所有的元素重复以上的步骤，除了最后一个；
（4）重复步骤1~3，直到排序完成。
*算法实例：
def bubble_sort(nums):
for i in range(len(nums) - 1): # 这个循环负责设置冒泡排序进行的次数
for j in range(len(nums) - i - 1): # j为列表下标
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j] #满足条件互换位置，省略了中间变量的写法
return nums
print(bubble_sort([45, 32, 8, 33, 12, 22, 19, 97]))
"""
扩展：交换a，b的值，a = ‘hello’ b = ‘world’
解法一
用中间变量去接受
team = a
a = b
b = team
解法二
a = ‘hello’
b = ‘world’
a,b = b,a
"""首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
*算法描述:
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
（1）对于一组关键字{K1,K2,…,Kn}，
（2）首先从K1,K2,…,Kn中选择最小值，假如它是 Kz，则将Kz与 K1对换；
（3）然后从K2，K3，… ，Kn中选择最小值 Kz，再将Kz与K2对换。
（4）如此进行选择和调换n-2趟。第(n-1)趟，从Kn-1、Kn中选择最小值 Kz将Kz与Kn-1对换，最后剩下的就是该序列中的最大值，
*算法实例：
def selectionSort(arr):
for i in range(len(arr) - 1):
minIndex = i # minIndex记录最小数的索引
for j in range(i + 1, len(arr)):
if arr[j] < arr[minIndex]:
minIndex = j
if i != minIndex:
arr[i], arr[minIndex] = arr[minIndex], arr[i] # i 不是最小数时，将 i 和最小数进行交换
return arr
print(selectionSort([45, 32, 8, 33, 12, 22, 19, 97]))
"""
[45, 32, 8, 33, 12, 22, 19, 97]
i=0、1、2、3、4、5、6
当i=0时，minIndex=0
arr[0]分别和arr[1,2,...7]去比较，找出最小值，最小值的下标赋值给minIndex，若最小值和arr[0]不相等，则交换位置
————》[8, 32, 45, 33, 12, 22, 19, 97]
当i=1时，minIndex=1
arr[1]分别和arr[2,...7]去比较，找出最小值，最小值的下标赋值给minIndex，若最小值和arr[1]不相等，则交换位置
————》[8, 12, 45, 33, 32, 22, 19, 97]
i=3：
[45, 32, 8, 12, 33, 22, 19, 97]
i=4：
[45, 32, 8, 33, 12, 22, 19, 97]
i=5：
[45, 32, 8, 33, 12, 19, 22, 97]
i=6：
[45, 32, 8, 33, 12, 22, 19, 97]
i=7：
[8, 12, 19, 22, 32, 33, 45, 97]
"""通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
*算法描述:
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
（1）将第一个数据当成已排序序列，后面的数据（即第2，3....）当成未排序序列
（2）取未排序的第一个数据与已排序的最后一个数据进行比较
（3）当不需要交换时则此轮插入完成。已排序序列变成了两个数据，未排序序列数据减1。
（4）如果位置错误则交换位置，交换位置后，继续将插入的数据与相邻的前一个数据进行比较。
（5）当插入的数据已经通过交换位置到达了数列的最前端，不需要再次交换了，此轮插入完成。
（6）一直重复取未排序的第一个数据插入已排序序列中，直到所有数据都已经插入到已排序序列中，排序完成
可参考：
Python实现插入排序_Python碎片的博客-CSDN博客_python插入排序
*算法实例：
def insertionSort(arr):
for i in range(1,len(arr)):
key=arr[i] # key为未排序的第一个数据
j=i-1 # a[j]为已排序的最后一个数据
while j>=0 and arr[j]>key: # 如果已排序的最后一个数据大于未排序的第一个数据
arr[j],arr[j+1]=arr[j+1],arr[j] # 交换位置
j-=1 # 用未排序的数据一直和已排序的倒数第二个、倒数第三个....一直比较，不符合排序规则就交换位置，直至已经排序的数列的最前端结束
return arr
print(insertionSort([45, 32, 8, 33, 12, 22, 19, 97]))
"""
i=1,2,3...8
while i=1：
key=32，j=0,a[j]=45,因为45>32，所以交换位置，==>[ 32,45,8, 33, 12, 22, 19, 97]
此时j=j-1=-1<0,while循环结束,for循环第一次结束
while i=2：
key=8，j=1,a[j]=45,因为45>8，所以交换位置，==>[ 32,8,45, 33, 12, 22, 19, 97]
此时j=j-1=0,arr[j]=32>key=8,那么交换位置==>[8，32,45, 33, 12, 22, 19, 97]
此时j=j-1=-1<0,while循环结束,for循环第一次结束
while i=3:
key=33，j=2,a[j]=45,因为45>33，所以交换位置，==>[ 8,32,33, 45, 12, 22, 19, 97]
此时j=j-1=1,arr[j]=32<key=33,so不用交换位置
此时j=j-1=0,arr[j]=8<key=33,so不用交换位置
此时j=j-1=-1<0,while循环结束,for循环第一次结束
while i=4:
key=12，j=3,a[j]=45,因为45>12，所以交换位置，==>[ 8,32,33, 12, 45, 22, 19, 97]
此时j=j-1=2,arr[j]=33>key=12,so交换位置==>[ 8,32,12, 33, 45, 22, 19, 97]
此时j=j-1=1,arr[j]=32>key=12,so交换位置==>[ 8,12,32, 33, 45, 22, 19, 97]
此时j=j-1=0,arr[j]=8<key=12,so不用交换位置
此时j=j-1=-1<0,while循环结束,for循环第一次结束
"""是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。 希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。
*算法描述:
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
（1）选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
（2）按增量序列个数k，对序列进行k 趟排序；
（3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排 序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
*算法实例：
def shellSrot(arr):
n=len(arr)
gap=n//2 # 初始步长
while gap > 0:
# 按步长进行插入排序
for i in range(gap, n):
j = i
# 插入排序
while j >= gap and arr[j - gap] > arr[j]:
arr[j - gap], arr[j] = arr[j], arr[j - gap]
j -= gap
gap = gap // 2 # 得到新的步长
return arr
print(shellSrot([45, 32, 8, 33, 12, 22, 19, 97]))
"""
n=8,gap=4
j=4,5,6,7
j=4:
j=gap=4,arr[j-gap]=a[0]=45>arr[j]=arr[4]=12,交换位置==>[12, 32, 8, 33, 45, 22, 19, 97]
j=j-gap=0<jap,while结束
j=5:
j=gap=5,arr[j-gap]=a[1]=32>arr[j]=arr[2]=22,交换位置==>[12, 22, 8, 33, 45, 32, 19, 97]
j=j-gap=1<jap,while结束
j=6:
j=gap=6,arr[j-gap]=a[2]=8<arr[j]=arr[6]=19,不用交换位置
j=j-gap=2<jap,while结束
j=7:
j=gap=7,arr[j-gap]=a[3]=33<arr[j]=arr[7]=97,不用交换位置
j=j-gap=3<jap,while结束
【for循环第一次结束，gap=gap//2=2】
gap=2，j=2，3，4，5，6，7
j=2:
j=gap=2,arr[j-gap]=a[0]=12>arr[j]=arr[2]=8,交换位置==>[8, 22,12, 33, 45, 32, 19, 97]
j=j-gap=0<jap,while结束
j=3:
j=gap=3,arr[j-gap]=a[1]=32<arr[j]=arr[3]=33,不用交换位置
j=j-gap=1<jap,while结束
j=4:
j=gap=4,arr[j-gap]=a[2]=12<arr[j]=arr[4]=45,不用交换位置
j=j-gap=2=jap,arr[j-gap]=a[0]=8<arr[j]=arr[2]=12，不用交换位置
j=j-gap=0<jap,while结束
j=5:
j=gap=5,arr[j-gap]=a[3]=33>arr[j]=arr[5]=32,交换位置==>[8, 22,12, 32, 45, 33, 19, 97]
j=j-gap=3>jap,arr[j-gap]=a[3]=22<arr[j]=arr[5]=33，不用交换位置
j=j-gap=1<jap,while结束
j=6:
j=gap=6,arr[j-gap]=a[4]=45>arr[j]=arr[6]=19,交换位置==>[8, 22,12, 32, 19, 33, 45, 97]
j=j-gap=4>jap,arr[j-gap]=a[4]=19<arr[j]=arr[6]=45，不用交换位置
j=j-gap=2=jap,arr[j-gap]=a[0]=8<arr[j]=arr[2]=12，不用交换位置
j=j-gap=0<jap,while结束
j=7:
j=gap=7,arr[j-gap]=a[5]=33<arr[j]=arr[7]=97,不用交换位置
j=j-gap=5>jap,arr[j-gap]=a[3]=22<arr[j]=arr[5]=33，不用交换位置
j=j-gap=1<jap,while结束
【for循环第2次结束，gap=gap//2=1】......
"""
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
*算法描述:
（1）把长度为n的输入序列分成两个长度为n/2的子序列；
（2）对这两个子序列分别采用归并排序；
（3）将两个排序好的子序列合并成一个最终的排序序列。
*算法实例：
def merge_sort(li): #（分组）
if len(li) == 1:
return li
mid = len(li) // 2 #取拆分的中间位置
left = li[:mid] # 左侧子串
right = li[mid:] # 右侧子串
# 对拆分过后的左右子串再拆分，直到只有一个元素为止
ll = merge_sort(left)
rl =merge_sort(right)
return merge(ll,rl)
def merge(left,right): # 排序and合并
result = []
while len(left)>0 and len(right)>0:
# 为了保持稳定性，当遇到相等的时候优先把左侧的数放进结果列表，因为left本来也是大数列中比较靠左的
if left[0] <= right[0]:
result.append(left.pop(0)) #left.pop(0)为删除的项，将其添加到result列表末尾
else:
result.append(right.pop(0))
# while循环出来之后 说明其中一个数组没有数据了，我们把另一个数组添加到结果数组后面
result += left
result += right
return result
print(merge_sort([5,4,3,2,1]))
"""
[5,4,3,2,1]
第一次拆分==》[5,4]、 [3,2,1]
第二次拆分==》[5]、[4]、 [3]、[2,1]
第三次拆分==》[5]、[4]、[3]、[2]、[1]
merge(left,right)——>([5] [4])，([2] [1])，([3] [1, 2])，([4, 5] [1, 2, 3])
[5][4] # 第二次分组的结果
[4] #比较后，提出右边分组的第一个数字[4]，放进result中
[4, 5] #比较后，再将左边分组[5]赋值给result（左边结果的最后一次的分组排序完成）
[2][1] # 第三次分组的结果
[1] #比较后，提出右边分组的第一个数字[1]，放进result中
[1, 2] #比较后，再将左边分组[2]赋值给result（右边边结果的最后一次的分组排序完成）
[3][1, 2] #[1, 2]已经排序并绑定
[1] #比较后，提出右边分组的第一个数字[1]，放进result中
[1, 2] #比较后，提出右边分组的第一个数字[2]，放进result中
[1, 2, 3] #比较后，再将左边分组[3]赋值给result（右边边结果的第二次的分组排序完成）
[4, 5][1, 2, 3]
[1] #比较后，提出右边分组的第一个数字[1]，放进result中
[1, 2] #比较后，提出右边分组的第一个数字[2]，放进result中
[1, 2, 3] #比较后，提出右边分组的第一个数字[3]，放进result中
[1, 2, 3, 4, 5] #比较后，再将左边分组[4][5]赋值给result（最后为第一次分组的排序完成）
"""参考：
归并排序简单理解_你是人间四月天-CSDN博客
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
*算法描述:
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
（1）从数列中挑出一个元素，称为 “基准”（pivot）；
（2）重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
（3）递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
*算法实例：
def quickSort(arr,i,j):
if i>=j:
return arr
key=arr[i] # 第一个数组值作为比较值，首先保存到key中
low=i
high=j
while i<j:
while i<j and arr[j]>=key:
j-=1 # j(右边)指向的元素大于等于基准元素，则j向左移动，直至找到比key小的值
arr[i]=arr[j]
while i<j and arr[i]<=key:
i+=1 # i(左边)指向的元素大于等于基准元素，则i向右移动，直至找到比key大的值
arr[j]=arr[i]
# 退出循环后，low与high重合，此时所指位置为基准元素的正确位置,左边的元素都比基准元素小,右边的元素都比基准元素大
arr[j]=key
quickSort(arr,low,i-1) # 对基准元素左边的子序列进行快速排序
quickSort(arr,i+1,high) # 对基准元素右边的子序列进行快速排序
return arr
aa=[19,32,8,33,12,22,45]
print(quickSort(aa,0,len(aa)-1))
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
*算法描述:
（1）将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
（2）将其与末尾元素进行交换，此时末尾就为最大值。可称为有序区
（3）然后将剩余n-1个元素重新构造成一个堆，估且称为堆区(未排序)。
（4）这样会得到n个元素的次小值。重复执行，有序区从:1--->n，堆区：n-->0，便能得到一个有序序列了
*算法实例：
def big_endian(arr, start, end): # 构造大根堆
root = start
child = root * 2 + 1 # 左孩子
while child <= end: # 如果有孩子节点
if child + 1 <= end and arr[child] < arr[child + 1]:
# 如果有右孩子，且右孩子大于左孩子，就左换右，左孩子大则默认
child += 1
if arr[root] < arr[child]:
arr[root], arr[child] = arr[child], arr[root] # 父节点小于子节点直接交换位置
root = child # 将当前节点，作为父节点，查找他的子树
child = root * 2 + 1
# 如果调整的父节点比下面最大的子节点大，就直接打断循环，堆已经调整好
else:
break
def heap_sort(arr): # 无序区大根堆排序
start = len(arr) // 2 - 1 # 最后一个有孩子节点的根节点索引
end=len(arr)-1 #最后一个元素的索引
"""--把序列调整为一个大根堆--"""
while start>=0:
big_endian(arr, start, end) # 去调整所有的节点
start-=1 #每调整好一个节点，从后往前移动一个节点
"""--把堆顶元素和堆末尾的元素交换，然后把剩下的元素调整为一个大根堆--"""
while end>0:
arr[0], arr[end] = arr[end], arr[0] # 顶部尾部互换位置
big_endian(arr, 0, end-1) # 重新调整子节点的顺序，从顶开始调整
end-=1 #每调整好一个节点，从后往前移动一个节点
return arr #将列表返回
l = [20,50,20,40,70,10,80,30,60]
print(heap_sort(l))
参考：
堆排、python实现堆排 - G1733 - 博客园
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
*算法描述:
（1）找出待排序的数组中最大和最小的元素；
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项=》下图步骤a
（3）对所有的计数累加(从C中的第一个元素开始，每一项和前一项相加)=>下图步骤b
（4）反向填充目标数组：=》下图步骤c
将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
*算法实例：
"""-------第一种-------"""
def counting_sort(arr):
if len(arr) <= 1:
return arr
max_num= max(arr) # 找出列表最大值
min_num=min(arr)
count = [0] * (max_num+ 1) # 会得到一个长度是max_num+ 1的list，其中的每一个元素都是0。
for num in arr: # 遍历arr中的值,下标位置数+1（等于是记录每个数在数组中出现了多少次）
count[num] += 1 # 走访到的元素值为num，则计数列表中索引num的值加1
new_arr = list()
for i in range(len(count)):
# 因为count的长度是arr中的最大值+1，所以可以遍历arr中的所有数据
for j in range(count[i]): # count[i]表示元素i出现的次数，如果有多次，通过循环重复追加
new_arr.append(i)
return new_arr
arr = [2,9,3,1,2,3,1,5]
print(counting_sort(arr))
# """
# -------第二种：类似桶排序-------
# 计数排序本质上是一种特殊的桶排序，当桶的个数取最大( maxV-minV+1 )的时候，就变成了计数排序。
# """
# def counting_sort(arr):
# if len(arr) <= 1:
# return arr
# count = [] * len(arr) # 会得到一个长度是和arr相同的list。
# for num in arr: # 遍历arr中的值,下标位置数+1（等于是记录每个数在数组中出现了多少次）
# count.append(num) # 走访到的元素值为num，则计数列表中索引num的值加1
# new_arr = list()
# for j in sorted(count): # count[i]表示元素i出现的次数，如果有多次，通过循环重复追加
# new_arr.append(j)
# return new_arr
# arr = [2,5,3,0,2,3,0,3]
# print(counting_sort(arr))*概念：桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
*算法描述:
（1）设置一个定量的数组当作空桶；
（2）遍历输入数据，并且把数据一个一个放到对应的桶里去；
（3）对每个不是空的桶进行排序；
（4）从不是空的桶里把排好序的数据拼接起来。
*算法实例：
def bucket_sort(arr):
max_num=max(arr)
min_num=min(arr)
bucket_num=(max_num-min_num)//2+1 # 桶的个数
bucket=[[] for _ in range(int(bucket_num))] # 创建出2个桶
print('创建的bucket：',bucket)
for num in arr:
bucket[int((num-min_num)//2)].append(num) # 将数据添加到对应的桶中
print('添加数据后的bucket：',bucket)
new_arr=list() # 等同于new_arr=[]，new_arr=list()其实是调用了list类的__init__()方法，内部执行for循环，把元组转换为列表
for i in bucket: # i 表示第 i 个桶
for j in sorted(i): # j 表示对桶内数据排序后的第 j 个数据,依次取出放入new_arr
new_arr.append(j)
print('排序后的新列表：',new_arr)
return new_arr
arr=[5, 7, 3, 7, 2, 3, 2, 5, 9, 5, 7, 8]
print(bucket_sort(arr))参考：
Python实现桶排序_Python碎片的博客-CSDN博客_python桶排序代码
*概念：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。
基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。
*算法描述:
1. 求出待排序列表中的最大值，并求出最大值的位数，有多少位就需要进行多少轮分桶和合并。
2. 创建用于分配数据的桶。整数排序时，每一位的范围都在0~9之间，所以需要创建10个桶。
3. 从数据的个位开始(从最高位开始也可以)，按个位数对数据进行分桶，不考虑其它位的数据大小。
4. 按个位，所有数据都分桶完后，将所有桶中的数据进行合并，按先进先出的原则取出桶中的数据放入列表。
5. 对按个位排序后的列表，重复步骤3,4，继续按其他位对前面处理过的数据进行分桶和合并。一直到对每一位数据都进行分桶和合并完成，最终得到一个有序序列，列表排序完成。
*算法案例:
def radix_sort(array):
max_num = max(array)
place = 1
while max_num >= 10 ** place:
place += 1 # 确定位数
for i in range(place):
buckets = [[] for _ in range(10)] # 创建10个桶
for num in array:
radix = int(num / (10 ** i) % 10) # i=0时取个位，i=1时，取十位...
buckets[radix].append(num) # 第一次循环先按个位数进行分组，第二次将重置后的array按十位数进行分组
print('bucket is:', buckets)
j = 0
for k in range(10): # 刚开始创建了10个桶，现在从这10个桶依次取数据
for num in buckets[k]: # 从每个桶遍历数据
array[j] = num # 按个位数排序的方式重置array数组，得到重置后array，再按照十位数排序的方式重置array...
j += 1
return array
if __name__ == '__main__':
array = [25, 17, 33, 17, 22, 13, 32, 195, 9, 25, 27, 18]
print(radix_sort(array))参考：
Python实现基数排序_Python碎片的博客-CSDN博客_基数排序python
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n^(1.3—2)) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
| 归并排序 | O(n*log2(n)) | O(n*log2(n)) | O(n*log2(n)) | O(n) | 稳定 |
| 快速排序 | O(n*log2(n)) | O(n*log(n)) | O(n^2) | O(nlog2n) | 不稳定 |
| 堆排序 | O(n*log2(n)) | O(n*log2(n)) | O(n*log2(n)) | O(1) | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |
| 桶排序 | O(n+k) | O(n) | O(n^2) | O(n+k) | 稳定 |
| 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 |
稳定：如果a 原本在 b 前面，而a=b， 排序之后a 任然在b前面。
不稳定：如果 a 原本在 b 前面，而 a = b, 排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排列数据的总的操作次数。反映当 n 变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数。
1）单段代码看高频：比如循环。
2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
3）嵌套代码求乘积：比如递归、多重循环等
4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。
O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）、O(n^3)（立方阶）
O(2^n)（指数阶）、O(n!)（阶乘阶）
（1）若n较小( 如n≤50)， 可采用直接插入或直接选择排序；
（2）若文件初始状态基本有序(指正序)，则应选用直接插入、冒泡或随机的快速排序为宜；
（3）若n较大，则应采用时间复杂度为O(n log n) 的排序方法：快速排序、堆排序或归并排序；
（4）若n较小，考虑稳定性，可以使用：基数排序、计数排序或者桶排序。
其中 插入算法和 归并算法 对重复率比较高的排序比较友好；冒泡算法不适合大量数据。
来源：https://zhuanlan.zhihu.com/p/446918184
关键字： 算法
上一篇： 十大编程算法助程序员走上高手之路
下一篇： JS判断null
634
1283
1146
646
1308
1336
523
529
932
948
9178
5753
5265
4887
4329
4042
3169
3092
3087
3046
