python排序实现及性能分析
程序员文章站
2022-07-23 23:37:35
我自己主要工作为后台开发，所以算法使用不多，最近在看到https://visualgo.net/en网站关于排序算法的动态实现，自己尝试用python实现各类算法，代码如下...
我自己主要工作为后台开发，所以算法使用不多，最近在看到https://visualgo.net/en网站关于排序算法的动态实现，自己尝试用python实现各类算法，代码如下
#coding:utf8
from random import randint
import random
import numpy as np
def create_list(lens):
return [randint(0,10000) for i in range(lens)]
def bubble_sort(nums):
lens = len(nums)
count = 0
for j in range(lens):
count += 1
for i in range(lens-count):
if nums[i] > nums[i+1]:
nums[i],nums[i+1] = nums[i+1],nums[i]
return nums
def select_sort(nums):
lens = len(nums)
count = -1
for i in range(1,lens):
count += 1
for j in range(count,lens):
if nums[count] > nums[j]:
nums[count],nums[j] = nums[j],nums[count]
return nums
def insert_sort(nums):
lens = len(nums)
count = 0
for i in range(lens):
count += 1
for j in range(count,lens):
if nums[j] < nums[i]:
nums[j],nums[i]=nums[i],nums[j]
return nums
def merge_sort(nums):
lens = len(nums)
count = lens
n = 2
def sort_two_list(list1,list2):
len1 = len(list1)
len2 = len(list2)
list3 = []
i,j=0,0
while i nums[i+1]:
nums[i],nums[i+1] = nums[i+1],nums[i]
while n<=lens:
list3 = []
for j in range(0,lens,2*n):
list3 += sort_two_list(nums[j:j+n],nums[j+n:j+2*n])
nums = list3
n += n
return nums
def quick_sort(nums):
lens = len(nums)
if lens <= 1:
return nums
else:
pivot = (nums[0] + nums[lens - 1] + nums[lens/2])/3
return quick_sort([x for x in nums[1:] if x < pivot]) + \
[pivot] + \
quick_sort([x for x in nums[1:] if x >= pivot])
def random_quick_sort(nums):
lens = len(nums)
if lens <= 1:
return nums
else:
pivot = random.sample(nums,1)[0]
return quick_sort([x for x in nums[1:] if x < pivot]) + \
[pivot] + \
quick_sort([x for x in nums[1:] if x >= pivot])
def counting_sort(nums):
'''适用于较小的重复的整数排序
这里限定为0-20'''
#检测是否是适合此方法的数组
if max(nums) >20 or min(nums)<0:
return 'this sort only suit for small int nums'
nums_check = [int(i) for i in nums ]
if nums_check != nums:
return 'this sort only suit for small int nums'
d = {}
for i in nums:
if i in d:
d[i] +=1
else:
d[i] = 1
list1 = []
print d
for i in range(0,21):
list1 += [i for x in range(d.get(i,0))]
return list1
def radix_sort(nums):
#判断是否为正整数
nums_check = [int(i) for i in nums if i >=0 ]
if nums_check != nums:
return 'err param'
lens = len(nums)
max_num = nums[0]
#寻找最大数字长度
for i in range(1,lens-1):
if max_num
15506 function calls in 12.800 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 :0(len)
15501 0.482 0.000 0.482 0.000 :0(range)
1 0.001 0.001 0.001 0.001 :0(setprofile)
1 0.000 0.000 12.799 12.799 :1()
1 12.316 12.316 12.799 12.799 as.py:7(bubble_sort)
1 0.000 0.000 12.800 12.800 profile:0(bubble_sort(nums))
0 0.000 0.000 profile:0(profiler)
15505 function calls in 5.592 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 :0(len)
15500 0.588 0.000 0.588 0.000 :0(range)
1 0.000 0.000 0.000 0.000 :0(setprofile)
1 0.000 0.000 5.592 5.592 :1()
1 5.003 5.003 5.591 5.591 as.py:17(select_sort)
0 0.000 0.000 profile:0(profiler)
1 0.000 0.000 5.592 5.592 profile:0(select_sort(nums))
15506 function calls in 6.426 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 :0(len)
15501 0.950 0.000 0.950 0.000 :0(range)
1 0.000 0.000 0.000 0.000 :0(setprofile)
1 0.000 0.000 6.426 6.426 :1()
1 5.476 5.476 6.426 6.426 as.py:27(insert_sort)
1 0.000 0.000 6.426 6.426 profile:0(insert_sort(nums))
0 0.000 0.000 profile:0(profiler)
130189 function calls in 0.188 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
106905 0.056 0.000 0.056 0.000 :0(append)
15511 0.011 0.000 0.011 0.000 :0(len)
14 0.000 0.000 0.000 0.000 :0(range)
1 0.000 0.000 0.000 0.000 :0(setprofile)
1 0.000 0.000 0.188 0.188 :1()
1 0.020 0.020 0.188 0.188 as.py:37(merge_sort)
7755 0.101 0.000 0.168 0.000 as.py:41(sort_two_list)
1 0.000 0.000 0.188 0.188 profile:0(merge_sort(nums))
0 0.000 0.000 profile:0(profiler)
46821 function calls (23413 primitive calls) in 0.083 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
23409 0.013 0.000 0.013 0.000 :0(len)
1 0.000 0.000 0.000 0.000 :0(setprofile)
1 0.000 0.000 0.083 0.083 :1()
23409/1 0.070 0.000 0.083 0.083 as.py:67(quick_sort)
0 0.000 0.000 profile:0(profiler)
1 0.000 0.000 0.083 0.083 profile:0(quick_sort(nums))
46638 function calls (23326 primitive calls) in 0.081 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 :0(add)
1 0.000 0.000 0.000 0.000 :0(hasattr)
23316 0.013 0.000 0.013 0.000 :0(len)
1 0.000 0.000 0.000 0.000 :0(random)
1 0.000 0.000 0.000 0.000 :0(setprofile)
1 0.000 0.000 0.081 0.081 :1()
23314/2 0.067 0.000 0.079 0.040 as.py:67(quick_sort)
1 0.002 0.002 0.081 0.081 as.py:77(random_quick_sort)
0 0.000 0.000 profile:0(profiler)
1 0.000 0.000 0.081 0.081 profile:0(random_quick_sort(nums))
1 0.000 0.000 0.000 0.000 random.py:293(sample)
77507 function calls in 0.112 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
77500 0.044 0.000 0.044 0.000 :0(append)
2 0.000 0.000 0.000 0.000 :0(len)
1 0.000 0.000 0.000 0.000 :0(range)
1 0.000 0.000 0.000 0.000 :0(setprofile)
1 0.000 0.000 0.112 0.112 :1()
1 0.067 0.067 0.112 0.112 as.py:109(radix_sort)
0 0.000 0.000 profile:0(profiler)
1 0.000 0.000 0.112 0.112 profile:0(radix_sort(nums))
[Finished in 26.2s]
通过profile查看各函数的运行时间，可以看到radix_sort 、random_quick_sort、quick_sort、merge_sort随排序数字的增加时间并没有明显增加，对时间复杂度较好。
关于各个算法的时间复杂度，我想很容易通过代码看出来。