排序算法python实现

参考java版的算法书，使用python重写了一遍。初学，自己写的，代码比较粗糙，意思明白就好。末尾补上了字符串排序和python封装好的排序函数用法

1 import numpy as np
2 import random
3 ####验证排序算法是否正确
4 a=[x for x in range(35)]
5 random.shuffle(a)
6 print(a)
7 rank(a)  ###rank为主函数
8 print(a)

接下来是不同算法实现

  1 def exch(a,i,j):
  2         t=a[j]
  3         a[j]=a[i]
  4         a[i]=t
  5 ####冒泡
  6 def rank(a):
  7     for i in range(len(a)-1):
  8         for j in range(i+1,len(a)):
  9             if a[i]>a[j]:
 10                 exch(a,i,j)
 11     return a
 12 #####选择排序
 13 def rank(a):
 14     for i in range(len(a)-1):
 15         flag=i
 16         for j in range(i+1,len(a)):
 17             if a[flag]>a[j]:
 18                 flag=j
 19         if flag!=i:
 20            exch(a,i,flag)
 21     return a
 22 ###########插入排序
 23 def rank(a):
 24     for i in range(1,len(a)):
 25         j=i
 26         while j>0 and a[j]<a[j-1]:
 27             exch(a,j,j-1)
 28             j-=1
 29     return a
 30 
 31 #######归并排序
 32 def rank(a):
 33     rankhelper(a,0,len(a)-1)
 34 def rankhelper(a,lo,hi):
 35     if hi<=lo:
 36         return
 37     mid=int((hi-lo)/2+lo)
 38     rankhelper(a,lo,mid)
 39     rankhelper(a, mid + 1,hi)
 40     merg(a,lo,mid,hi)
 41 def merg(a,lo,mid,hi):
 42 
 43     i=lo
 44     j=mid+1
 45     result=np.ones(len(a),dtype=int)  ####建空数组会降低排序效率，待改进
 46     result[lo:hi+1]=a[lo:hi+1]
 47 
 48     for k in range(lo,hi+1):
 49         if i>mid:
 50             a[k]=result[j]
 51             j+=1
 52         elif j>hi:
 53             a[k]=result[i]
 54             i+=1
 55         elif result[i]<result[j]:
 56             a[k]=result[i]
 57             i+=1
 58         else:
 59             a[k]=result[j]
 60             j+=1
 61 
 62 ####快排
 63 def rank(a):
 64     random.shuffle(a)
 65     rankhelper(a,0,len(a)-1)
 66 def rankhelper(a,lo,hi):
 67     if lo>=hi:
 68         return
 69     j=partition(a,lo,hi)
 70     rankhelper(a,lo,j-1)
 71     rankhelper(a,j+1,hi)
 72 def partition(a,lo,hi):
 73     l1=lo+1
 74     l2=hi
 75     while True:
 76         while a[l1]<a[lo]:
 77             if l1==hi:
 78                 break
 79             l1+=1
 80         while a[l2]>a[lo]:
 81             if l2==lo:
 82                 break
 83             l2-=1
 84         if l1>=l2:
 85             break
 86         exch(a,l1,l2)
 87     exch(a,lo,l2)
 88     return l2
 89 
 90 #############堆排序

 95 def sink(a,k,l):   #####最小堆
 96     while 2*k+1<=l:
 97         j=2*k+1
 98         if j<l and a[j]>a[j+1]:
 99             j=j+1
100         if a[j]>a[k]:
101             break
102         exch(a,j,k)
103         k=j
104 def sink1(a,k,l):  ###最大堆
105     while 2*k+1<=l:
106         j=2*k+1
107         if j<l and a[j]<a[j+1]:
108             j+=1
109         if a[j]<a[k]:
110             break
111         exch(a,j,k)
112         k=j
113 def rank(a):
114     l=len(a)-1
115     t=int(l/2)+1
116     while t>=0:
117         sink(a,t,l)
118         t-=1
119     while l>0:
120         exch(a,l,0)
121         l-=1
122         sink(a,0,l)

字符串排序高位优先及低位优先。其中字符串排序可以和以上排序算法结合，比如和快排

 1 '''def rank(s):   #########低位优先
 2     n=len(s) ###字符串数量
 3     l=len(s[0])-1 ###长度
 4     temp=[0]*len(s)  ###临时数组
 5     while l>=0:
 6         count=[0]*257 ###计数数组
 7         for i in s:
 8             count[ord(i[l])+1]+=1   ###每个字符计数
 9         for j in range(256):
10             count[j+1]+=count[j]
11         for k in range(n):
12             temp[count[ord(s[k][l])]]=s[k]  ####将原数组按顺序呢放入到新数组中
13             count[ord(s[k][l])]+=1  #####顺序后移1
14         for t in range(n):
15             s[t]=temp[t]
16         l-=1'''
17 
18 ############高位优先排序
19 def rank(s):
20     rankhelper(s,0,len(s)-1,0)
21 
22 def rankhelper(s,lo,hi,d): ####引入count[1]即为长度为d的字符串数量，如果字符串长度相同，下一轮迭代count[0]==count[1]将不再递归下去
23     count=[0]*258
24     temp=[0]*len(s)
25     if lo>=hi:
26         return
27     for i in range(lo,hi+1):
28         count[chartAt(s[i],d)+2]+=1
29     for j in range(257):
30         count[j+1]+=count[j]
31     for k in range(lo,hi+1):
32         temp[count[chartAt(s[k],d)+1]]=s[k]
33         count[chartAt(s[k], d) + 1]+=1
34     for l in range(lo,hi+1):
35         s[l]=temp[l-lo]
36     for r in range(256):
37         rankhelper(s,lo+count[r],lo+count[r+1]-1,d+1)
38 
39 
40 def chartAt(s,d):
41     if d<len(s):
42         return ord(s[d])
43     else:
44         return -1
45 
46 s1='qwertyuiopasdfghjklzxcvbnm1234567890'
47 s=[]
48 for i in range(10):
49     #s.append(''.join(random.sample(s1,6)))  ###低位优先生成长度一致的字符
50     s.append(''.join(random.sample(s1,int(random.randint(2,8))))) ###高位优先自动生成字符串
51 print(s)
52 rank(s)
53 print(s)

之后就是封装好的函数sorted使用了 python3 取消了cmp，感觉不是很灵活，自定义函数有点麻烦 python3 3个参数，list（可迭代对象）key 函数定义，按值或按键，reverse 升序或降序

 1 import random
 2 
 3 ###s生成随机字典
 4 keys=[]
 5 for i in range(10):
 6     keys.append(random.randint(1,100))
 7 values=[]
 8 s1='qwertyuiopasdfghjklzxcvbnm1234567890'
 9 for j in range(10):
10     values.append(''.join(random.sample(s1,int(random.randint(2,5)))))
11 
12 list1={key:value for key,value in zip(keys,values)}
13 
14 print(list1)
15 ####排序主体
16 t1=sorted(list1) ###对键排序
17 t2=sorted(list1.values()) ##对值排序
18 t3=sorted(list1.items(),key=lambda x:x[0]) ###按键排序并返回字典
19 t4=sorted(list1.items(),key=lambda x:x[1]) ###按值排序并返回字典
20 print(t1)
21 print(t2)
22 print(t3)
23 print(t4)

排序算法python实现

推荐阅读