首页 > 代码库 > 算法导论之所有排序算法的Python实现

算法导论之所有排序算法的Python实现

最近一段时间学习了算法导论第二版书的第一部分和第二部分的内容,自己编写了其中排序相关的几乎全部算法,包括冒泡排序(bubble sort)、选择排序( selection sort)、插入排序(insertion sort)、希尔排序(shell sort)、归并排序(merge sort)、快速排序(quick sort)、计数排序(count sort)、基数排序(radix sort)、桶排序(bucket sort)、期望线性时间的第k个顺序统计量选择、最坏情况线性时间的中位数选择,并给出了习题8.4-5和9.3—8的算法思路及Python实现。其中大部分算法的基本原理不赘述,着重写了我对桶排序的理解,并详细分析了算法导论书中两道题目。堆排序因为涉及二叉树,会在下一部分数据结构的学习中实现。

初学Python,代码虽能准确运行,但是语言的使用方面可能不简洁或不准确,希望各位前辈指正。

1、冒泡排序(bubble sort) 

层层比较,不赘述,时间复杂度O(n^2)。

技术分享
 1 def bubble_sort(a_list):
 2     for last in range(len(a_list)-1,0,-1):
 3         exchange=0
 4         for i in range(0,last):
 5             if a_list[i]>a_list[i+1]:
 6                 temp=a_list[i]
 7                 a_list[i]=a_list[i+1]
 8                 a_list[i+1]=temp
 9                 exchange +=1
10         if exchange==0:
11             break
12 
13 测试:
14 a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
15 bubble_sort(a_list)
16 print(a_list)
17 输出:
18 [17, 20, 26, 31, 44, 54, 55, 77, 93]  
View Code 

2、选择排序( selection sort) 
该算法依次找出最大、次大……的元素并置于应属的位置,与冒泡排序的实现效果相同,只不过选择排序只是在每一轮选择结束后交换一次元素,减少了交换元素的次数。但比较次数没有减少,故时间复杂度依然是O(n^2)。

技术分享
 1 def selection_sort(a_list):
 2     for last in range(len(a_list)-1,0,-1):
 3         max=a_list[last]
 4         pos=last
 5         for i in range(last):
 6             if a_list[i]>max:
 7                 pos=i
 8                 max=a_list[i]
 9         a_list[pos]=a_list[last]
10         a_list[last]=max
11 
12 测试:     
13 a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
14 selection_sort(a_list)
15 print(a_list)
16 输出:
17 [17, 20, 26, 31, 44, 54, 55, 77, 93]
View Code

3、插入排序(insertion sort) 
倒着比较,将新元素插入已排序列的正确位置,采用递归,时间复杂度仍为O(n^2)。 

技术分享
 1 def insertion_sort(a_list):
 2     last=len(a_list)-1
 3     if last>0:
 4         list1=insertion_sort(a_list[:last])
 5         i=len(list1)-1
 6         temp=a_list[last]
 7         while i>=0:
 8             if temp<=list1[i]:
 9                 i-=1
10             else:
11                 break
12         for pos in range(last,i+1,-1):
13             a_list[pos]=list1[pos-1]
14         a_list[i+1]=temp
15         a_list[:i+1]=list1[:i+1]
16     return a_list  
17  
18 测试:
19 a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
20 print insertion_sort(a_list)
21 输出:
22 [17, 20, 26, 31, 44, 54, 55, 77, 93]
View Code

4、希尔排序(shell sort)

选取合适的gap值,将待排序元素数组中相隔gap个位置的元素归为一组,总共分成gap个组,组内排序(用插入排序实现),缩小gap,递归调用自身获得更新的排序结果。

 

技术分享
 1 def shell_sort(a_list,gap):
 2     if gap>0:
 3         for i in range(0,gap):
 4             for j in range(i+gap,len(a_list),gap):
 5                 k=j-gap
 6                 temp=a_list[j]
 7                 while a_list[k]>temp and k>=i:
 8                     a_list[k+gap]=a_list[k]
 9                     k-=gap
10                 a_list[k+gap]=temp
11         shell_sort(a_list,gap//2)
12 测试:
13 a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
14 shell_sort(a_list,4)
15 print(a_list)
16 输出:
17 [17, 20, 26, 31, 44, 54, 55, 77, 93]
View Code

5、归并排序(merge sort)

把待排序数组分成两部分分别排序,以递归调用自身实现,对已排好的两部分比较合并。

 

技术分享
 1 def merge_sort(a_list):
 2       if len(a_list)>1:
 3           split=len(a_list)//2
 4           left_list=merge_sort(a_list[0:split])
 5           right_list=merge_sort(a_list[split:len(a_list)])
 6           i=0
 7           j=0
 8           k=0
 9           while i <len(left_list) and j <len(right_list):
10                if left_list[i]<right_list[j]:
11                    a_list[k]=left_list[i]
12                    i+=1
13                    k+=1
14                else:
15                    a_list[k]=right_list[j]
16                    j+=1
17                    k+=1
18            if i==len(left_list):
19                a_list[k:]=right_list[j:]
20            if j==len(right_list):
21                a_list[k:]=left_list[i:]
22        return a_list
23  测试:
24 a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
25 print merge_sort(a_list)
26 输出:
27 [17, 20, 26, 31, 44, 54, 55, 77, 93]
View Code

6、快速排序(quick sort) 

采用分治思想,每次选取list中的第一个元素作为主元(pivot),通过比较找到其应属的位置,将原list划分为左右两个list,分别递归调用自身。

 

技术分享
 1   def quick_sort(a_list):
 2       if len(a_list)>1:
 3           pivot=a_list[0]
 4           i=0
 5           j=1
 6           while j<len(a_list):
 7               if a_list[j]<pivot:
 8                   i+=1
 9                   temp=a_list[i]
10                   a_list[i]=a_list[j]
11                   a_list[j]=temp
12               j+=1
13           a_list[0]=a_list[i]
14           a_list[i]=pivot
15           a_list=quick_sort(a_list[:i])+[a_list[i]]+quick_sort(a_list[i+1:])
16       return a_list
17  
18  测试:
19  a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
20  print quick_sort(a_list)
21  输出:
22  [17, 20, 26, 31, 44, 54, 55, 77, 93]
View Code

 

下面附上随机化快排中随机划分的部分Python代码:

技术分享
 1 import random
 2 def random_partition(a_list):
 3     p=random.randint(0,len(a_list)-1)
 4     pivot=a_list[p]
 5     a_list[p]=a_list[0]
 6     a_list[0]=pivot
 7     i=0
 8     j=1
 9     while j<len(a_list):
10         if a_list[j]<pivot:
11             i+=1
12             a_list[i],a_list[j]=a_list[j],a_list[i]
13         j+=1
14     a_list[0],a_list[i]=a_list[i],a_list[0]
15     return (pivot,i+1,a_list[:i],a_list[i+1:])
16 
17 测试: 
18 a_list=[2,4,13,5,8,6,14,7]
19 pivot,i,list_left,list_right=random_partition(a_list)
20 print (pivot,i,list_left,list_right)
21 输出:
22 (13, 7, [7, 4, 2, 5, 8, 6], [14])
View Code

7、计数排序(count sort) 
不是比较排序类算法,没有Ω(nlogn)时间复杂度限制,但要求待排序元素为非负整数。选择合适的待排序数的数值上限k,创建大小为k的list C,待排元素的数值作为C的index,在C[index]里记录该元素出现的次数,把C中某一index前的所有元素求和即为index对应的待排元素应属的位置。线性时间复杂度。  

 

技术分享
 1 def count_sort(a_list,k):
 2     B=[None]*len(a_list)  # ordered list
 3     C=[0]*k     # helper list to count
 4     for i in a_list:
 5         C[i]+=1
 6     for j in range(1,k):
 7         C[j]=C[j-1]+C[j]
 8     for p in range(len(a_list)-1,-1,-1):
 9         B[C[a_list[p]]-1]=a_list[p]      # the index of a list starts from 0, not 1
10         C[a_list[p]]-=1
11     return B
12 
13 a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20, 26, 93]
14 print count_sort(a_list,100)
View Code

 

8、基数排序(radix sort) 
基本思想是,对于n个r进制k位数进行排序,采用稳定排序算法,先依低位排序再依高位排序,以此保证依高位排序时,相同高位的数可保持其依低位已排好的次序。时间复杂度为O(k(n+r))。 
下面代码以十进制数的排序为例。但是代码中的两个问题我没有想明白,如Question1和Question2描述,希望各位前辈指点~

 

技术分享
 1 def radix_sort(a_list,k):
 2     B=[0]*len(a_list)
 3     for j in range(1,k+1):
 4         C=[0]*10            # helper list to count
 5         # A=[(i%10**j)//(10**(j-1))  for i in a_list]  # Question1: why is this way wrong to def A?
 6         A=[]
 7         for t in a_list:
 8             A.append((t%10**j)//(10**(j-1)))   
 9         for i in A:
10             C[i]+=1
11         for q in range(1,10):
12             C[q]=C[q-1]+C[q]
13         for p in range(len(A)-1,-1,-1):
14             B[C[A[p]]-1]=a_list[p]      # the index of a list starts from 0, not 1
15             C[A[p]]-=1
16         a_list=B
17         B=[0]*len(a_list)           # Question2: why must B set to be 0 here ????
18     return a_list
19 
20 a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20, 26, 93]
21 print radix_sort(a_list,2)
View Code

 

9、桶排序(bucket sort) 
桶排序的原始定义针对(0,1)范围内均匀分布的数,下面代码也是针对这种情况编写的。

 

技术分享
 1 from insertion_sort import insertion_sort
 2 import random
 3 def bucket_sort(a_list):
 4     bucket=[[] for i in range(len(a_list))]   # [[]]*len(list) is shallow copy, wrong
 5     for i in a_list:
 6         if i== 1:
 7             i= 0.99
 8         bucket[int(i*len(a_list))].append(i)
 9     a_list=[]
10     for j in bucket:
11         a_list=a_list+insertion_sort(j)
12     return a_list
13 测试: 
14 a_list=[random.uniform(0,1) for i in range(13)]
15 print before sort: \n %s % a_list
16 print after sort: \n %s  % bucket_sort(a_list)
17 输出:
18 before sort: 
19  [0.6017131497978297, 0.5257088814737517, 0.5308222308002468, 0.9233128021687357, 0.8701655171999804, 0.5526799446055798, 0.11875967581091884, 0.9175286740805743, 0.8919451407674414, 0.5193946279480275, 0.8656422841387905, 0.7077658852432671, 0.7646975175708084] 
20 after sort: 
21  [0.11875967581091884, 0.5193946279480275, 0.5257088814737517, 0.5308222308002468, 0.5526799446055798, 0.6017131497978297, 0.7077658852432671, 0.7646975175708084, 0.8656422841387905, 0.8701655171999804, 0.8919451407674414, 0.9175286740805743, 0.9233128021687357] 
View Code

 

桶排序算法的核心思想是通过合理设置桶,来满足每个桶所含元素数的平方和的期望与输入规模成线性关系,达到线性期望时间复杂度。 
直观上理解,我认为就是对分布较密的数据区域多划分些桶,对数据分布稀疏的区域少划分桶,以达到平均每个桶内分配常数个元素(原始定义里分成n个桶时每个桶平均分配1个元素)。对一般情况可采取的办法是,针对输入序列超出(0,1)范围的情况,可通过归一操作保证待排成数据在(0,1)范围内;针对输入序列非均匀分布的情况,可通过某种映射 f 将待排序列映射为均匀分布。 
以算法导论第二版的习题8.4-5来说明使用该算法的更一般的情况。

Ex8.4-5 一个随机变量X的概率分布函数P(x)定义为 P(x)=Pr{X<=x}。假设n个随机变量X1,X2,……,Xn 符合一个连续概率分布函数P,它可以在O(1)时间内计算。说明如何在线性期望时间内排序这n个数。 

若考虑采用桶排序算法,则桶的大小要依据X的分布来设置,设n个数分配n个桶,P(x)为[0,1]上的增函数,为了使每个桶中平均分配一个元素,只需将P(x) n均分(即[0,1] n均分),函数值对应的自变量即为桶划分的界。对于第i个桶,其范围( P?1((i?1)/n),P?1(i/n)) 。由于反函数运算不便,可直接将xi映射为P(xi)分析。则xi将被放入第?P(xi)?n?个桶中。

10、期望线性时间的第k个顺序统计量选择 
随机化选择主元,分治处理,返回第k个顺序统计量。代码中base的设置是为了更新当前处理list中的元素在原a_list中的位置。  

 

技术分享
 1 import random
 2 def random_partition(a_list):
 3     p=random.randint(0,len(a_list)-1)
 4     pivot=a_list[p]
 5     a_list[p]=a_list[0]
 6     a_list[0]=pivot
 7     i=0
 8     j=1
 9     while j<len(a_list):
10         if a_list[j]<pivot:
11             i+=1
12             a_list[i],a_list[j]=a_list[j],a_list[i]
13         j+=1
14     a_list[0],a_list[i]=a_list[i],a_list[0]
15     return (pivot,i+1,a_list[:i],a_list[i+1:])
16 
17 def random_select(a_list,k):
18     base =0
19     list_next=a_list
20     while list_next !=[]:
21         pivot,i,list_left,list_right= random_partition(list_next)
22         i=base+i
23         if i==k:
24             return pivot
25         elif i<k:
26             list_next=list_right
27             base =i
28         else:
29             list_next=list_left
30     return False
31 
32 测试: 
33 a_list=[2,4,13,5,8,6,14,7]
34 print random_select(a_list,5)
35 输出:
36 7   
View Code

 

11、最坏情况线性时间的中位数选择 
随机化算法可以获得良好的期望时间复杂度,却对最坏情况无能为力。该求取中位数(偶数指下中位数)的算法优化了主元的选择方法,将n个元素以每组5个元素分成?n/5?组,将每组的中位数组成新的list,递归调用自身,可保证得到的新list的中位数位于该n位有序序列的1/4~3/4位置范围(还可更精确),杜绝了随机化算法可能引起的最差情况,保证了线性时间复杂度。 
在下面的partition函数中,为了得到主元的index,注释行用了list.index()函数,但是该方法时间复杂度O(n),怎样修改才能使partition函数直接传入主元的index参数呢?求大神帮忙~

 

技术分享
 1 def insertion_sort(a_list):     
 2     last=len(a_list)-1
 3     if last>0:
 4         a_list1=insertion_sort(a_list[:last])
 5         i=len(a_list1)-1
 6         temp=a_list[last]
 7         while i>=0:
 8             if temp<=a_list1[i]:
 9                 i-=1
10             else:
11                 break
12         for pos in range(last,i+1,-1):
13             a_list[pos]=a_list1[pos-1]
14         a_list[i+1]=temp
15         a_list[:i+1]=a_list1[:i+1]
16     return a_list   
17 
18 def partition(a_list,key):  
19     p=a_list.index(key)      #Question: such an enbarrasing thing to find the key from a_list, how to do?
20     pivot=a_list[p]
21     a_list[p]=a_list[0]
22     a_list[0]=pivot
23     i=0
24     j=1
25     while j<len(a_list):
26         if a_list[j]<pivot:
27             i+=1
28             a_list[i],a_list[j]=a_list[j],a_list[i]
29         j+=1
30     a_list[0],a_list[i]=a_list[i],a_list[0]
31     return (i+1,a_list[:i],a_list[i+1:])
32 
33 
34 def mid_select(a_list):
35     if len(a_list)>5:
36         k=(len(a_list)+1)//2
37         a_list_next=a_list[:]
38         base=0
39         while a_list_next !=[]:
40             a_list_mid =[]
41             for i in range(len(a_list_next)//5):  
42                 a_list_part=a_list_next[5*i:5*(i+1)]
43                 a_list_order=insertion_sort(a_list_part)
44                 mid_part=a_list_order[2]
45                 a_list_mid.append(mid_part)
46             if len(a_list_next)%5 !=0:
47                 a_list_part=a_list_next[5*(len(a_list_next)//5):]
48                 a_list_order=insertion_sort(a_list_part)
49                 mid_part =a_list_order[(len(a_list_order)+1)//2-1]
50                 a_list_mid.append(mid_part)
51             mid= mid_select(a_list_mid)
52             i,a_list_left,a_list_right = partition(a_list_next,mid)  
53 
54             i =base +i                      # revise the index of mid in the original a_list
55             if i==k:
56                 return mid 
57             elif i <k:
58                 a_list_next=a_list_right
59                 base =i
60             else:
61                 a_list_next=a_list_left
62         return False
63     else:
64         a_list_order=insertion_sort(a_list)
65         return a_list_order[(len(a_list)+1)//2-1]
66 
67 
68 a_list=[2,54,26,4,13,5,8,14,7,93,6,17,77,31,44,55,20,26,93]
69 
70 print (mid_select(a_list))
71  
View Code

 

 

算法导论第二版书的习题9.3-8也用到了类似的思想。下分析。 
EX 9.3-8 设x[1..n]和Y[1..n]为两个数组,每个都包含n个已排好序的数。给出一个求数组X和Y中所有2n个元素的中位数的O(logn)时间的算法。 
看到O(logn)时间复杂度,首先想到分治思想的T(n)=T(n/2)+O(1)模式,那么如何才能通过常数次比较(最好一次),直接排除一部分不可能是中位数的元素呢(这部分元素的数量与n成线性关系即可)?首先最直观的考虑这部分元素数量为n/2,于是想到比较X和Y的中位数(偶数指下中位数),索引为mid,如果X[mid]=Y[mid],则X[mid](Y[mid])就是该2n个元素的中位数;如果X[mid]<Y[mid],则若将X和Y这2n个元素排序,Y[mid]必然排在第n个元素之后(反证法可得),同理 X[mid]必然排在前n个元素,因此 X[mid]之前的元素和Y[mid]之后的元素可以直接扔掉,因为它们肯定不是中位数。于是保留一半的元素递归调用自身。算法思路理清。 
但是还有一个问题,当n为偶数时,取的下中位数进行比较,若二者不等,则下一次处理的两数组长度不等,遇到困难。因此n为偶数时,我对舍弃后一半元素的数组保留至其中位数的后一位,保证了算法的正常递归。代码如下。

 

技术分享
 1 import random
 2 def mid_array_938(list_a,list_b):
 3     if len(list_a) >2:  
 4         len_mid=(len(list_a)+1)//2
 5         mid_a= list_a[len_mid-1]
 6         mid_b= list_b[len_mid-1]
 7         if mid_a == mid_b:
 8             return mid_a
 9         elif mid_a< mid_b:
10             if len(list_a)%2==0:
11                 return mid_array_938(list_a[len_mid-1:],list_b[:len_mid+1])
12             else:
13                 return mid_array_938(list_a[len_mid-1:],list_b[:len_mid])
14         else:
15             if len(list_a)%2==0:
16                 return mid_array_938(list_a[:len_mid+1],list_b[len_mid-1:])
17             else:
18                 return mid_array_938(list_a[:len_mid],list_b[len_mid-1:])
19     else:
20         list_ab=list_a + list_b
21         list_ab=insertion_sort(list_ab)
22         return list_ab[(len(list_ab)+1)//2-1]
23 
24 
25 def insertion_sort(a_list):
26     last=len(a_list)-1
27     if last>0:
28         list1=insertion_sort(a_list[:last])
29         i=len(list1)-1
30         temp=a_list[last]
31         while i>=0:
32             if temp<=list1[i]:
33                 i-=1
34             else:
35                 break
36         for pos in range(last,i+1,-1):
37             a_list[pos]=list1[pos-1]
38         a_list[i+1]=temp
39         a_list[:i+1]=list1[:i+1]
40     return a_list   
41 
42 测试:
43 list_a=[1,4,6,9,13,19,35,52]
44 list_b=[2,3,15,18,19,20,43,45]
45 print mid_array_938(list_a,list_b)      
46 输出:
47 15
View Code

算法导论之所有排序算法的Python实现