线性时间排序

一.线性时间排序

1.排序算法复杂度都可以是线性时间O（n）

2.都是在一定假设的条件下进行

二.计数排序：假设输入的n个数据的每一个都是0-k区间的一个整数，对于一个元素x,确定小于x的元素个数，把x放在对于数组位置

时间复杂度：O(k+n);当k=O(n)时,

 1 #计数排序
 2 def counting_sort(A,B,k):
 3     n=len(A)
 4     C=[]
 5     for i in range(0,k+1):
 6         C.append(0)#C全置为0
 7     for j in range(0,n):
 8         C[A[j]]=C[A[j]]+1#计算A中每个元素的个数，存放在C中
 9     for i in range(1,k+1):
10         C[i]=C[i]+C[i-1]#总加和
11     for j in range(n-1,-1,-1):
12         #从后到前，把A[j]放在B的正确位置
13         B[C[A[j]]-1]=A[j]
14         C[A[j]]=C[A[j]]-1#更新C
15 
16 A=[2,5,3,0,2,3,0,3]
17 B=[0,0,0,0,0,0,0,0]
18 counting_sort(A,B,5)
19 print(A)
20 print(B)
21 ----------------------------------------
22 [2, 5, 3, 0, 2, 3, 0, 3]
23 [0, 0, 2, 2, 3, 3, 3, 5]

计数排序

二.基数排序：先按最低有效位进行排序，在将所有卡片合成一叠

为了保证计数排序的正确性，一位数排序算法必须是稳定的

四.桶排序:假设输入数据服从均匀分布，平均情况下它的时间代价为O(n)。将【0,1）区间划分n个相同大小的子区间（桶），对每个桶排序从而实现整个的排序

 1 import math
 2 
 3 #桶排序
 4 def bucket_sort(A):
 5     n = len(A)#实际控制桶的个数
 6     B = [[] for i in range(n)]
 7     print(B)#创建空列表B
 8     for i in range(0, n):
 9         B[math.floor(n * A[i])].append(A[i])
10     print(B)#把A【i】插入B[nA[i]]
11     for i in range(0, n):
12         insertion_sort(B[i])#对每个B【i】排序
13     del A[:]#清空A
14     for each in B:
15         A.extend(each)#在A中插入已排好的数
16 
17 #插入排序
18 def insertion_sort(A):
19     for j in range(1, len(A)):
20         key = A[j]
21         i = j - 1
22         while i >= 0 and A[i] > key:
23             A[i + 1] = A[i]
24             i = i - 1
25             A[i + 1] = key
26 
27 A=[0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68]
28 bucket_sort(A)
29 print(A)
30 --------------------------------------------------------------
31 [[], [], [], [], [], [], [], [], [], []]
32 [[], [0.17, 0.12], [0.26, 0.21, 0.23], [0.39], [], [], [0.68], [0.78, 0.72], [], [0.94]]
33 [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

桶排序