首页 > 代码库 > Python之基本排序算法的实现
Python之基本排序算法的实现
1 import cProfile 2 import random 3 class SortAlgorithm: 4 def __init__(self,unsortedlist=[]): 5 self.unsortedlist = unsortedlist or [i for i in random.sample(range(10000),100)] 6 self.length = len(self.unsortedlist) 7 8 def bubble_sort(self): 9 ‘‘‘ 10 冒泡排序:从第一个元素开始,每每相邻的两个元素进行比较,若前者比后者大则交换位置。最后两个相邻元素比较完成后,最大的元素形成, 11 然后再次从头开始进行比较,若元素个数为n个,则总共需要进行n-1轮比较就可完成排序。一般情况下算法复杂度是平方级。 12 ‘‘‘ 13 for i in range(self.length-1): 14 for j in range(self.length-i-1): 15 if self.unsortedlist[j]>self.unsortedlist[j+1]: 16 self.unsortedlist[j],self.unsortedlist[j+1] = self.unsortedlist[j+1],self.unsortedlist[j] 17 18 return self.unsortedlist 19 20 def selection_sort(self): 21 ‘‘‘ 22 选择排序:从未排序的序列中找到一个最小的元素,放到第一位,再从剩余未排序的序列中找到最小的元素,放到第二位,依此类推,直到所有元素都已排序完毕。 23 假设序列元素总共n个,则我们需要找n-1轮,就可以使该序列排好序。时间复杂度是平方级。 24 ‘‘‘ 25 for i in range(self.length-1): 26 for j in range(i+1,self.length): 27 if self.unsortedlist[i]>self.unsortedlist[j]: 28 self.unsortedlist[i],self.unsortedlist[j] = self.unsortedlist[j],self.unsortedlist[i] 29 return self.unsortedlist 30 31 def insert_sort(self): 32 ‘‘‘ 33 插入排序:把序列的第一个元素当成已排序列表中的元素,接着从第二个元素开始,与已排序列表中的元素一一比较,并放到合适的位置。假设有n个元素需要排序,则需要n-1轮插入就可排好序。 34 时间复杂度为平方级。 35 ‘‘‘ 36 for i in range(1,self.length): 37 for j in range(i): 38 if self.unsortedlist[i]<self.unsortedlist[j]: 39 self.unsortedlist.insert(j,self.unsortedlist.pop(i)) 40 break 41 return self.unsortedlist 42 43 def merge_sort(self,lists=None,divid=None): 44 ‘‘‘ 45 归并排序:归并排序是约翰·冯·诺伊曼发明,是一种典型的分治法(Divide and Conquer),把一个无序列表一分为二,对每个子序列再一分为二,继续下去,直到无法再进行划分为止。 46 然后,就开始合并的过程,对每个子序列和另外一个子序列的元素进行比较,依次把小元素放入结果序列中进行合并,最终完成归并排序。时间复杂度是线性对数级。 47 ‘‘‘ 48 lists = lists or self.unsortedlist 49 if len(lists)<=1: 50 return lists 51 divid = divid or len(lists)//2 52 left_list = self.merge_sort(lists=lists[:divid]) 53 right_list = self.merge_sort(lists=lists[divid:]) 54 55 result = [] 56 l,r=0,0 57 while len(left_list)>l and len(right_list)>r: 58 if left_list[l]<right_list[r]: 59 result.append(left_list[l]) 60 l+=1 61 else: 62 result.append(right_list[r]) 63 r+=1 64 result+=left_list[l:] 65 result+=right_list[r:] 66 return result 67 68 def quick_sort(self,lists=None): 69 ‘‘‘ 70 快速排序:快速排序也是一种分治思想,基本思想是先随便在无序列表中找一个元素,以这个元素为基准,其他所有元素都跟该元素比,比该元素小的成为一个子序列,比该元素大的成为另一个子序列, 71 这样其中一部分数据都比另一部分小,然后再按照此方法分别进行快速排序,最终达到排序效果。时间复杂度一般为线性对数级。 72 ‘‘‘ 73 lists = lists or self.unsortedlist 74 if len(lists)<=1: 75 return lists 76 small = [] 77 large = [] 78 divid = lists.pop(0) 79 for each in lists: 80 if each<divid: 81 small.append(each) 82 else: 83 large.append(each) 84 self.quick_sort(small) 85 self.quick_sort(large) 86 return self.quick_sort(small)+[divid]+self.quick_sort(large) 87 88 89 if __name__==‘__main__‘: 90 sort = SortAlgorithm() 91 #result = sort.bubble_sort() 92 #result = sort.selection_sort() 93 #result = sort.insert_sort() 94 #result = sort.merge_sort() 95 result = sort.quick_sort() 96 print(result)
Python之基本排序算法的实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。