Python实现的几个常用排序算法实例
前段时间为准备百度面试恶补的东西，虽然最后还是被刷了，还是把那几天的“战利品”放点上来，算法一直是自己比较薄弱的地方，以后还要更加努力啊。
下面用Python实现了几个常用的排序，如快速排序，选择排序，以及二路并归排序等等。
#encoding=utf-8 importrandom fromcopyimportcopy
defdirectInsertSort(seq): """直接插入排序""" size=len(seq) foriinrange(1,size): tmp,j=seq[i],i whilej>0andtmp<seq[j-1]: seq[j],j=seq[j-1],j-1 seq[j]=tmp returnseq
defdirectSelectSort(seq): """直接选择排序""" size=len(seq) foriinrange(0,size-1): k=i;j=i+1 whilej<size: ifseq[j]<seq[k]: k=j j+=1 seq[i],seq[k]=seq[k],seq[i] returnseq
defbubbleSort(seq): """冒泡排序""" size=len(seq) foriinrange(1,size): forjinrange(0,size-i): ifseq[j+1]<seq[j]: seq[j+1],seq[j]=seq[j],seq[j+1] returnseq
def_divide(seq,low,high): """快速排序划分函数""" tmp=seq[low] whilelow!=high: whilelow<highandseq[high]>=tmp:high-=1 iflow<high: seq[low]=seq[high] low+=1 whilelow<highandseq[low]<=tmp:low+=1 iflow<high: seq[high]=seq[low] high-=1 seq[low]=tmp returnlow
def_quickSort(seq,low,high): """快速排序辅助函数""" iflow>=high:return mid=_divide(seq,low,high) _quickSort(seq,low,mid-1) _quickSort(seq,mid+1,high)
defquickSort(seq): """快速排序包裹函数""" size=len(seq) _quickSort(seq,0,size-1) returnseq
defmerge(seq,left,mid,right): tmp=[] i,j=left,mid whilei<midandj<=right: ifseq[i]<seq[j]: tmp.append(seq[i]) i+=1 else: tmp.append(seq[j]) j+=1 ifi<mid:tmp.extend(seq[i:]) ifj<=right:tmp.extend(seq[j:])
seq[left:right+1]=tmp[0:right-left+1]
def_mergeSort(seq,left,right): ifleft==right: return else: mid=(left+right)/2 _mergeSort(seq,left,mid) _mergeSort(seq,mid+1,right) merge(seq,left,mid+1,right)
#二路并归排序 defmergeSort(seq): size=len(seq) _mergeSort(seq,0,size-1) returnseq
if__name__=='__main__': s=[random.randint(0,100)foriinrange(0,20)] prints print"\n" printdirectSelectSort(copy(s)) printdirectInsertSort(copy(s)) printbubbleSort(copy(s)) printquickSort(copy(s)) printmergeSort(copy(s))