Algorithms Part 1-Question 2-QuickSort-快速排序算法

  Algorithms: Design and Analysis, Part 1         第一章講的是分治算法，即DC，這一章講的是快速排序QuickSort。作業難度已經增加了，Problem Sets做了兩次一不小心只得了四分，編程作業也作了兩次才作對。     這次作業是實現快速排序，並改變哨兵元素的選擇方法比較性能。哨兵可以選擇為第一個、最後一個元素，也可以選取首、尾、中間三個元素第二大的數字。     最後一種方法實現時可以借用list的排序方法。     代碼如下：      

def quickSort(arrayall):  
    if len(arrayall)<=1:return arrayall,0  
  
    #sel p   
    #p=0   
    #p=len(arrayall)-1   
  
  
    p=(len(arrayall)-1)/2  
    a=[(arrayall[0],0),(arrayall[p],p),(arrayall[-1],len(arrayall)-1)]  
    a.sort()  
    tmp,p=a[1]  
      
    if p!=0:  
        arrayall[0],arrayall[p]=arrayall[p],arrayall[0]  
    indi=1  
    for indj in range(1,len(arrayall)):  
        if arrayall[indj]<arrayall[0]:  
            arrayall[indi],arrayall[indj]=arrayall[indj],arrayall[indi]  
            indi+=1  
    arrayall[0],arrayall[indi-1]=arrayall[indi-1],arrayall[0]  
      
    arrayallp,mp=quickSort(arrayall[:indi-1])  
    arrayallq,mq=quickSort(arrayall[indi:])  
  
    return arrayallp+[arrayall[indi-1]]+arrayallq,mp+mq+len(arrayall)-1  
  
  
f=open('QuickSort.txt','r')  
listall=f.read()  
listall=[int(x) for x in listall.split()]  
f.close()  
  
sortedlist,m=quickSort(listall)  
print m  
  
      

def quickSort(arrayall):
    if len(arrayall)<=1:return arrayall,0

    #sel p
    #p=0
    #p=len(arrayall)-1


    p=(len(arrayall)-1)/2
    a=[(arrayall[0],0),(arrayall[p],p),(arrayall[-1],len(arrayall)-1)]
    a.sort()
    tmp,p=a[1]
    
    if p!=0:
        arrayall[0],arrayall[p]=arrayall[p],arrayall[0]
    indi=1
    for indj in range(1,len(arrayall)):
        if arrayall[indj]<arrayall[0]:
            arrayall[indi],arrayall[indj]=arrayall[indj],arrayall[indi]
            indi+=1
    arrayall[0],arrayall[indi-1]=arrayall[indi-1],arrayall[0]
    
    arrayallp,mp=quickSort(arrayall[:indi-1])
    arrayallq,mq=quickSort(arrayall[indi:])

    return arrayallp+[arrayall[indi-1]]+arrayallq,mp+mq+len(arrayall)-1


f=open('QuickSort.txt','r')
listall=f.read()
listall=[int(x) for x in listall.split()]
f.close()

sortedlist,m=quickSort(listall)
print m