十大排序算法(Python实现)
算法复杂度
| 排序方法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | O ( 1 ) O(1) O(1) | 稳定 |
| 插入排序 | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | O ( 1 ) O(1) O(1) | 稳定 |
| 选择排序 | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | 不稳定 |
| 堆排序 | O ( n log n ) O(n \log n) O(nlogn) | O ( n log n ) O(n \log n) O(nlogn) | O ( n log n ) O(n \log n) O(nlogn) | O ( n ) O(n) O(n) | 不稳定 |
| 希尔排序 | O ( n 1.3 ) O(n^{1.3}) O(n1.3) | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | O ( 1 ) O(1) O(1) | 不稳定 |
| 归并排序 | O ( n log n ) O(n \log n) O(nlogn) | O ( n log n ) O(n \log n) O(nlogn) | O ( n log n ) O(n \log n) O(nlogn) | O ( n ) O(n) O(n) | 稳定 |
| 快速排序 | O ( n log n ) O(n \log n) O(nlogn) | O ( n 2 ) O(n^2) O(n2) | O ( n log n ) O(n \log n) O(nlogn) | O ( log n ) O(\log n) O(logn) | 不稳定 |
| 计数排序 | O ( n + k ) O(n+k) O(n+k) | O ( n + k ) O(n+k) O(n+k) | O ( n + k ) O(n+k) O(n+k) | O ( n + k ) O(n+k) O(n+k) | 稳定 |
| 桶排序 | O ( n + k ) O(n+k) O(n+k) | O ( n l o g n ) O(nlogn) O(nlogn) | O ( n ) O(n) O(n) | O ( n + k ) O(n+k) O(n+k) | 稳定 |
| 基数排序 | O ( n ∗ k ) O(n*k) O(n∗k) | O ( n ∗ k ) O(n*k) O(n∗k) | O ( n ∗ k ) O(n*k) O(n∗k) | O ( n ) O(n) O(n) | 稳定 |
冒泡排序
冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来，直到数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的右端。
算法描述
- 比较相邻元素，如果第一个比第二个大，就交换它们
- 对每个相邻元素作同样的比较交换操作，从开始的第一对到结尾的最后一对，这样一轮过后最后的元素就会是最大数
- 针对所有元素重复以上操作，除了最后一个(因为已经排序出来)
- 重复步骤1～3，直到排序完成
步骤4可以设置一个flag记录是否出现逆序的情况，如果没有就提前完成排序
复杂度分析
步骤1～2为第一轮遍历，从开始的第一对到最后一对，总共n-1对，步骤3第二轮重复时不需要最后一个，此时遍历n-2次，排序完成时应遍历操作了 n − 1 + n − 2 + n − 3 + . . . + 1 = n 2 / 2 − n / 2 n-1+n-2+n-3+...+1=n^2/2-n/2 n−1+n−2+n−3+...+1=n2/2−n/2次，时间复杂度为 O ( n 2 ) O(n^2) O(n2)
最好的情况(设置flag)下只需要进行第一轮遍历，因此为 O ( n ) O(n) O(n)
def bubble_sort(arr):
'''冒泡排序
'''
for i in range(1, len(arr)):
found = False # 定义是否发现逆序的flag
for j in range(0, len(arr)-i):
if arr[j] > arr[j+1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
found = True
if not found:
break
return arr
插入排序
def insert_sort(arr):
'''插入排序
'''
for i in range(len(arr)):
pre_index = i-1
current = arr[i] # 取出元素
'''从当前位置向前扫描'''
while pre_index >= 0 and arr[pre_index] > current:
arr[pre_index+1] = arr[pre_index]
pre_index -= 1
# 扫描完成，将取出元素插入到当前位置后面
arr[pre_index+1] = current
return arr
选择排序
def selection_sort(arr):
'''选择排序
'''
for i in range(len(arr) - 1):
# 记录最小数的索引
min_index = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
min_index = j
# i 不是最小数时，将 i 和最小数进行交换
if i != min_index:
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
堆排序
def heap_sort(arr):
from heapq import heappush,heappop # heapq模块总是构成小顶堆
h = []
for i in range(len(arr)):
heappush(h, arr[i])
# 每次heappop移除堆顶的时候python内部自动构成新堆
return [heappop(h) for i in range(len(h))]
希尔排序
def shell_sort(arr):
'''希尔排序
'''
import math
gap = 1 # 增量，即分成子序列的个数
while(gap < len(arr)/3): # 动态定义增量间隔，为了最后增量能够减小到1
gap = gap*3+1
while gap > 0:
# 从第一组开始插入排序
for i in range(gap, len(arr)):
temp = arr[i]
j = i-gap
while j >= 0 and arr[j] > temp:
arr[j+gap] = arr[j]
j -= gap
arr[j+gap] = temp
# 增量减小3倍
gap = math.floor(gap/3)
return arr
归并排序
def merge_sort(arr):
import math
if(len(arr)<2):
return arr
'''拆分两半'''
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:]
return merge(merge_sort(left), merge_sort(right))
def merge(left,right):
'''合并
'''
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0));
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0));
while right:
result.append(right.pop(0));
return result
快速排序
def partition(arr,low,high):
'''分割数组
'''
i = ( low-1 ) # 最小元素索引
pivot = arr[high]
for j in range(low , high):
# 当前元素小于或等于 pivot
if arr[j] <= pivot:
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return i+1
def quick_sort(arr,low,high):
'''quick_sort
Args:
arr [type]: 数组
low [type]: 起始索引
high [type]: 结束索引
'''
if low < high:
pi = partition(arr,low,high)
quick_sort(arr, low, pi-1)
quick_sort(arr, pi+1, high)
return arr
arr = [3,1,4,5,6]
quick_sort(arr,0,len(arr)-1)
print(arr)
计数排序
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数
算法描述
- 找出待排序的数组中最大元素，新建一个数组C，C的长度为最大元素的值+1
- 统计累加原数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
def counting_sort(arr):
'''只适用于整数数组
'''
bucket_len = max(arr)+1 # 新数组长度为arr中的最大值+1
bucket = [0]*bucket_len
# 开始计数
for i in range(len(arr)):
if not bucket[arr[i]]:
bucket[arr[i]]=0
bucket[arr[i]]+=1
# 按顺序重新填入
sorted_index = 0
for j in range(bucket_len):
while bucket[j]>0:
arr[sorted_index] = j
sorted_index+=1
bucket[j]-=1
return arr
桶排序
算法描述
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。其原理是：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序(使用时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)的快排等)
- 设置一个定量的数组当作空桶
- 遍历输入数据，并且把数据一个一个放到对应的桶里去
- 对每个不是空的桶进行排序
- 从不是空的桶里把排好序的数据拼接起来。
复杂度分析
首先 n n n次遍历，将数据装入 k k k个桶中，时间为 T ( n ) T(n) T(n)；
然后对每个桶中的元素采取先进的排序算法(一般复杂度为 O ( n l o g n ) O(n log n) O(nlogn))，时间为 T ( k ∗ ( n / k ) ∗ l o g ( n / k ) ) T(k*(n/k)*log(n/k)) T(k∗(n/k)∗log(n/k));
最后 k k k个桶合并时间为 T ( k ) T(k) T(k);
所有时间为 T ( n ) + T ( k ∗ ( n / k ) ∗ l o g ( n / k ) ) + T ( k ) = T ( n ∗ ( 1 + l o g ( n / k ) + k / n ) ) T(n)+T(k*(n/k)*log(n/k))+T(k)=T(n*(1+log(n/k)+k/n)) T(n)+T(k∗(n/k)∗log(n/k))+T(k)=T(n∗(1+log(n/k)+k/n))，一般 k < n k<n k<n，所以有：
- 效率最高的时候 k = n k=n k=n，时间复杂度为 O ( n ) O(n) O(n);
- 最低的时候 k = 1 k=1 k=1，复杂度为 O ( n l o g n ) O(nlogn) O(nlogn);
- 平均时间复杂度为 O ( n + k ) O(n+k) O(n+k) .
空间复杂度为 O ( n + k ) O(n+k) O(n+k)
def bucket_sort(arr):
"""桶排序"""
min_num = min(arr)
max_num = max(arr)
# 桶的大小
bucket_range = (max_num-min_num) / len(arr)
# 桶数组
count_list = [ [] for i in range(len(arr) + 1)]
# 向桶数组填数
for i in arr:
count_list[int((i-min_num)//bucket_range)].append(i)
arr.clear()
# 回填，这里桶内部排序直接调用了sorted
for i in count_list:
for j in sorted(i):
arr.append(j)
import random
random.seed(54)
arr = [random.randint(0,100) for _ in range(10)]
print("原始数据：", arr)
bucket_sort(arr)
print("桶排序结果：", arr)
# 结果：
原始数据： [17, 56, 71, 38, 61, 62, 48, 28, 57, 42]
桶排序结果： [17, 28, 38, 42, 48, 56, 57, 61, 62, 71]
基数排序
基数排序是一种非比较型整数排序算法，其原理是将所有待比较数值(可以整数，也可以小数)统一为同样的数位长度，数位较短的数补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序(LSD,Least significant digital)完成以后，数列就变成一个有序序列。或者也可以从最高位到最低位开始排序，即MSD(Most significant digital)的方式。
计数排序、桶排序和基数排序这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；
算法描述
- 取得数组中的最大数，并取得位数；
- arr为原始数组，从最低位开始取每个位组成radix数组
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）
复杂度分析
设总位数为
k
k
k，待排序元素个数为
n
n
n，由于每一轮的计数排序中是固定的0～9范围的值，因此每轮排序时间为
T
(
n
+
10
)
T(n+10)
T(n+10)，总的基数排序时间复杂度为
O
(
n
∗
k
)
O(n*k)
O(n∗k)。尽管
O
(
n
∗
k
)
O(n*k)
O(n∗k)和
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)难以比较，但一般
k
<
l
o
g
n
k<logn
k<logn。所以一般来讲，基数排序要快于基于比较的排序，比如快速排序。
基数排序中需要在每轮计数排序中使用临时
O
(
n
+
10
)
O(n+10)
O(n+10)的空间，因此空间复杂度为
O
(
n
)
O(n)
O(n)。
def radix_sort(arr):
digit = 0
max_digit = 1
max_value = max(arr)
#找出列表中最大的位数
while 10**max_digit < max_value:
max_digit = max_digit + 1
while digit < max_digit:
temp = [[] for i in range(10)]
for i in arr:
#求出每一个元素的个、十、百位的值
t = int((i/10**digit)%10)
temp[t].append(i)
coll = []
for bucket in temp:
for i in bucket:
coll.append(i)
arr = coll
digit = digit + 1
return arr