文章目录
8.1排序算法的下界
| 算法 | 最好情况 | 最糟情况 | 平均情况 | 是否原址 |
|---|---|---|---|---|
| 插入排序 | Θ ( n ) \Theta(n) Θ(n) | Θ ( n 2 ) \Theta(n^2) Θ(n2) | Θ ( n 2 ) \Theta(n^2) Θ(n2) | 原址 |
| 冒泡排序 | Θ ( n ) \Theta(n) Θ(n) | Θ ( n 2 ) \Theta(n^2) Θ(n2) | Θ ( n 2 ) \Theta(n^2) Θ(n2) | 原址 |
| 选择排序 | Θ ( n 2 ) \Theta(n^2) Θ(n2) | Θ ( n 2 ) \Theta(n^2) Θ(n2) | Θ ( n 2 ) \Theta(n^2) Θ(n2) | 原址 |
| 归并排序 | Θ ( n l g n ) \Theta(nlgn) Θ(nlgn) | Θ ( n l g n ) \Theta(nlgn) Θ(nlgn) | Θ ( n l g n ) \Theta(nlgn) Θ(nlgn) | 非原址 |
| 堆排序 | O ( n l g n ) ) O(nlgn)) O(nlgn)) | O ( n l g n ) ) O(nlgn)) O(nlgn)) | − − − − ---- −−−− | 原址 |
| 快速排序 | Θ ( n l g n ) \Theta(nlgn) Θ(nlgn) | Θ ( n 2 ) \Theta(n^2) Θ(n2) | O ( n l g n ) O(nlgn) O(nlgn) | 原址 |
1、在最坏情况下，任何比较排序算法都需要
Ω
(
n
l
g
n
)
\Omega(nlgn)
Ω(nlgn)次比较
2、堆排和归并排序是渐进最优的比较排序算法
决策树模型： 比较排序可以被抽象为一颗决策树。决策树是一棵完全二叉树，它可以表示在给定输入规模情况下，某一特定排序算法对所有元素的比较操作。
8.2 计数排序
1、时间复杂度：
Θ
(
n
+
k
)
\Theta(n+k)
Θ(n+k)
2、计数排序具有稳定性：具有相同值的元素在输出数组中的相对次序与他们在输入数据中的相对次序相同。
3、非原址排序
"""计数排序"""
import numpy as np
def Counting_sort(A):
if len(A) < 2:
return A
MAX = max(A)
MIN = min(A)
C = [0] * (MAX - MIN + 1)
B=[0]*(len(A))
for i in range(0, len(A)):
C[A[i]] = C[A[i]] + 1
C = np.cumsum(C)
for i in range((len(A)-1),-1,-1):
"""此处不可以改为有 0->len(A)-1 因为C是一个累加的值，
即在往B中安放出现了3次的元素的A[i]，假设A[i]排列后分别位于索引（2，3，4）位置，
是先将A[i]放在第4的位置的，然后第3，第2的"""
B[C[A[i]]-1]=A[i]
C[A[i]]=C[A[i]]-1
return B
A = [2, 5, 3, 0, 2, 3, 0, 3]
print(Counting_sort(A))
8.3 基数排序
1、时间复杂度：
Θ
(
d
(
n
+
k
)
)
\Theta(d(n+k))
Θ(d(n+k)) n个k进制的d位数
2、具有稳定性但不是原址排序
"""基数排序"""
def Radix_SORT(A):
n = len(str(max(A)))
for k in range(n):#从低位到高位轮排序
bucket_list = [[] for i in range(10)]
for i in A:
bucket_list[i // (10 ** k) % 10].append(i)#基于计数排序
#A = [j for i in bucket_list for j in i]
A=[]
for i in bucket_list:
for j in i:
A.append(j)
return A
A = [329,457,657,839,436,720,355]
print(Radix_SORT(A))
#输出[329, 355, 436, 457, 657, 720, 839]
8.4 桶排序
1、时间复杂度：
T
(
n
)
=
Θ
(
n
)
+
∑
i
=
0
b
u
c
k
e
t
−
1
(
n
i
2
)
T(n)=\Theta(n)+\sum_{i=0}^{bucket-1}(n_i^2)
T(n)=Θ(n)+∑i=0bucket−1(ni2)(
n
i
n_i
ni表示桶B[i]中的元素个数,求和符号中的
(
b
u
c
k
e
t
−
1
)
(bucket-1)
(bucket−1)表示桶的个数）
当达到极限情况即每个桶只有一个数据时，桶排序的最好效率能够达到
O
(
n
)
O(n)
O(n)
2、具有稳定性
"""桶排序"""
# 插入排序
def INSERTION_SORT(A):
if len(A) < 2:
return A
for i in range(1, len(A)):
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j + 1] = A[j]
j = j - 1
A[j + 1] = key
return A
def BUCKET_SORT(A):
n = len(A)
BUCKET = [[] for i in range(n)]
for i in range(n):
BUCKET[int(n * A[i])].append(A[i])
RES = []
for j in BUCKET:
if j:
j = INSERTION_SORT(j)
for num in range(len(j)):
RES.append(j[num])
return RES
A = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
print(BUCKET_SORT(A))