Python实现的几个常用排序算法实例

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))