需要的库：

import sys

import time

sys.setrecursionlimit(1000000) #手动设置递归深度,如果不设置,当数字取多一些时,快速排序,归并函数因为利用了递归, 会溢出,报错

首先先建立一个函数得出1000个大小在（0，9999）之间的随机数

# 随机生成0-10000之间的数值

def getrandata(num):

a = []

i = 0

while i <= num:

a.append(random.randint(0, 9999))

i += 1

print(a)

return a

a = getrandata(1000)

1、冒泡排序

冒泡排序是最简单的排序之一了，其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样，因此而得名。举个栗子，对5,3,8,6,4这个无序序列进行冒泡排序。首先从后向前冒泡，4和6比较，把4交换到前面，序列变成5,3,8,4,6。同理4和8交换，变成5,3,4,8,6,3和4无需交换。5和3交换，变成3,5,4,8,6,3.这样一次冒泡就完了，把最小的数3排到最前面了。对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)。

# 冒泡排序 时间复杂度O(n^2)

'''

算法思路: 每次从最后开始往前面滚,相邻元素两两比较,小元素交换到前面,每一轮把最小到元素上浮至第一个位置

第一轮,n个数, 比较 n-1 次,得到最小数,放在第一位,

第二轮,比较剩余 n-1 个数, 比较 n-2 次, 得到第二小的数, 放在第二位

以此类推

最后总比较次数:1 + 2 + 3 + 。。。 + (n-1) = (1+n-1)*(n-1)/2 = n(n-1)/2

'''

def maopao(a):

start_time = time.time()*1000

x = len(a)

for i in range(x-1):

for j in range(i,x-1)[::-1]: # 每轮的比较数列为[第i个, 最后],因为每一轮已经将最小第数放到最前面

if a[j+1] < a[j]:

a[j], a[j+1] = a[j+1], a[j]

use_time = time.time()*1000 - start_time

print('1 冒泡排序: ',a,'\n', '使用时间: ', '%s ms' % use_time)

maopao(a)

结果：排序完的的结果太长，不列出来了， 使用时间: 155.197021484375 ms

2、插入排序

插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。相信大家都有过打扑克牌的经历，特别是牌数较大的。在分牌时可能要整理自己的牌，牌多的时候怎么整理呢？就是拿到一张牌，找到一个合适的位置插入。这个原理其实和插入排序是一样的。举个栗子，对5,3,8,6,4这个无序序列进行简单插入排序，首先假设第一个数的位置时正确的，想一下在拿到第一张牌的时候，没必要整理。然后3要插到5前面，把5后移一位，变成3,5,8,6,4.想一下整理牌的时候应该也是这样吧。然后8不用动，6插在8前面，8后移一位，4插在5前面，从5开始都向后移一位。注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O(n^2)。

def insertSort(a):

start_time = time.time()*1000

for i in range(1, len(a)):

j = i

while j>0 and a[j-1] > a[i]:

j -= 1

a.insert(j,a[i])

a.pop(i+1)

use_time = time.time()*1000 - start_time

print('2 插入排序: ',a, '\n', '使用时间: ', '%s ms' % use_time)

insertSort(a)

使用时间: 52.470947265625 ms

3、快速排序

快速排序一听名字就觉得很高端，在实际应用当中快速排序确实也是表现最好的排序算 法。快速排序虽然高端，但其实其思想是来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。

# 快速排序 时间复杂度O(nlogn)

def quickSort(a):

start_time = time.time()*1000

def quick(a):

if len(a) <= 1:

return a

x = len(a)

i = 0

flag = a[i]

for j in range(1,x):

if a[j]< flag:

flag=a[j]

a.insert(0,flag)

a.pop(j+1)

i += 1

a1 = a[:i]

a2 = a[i+1:]

a = quick(a1)

a.append(flag)

a.extend(quick(a2))

return a

use_time = time.time()*1000 - start_time

print("3 快速排序: ", quick(a))

print(" 使用时间: %s ms" % use_time)

quickSort(a)

使用时间: 0.0009765625 ms

4、选择排序

选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。举个栗子，对5,3,8,6,4这个无序序列进行简单选择排序，首先要选择5以外的最小数来和5交换，也就是选择3和5交换，一次排序后就变成了3,5,8,6,4.对剩下的序列一次进行选择和交换，最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。选择排序的时间复杂度为O(n^2)。

# 选择排序 时间复杂度O(n^2) 选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。

# 但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。

def selectSort(a):

start_time = time.time()*1000

x = len(a)

for i in range(x-1):

flag = a[i]

tmp = i

for j in range(i+1,x):

if flag > a[j]:

flag = a[j]

tmp = j

a[i],a[tmp] = a[tmp],a[i]

use_time = time.time()*1000 - start_time

print("4 选择排序: ", a, '\n', "使用时间: %s ms" % use_time)

# 时间复杂度也为 O(n^2)

selectSort(a)

使用时间: 40.88720703125 ms

5、希尔排序

# 希尔排序 如果待排序列是正序时，时间复杂度是O(n), 平均情况O(n^1.3)

# 希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。简单的插入排序中，如果待排序列是正序时，时间复杂度是O(n)，

# 如果序列是基本有序的，使用直接插入排序效率就非常高。希尔排序就利用了这个特点。

# 基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序（也可以其他方式）。

def shellSort(a):

start_time = time.time()*1000

x = len(a)

group = int(x/2)

while group > 0:

for i in range(group):

a1 = a[i::group]

for j in range(1,len(a1)):

k = j # 该位置数字 原始位置在 i+group*j

while k>0 and a1[k-1] > a1[j]:

k -= 1

a.insert(i+group*k,a1[j])

a.pop(i+group*j+1)

group = int(group/2)

use_time = time.time()*1000 - start_time

print("5 希尔排序: ", a, '\n', "使用时间: %s ms" % use_time)

shellSort(a)

使用时间: 11.671630859375 ms

6、计数排序

# 计数排序的时间复杂度和空间复杂度为O(n) 或时间复杂度O(n+k),空间复杂度为O(k) k为整数度范围

# 计数排序对输入的数据有附加的限制条件：

# 1、输入的线性表的元素属于有限偏序集S；

# 2、设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。

# 在这两个条件下，计数排序的复杂性为O(n)。

def countSort(a):

start_time = time.time()*1000

b = [0 for i in range(10001)] #最小值最好为0 ,否则,算法需要改进, 如再建一个列表,利用list[-1]这样代表负数

for i in a:

b[i] += 1

a = []

for i in range(10000):

while b[i] >0:

a.append(i)

b[i] -= 1

use_time = time.time()*1000 - start_time

print("6 计数排序: ", a, "\n", "使用时间: %s ms" % use_time)

countSort(a)

使用时间: 1.761962890625 ms

7、桶排序

# 桶排序 总结：桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，

# 最好的时间复杂度达到O(N)。当然桶排序的空间复杂度为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。

# 此外，桶排序是稳定的。

'''

例如要对大小为[1..1000]范围内的n个整数A[1..n]排序，可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，

集合B[2]存储(10..20]的整数，……集合B[i]存储((i-1)*10, i*10]的整数，i = 1,2,..100。总共有100个桶。然后对A[1..n]从头到尾扫描一遍，

把每个A[i]放入对应的桶B[j]中。 然后再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任何排序法都可以。

最后依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。

'''

# 极限情况下一个数一个桶,这样就为计数排序,时间复杂度O(n)

# 以下为先分桶,再插入排序的方式,默认最大数为10000

def bucketSort(a,bucket_num):

start_time = time.time()*1000

sep = int(10000/bucket_num)+1

b = []

for i in range(1,bucket_num+1):

c = []

for j in a:

if j >= sep * (i-1) and j < i *sep:

c.append(j)

x = len(c)

for j in range(1,x):

k = j

while k >0 and c[k-1]>c[j]:

k -= 1

c.insert(k,c[j])

c.pop(j+1)

b.extend(c)

use_time = time.time()*1000 - start_time

print("7 桶排序 : ", b, "\n", "使用时间: %s ms" % use_time)

bucketSort(a,10)

使用时间: 6.691162109375 ms

8、归并排序

# 归并排序 时间复杂度为 O(nlogn)

# 将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；

# 将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。

def mergeSort(a):

start_time = time.time()*1000

def Sort(left, right):

left_right = []

while len(left) > 0 and len(right) > 0:

if left[0] < right[0]:

left_right.append(left[0])

left.pop(0)

else:

left_right.append(right[0])

right.pop(0)

if len(left) > 0:

left_right.extend(left)

else:

left_right.extend(right)

return left_right

def merge(a):

if len(a) <=1:

return a

x = int(len(a)/2)

left = merge(a[:x])

right = merge(a[x:])

return Sort(left, right)

a = merge(a)

use_time = time.time()*1000 - start_time

print("8 归并排序: ", a, "\n", "使用时间: %s ms" % use_time)

mergeSort(a)

使用时间: 7.035888671875 ms

9、基数排序

# 基数排序 基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。

# 所谓的多关键字排序就是有多个优先级不同的关键字。比如说成绩的排序，如果两个人总分相同，则语文高的排在前面，语文成绩也相同则数学高的排在前面。。。

# 如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级一次增加。

# 基数排序是通过多次的收分配和收集来实现的，关键字优先级低的先进行分配和收集。

def radixSort(a,maxs):#为了速度,确定就不用max函数找出最大数多少位的,人工输入最大位数

start_time = time.time()*1000

for g in range(4):

x = [[] for i in range(10)]

for i in a:

radix = int(i/(10**g))%10

x[radix].append(i)

a = []

for i in x:

for j in i:

a.append(j)

use_time = time.time()*1000 - start_time

print("9 基数排序: ", a, "\n", "使用时间: %s ms" % use_time)

radixSort(a,4)

使用时间: 3.02294921875 ms

10、堆排序

# 堆排序与快速排序，归并排序一样都是时间复杂度为O(n*logn)的几种常见排序方法

# 按定义，堆中每次都只能删除第0个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。

# 我选择将第一个元素重列表删除,那么第二个元素上升至第一个,再开始

# 调整时先在左右儿子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。

def heapSort(a):

start_time = time.time()*1000

b = []

x = len(a)

while x > 1:

for i in range(1,x)[::-1]:

j = int((i-1)/2)

if a[i] < a[j]:

a[i], a[j] = a[j], a[i]

b.append(a[0])

a.pop(0)

x -= 1

b.append(a[0])

use_time = time.time()*1000 - start_time

print("10 堆排序: ", b, "\n", "使用时间: %s ms" % use_time)

heapSort(a)

使用时间: 193.88818359375 ms

11、python的sorted函数

# 顺便测验一下python 自带的排序函数sorted的使用时间

def selfSort(a):

start_time = time.time() * 1000

a = sorted(a)

use_time = time.time() * 1000 - start_time

print("11 python的排序函数: ", a, "\n", "使用时间: %s ms" % use_time)

selfSort(a)

使用时间: 0.223876953125 ms

总结

冒泡排序、选择排序、插入排序三种简单的排序及其变种快速排序、堆排序、希尔排序三种比较高效的排序；

基于分治递归思想的归并排序还有计数排序、桶排序、基数排序三种线性排序；

可以知道排序算法要么简单有效，要么是利用简单排序的特点加以改进，要么是以空间换取时间在特定情况下的高效排序

参考：

http://www.imooc.com/article/8633