参考 java 版的算法书, 使用 python 重写了一遍. 初学, 自己写的, 代码比较粗糙, 意思明白就好.
- import numpy as np
- import random
- #### 验证排序算法是否正确
- a=[x for x in range(35)]
- random.shuffle(a)
- print(a)
- rank(a) ###rank 为主函数
- print(a)
接下来是不同算法实现
- def exch(a,i,j):
- t=a[j]
- a[j]=a[i]
- a[i]=t
- #### 冒泡
- def rank(a):
- for i in range(len(a)-1):
- for j in range(i+1,len(a)):
- if a[i]>a[j]:
- exch(a,i,j)
- return a
- ##### 选择排序
- def rank(a):
- for i in range(len(a)-1):
- flag=i
- for j in range(i+1,len(a)):
- if a[flag]>a[j]:
- flag=j
- if flag!=i:
- exch(a,i,flag)
- return a
- ########### 插入排序
- def rank(a):
- for i in range(1,len(a)):
- j=i
- while j>0 and a[j]<a[j-1]:
- exch(a,j,j-1)
- j-=1
- return a
- ####### 归并排序
- def rank(a):
- rankhelper(a,0,len(a)-1)
- def rankhelper(a,lo,hi):
- if hi<=lo:
- return
- mid=int((hi-lo)/2+lo)
- rankhelper(a,lo,mid)
- rankhelper(a, mid + 1,hi)
- merg(a,lo,mid,hi)
- def merg(a,lo,mid,hi):
- i=lo
- j=mid+1
- result=np.ones(len(a),dtype=int) #### 建空数组会降低排序效率, 待改进
- result[lo:hi+1]=a[lo:hi+1]
- for k in range(lo,hi+1):
- if i>mid:
- a[k]=result[j]
- j+=1
- elif j>hi:
- a[k]=result[i]
- i+=1
- elif result[i]<result[j]:
- a[k]=result[i]
- i+=1
- else:
- a[k]=result[j]
- j+=1
- #### 快排
- def rank(a):
- random.shuffle(a)
- rankhelper(a,0,len(a)-1)
- def rankhelper(a,lo,hi):
- if lo>=hi:
- return
- j=partition(a,lo,hi)
- rankhelper(a,lo,j-1)
- rankhelper(a,j+1,hi)
- def partition(a,lo,hi):
- l1=lo+1
- l2=hi
- while True:
- while a[l1]<a[lo]:
- if l1==hi:
- break
- l1+=1
- while a[l2]>a[lo]:
- if l2==lo:
- break
- l2-=1
- if l1>=l2:
- break
- exch(a,l1,l2)
- exch(a,lo,l2)
- return l2
- ############# 堆排序
- def sink(a,k,l): ##### 最小堆
- while 2*k+1<=l:
- j=2*k+1
- if j<l and a[j]>a[j+1]:
- j=j+1
- if a[j]>a[k]:
- break
- exch(a,j,k)
- k=j
- def sink1(a,k,l): ### 最大堆
- while 2*k+1<=l:
- j=2*k+1
- if j<l and a[j]<a[j+1]:
- j+=1
- if a[j]<a[k]:
- break
- exch(a,j,k)
- k=j
- def rank(a):
- l=len(a)-1
- t=int(l/2)+1
- while t>=0:
- sink(a,t,l)
- t-=1
- while l>0:
- exch(a,l,0)
- l-=1
- sink(a,0,l)
来源: http://www.bubuko.com/infodetail-2850765.html