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随排序数字的增加时间并没有明显增加,对时间复杂度较好。
关于各个算法的时间复杂度,我想很容易通过代码看出来。