首页 > 代码库 > 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之基本排序算法的实现