选择排序
1 def selectSort(data):
2 num =
len(data)
3 for i
in range(num-1
):
4 min_index =
i
5 for j
in range(i+1
,num):
6 if data[j] <
data[min_index]:
7 min_index =
j
8 data[i], data[min_index] =
data[min_index], data[i]
9 return data
10 data = [5,6,3,2,1,65,2,0,8
,0]
11 result =
selectSort(data)
12 print(result)
冒泡排序
1 def bubbleSort(data):
2 n =
len(data)
3 for i
in range(n):
4 # Last i elements are already in place
5 for j
in range(0, n-i-1
):
6 if data[j] > data[j+1
] :
7 data[j], data[j+1] = data[j+1
], data[j]
8 return data
9 data = [5,6,3,2,1,65,2,0,8
,0]
10 result =
bubbleSort(data)
11 print(result)
插入排序
1 def insertSort(data):
2 num =
len(data)
3 for i
in range(1
,num):
4 key =
data[i]
5 for j
in range(i-1,-1,-1
):
6 if data[j] >
key:
7 data[j+1] =
data[j]
8 data[j] =
key
9 return data
10 data = [5,6,3,2,1,65,2,0,8
,0]
11 result =
insertSort(data)
12 print(result)
基数排序：计数排序和桶排序都属于非比较排序，时间复杂度为O(n)，
基数排序一般用于长度
同的元素组成的数组。首先按照最低有效数字进行排序，然后由低位向高位进行。
1 import random
2 def radixSort(data, bit):
3 for k
in range(bit):
#4轮排序
4 s=[[]
for i
in range(10
)]
5 for i
in data:
6 s[int(i/(10**k)
)].append(i)
7 data=[a
for b
in s
for a
in b]
8 return data
9 data=[random.randint(1,9999)
for i
in range(20
)]
10 result=radixSort(data ,4
)
11 print(result)
计数排序：
假设n个输入元素中每一个都是介于0到k之间的整数，此处k为某个整数。当k=O(n)时，计数排序的运行时间为Θ(n)。对每一个数的元素x，确定出小于x的元素个数。有了这一信息就可以把x直接放到最终输出数组中的位置上。
1 def countSort(data,num):
2 b=[0
for i
in range(num)]
3 c=[0
for i
in range(num+1
)]
4 for i
in data:
5 c[i]+=1
6 for i
in range(1
,len(c)):
7 c[i]=c[i-1]+
c[i]
8 for i
in data:
9 b[c[i]-1]=
i
10 c[i]-=1
11 return b
12
13
14 a=[random.randint(0,100)
for i
in range(100
)]
15 print(countSort(a,len(a)))
桶排序：
通排序不能排序小数，桶排序也叫计数排序，简单来说，就是将数据集里面所有元素按顺序列举出来，然后统计元素出现的次数。最后按顺序输出数据集里面的元素。
1 def bucketSort(nums):
2 max_num =
max(nums)
3 bucket = [0]*(max_num+1
)
4 for i
in nums:
5 bucket[i] += 1
6 sort_nums =
[]
7 for j
in range(len(bucket)):
8 if bucket[j] !=
0:
9 for y
in range(bucket[j]):
10 sort_nums.append(j)
11 return sort_nums
12 nums = [5,6,3,2,1,65,2,0,8
,0]
13 print(bucketSort(nums))
转载于:https://www.cnblogs.com/charlie7/p/11276409.html
