快速排序的Python實現

上一篇 / 下一篇  2020-11-14 18:18:30 / 個人分類:算法

目錄

  • 快速排序的介紹
  • 快速排序的Python實現

快速排序的介紹

快速排序(quick sort)的采用了分治的策略。

  • 分治策略指的是:
    將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題,然后將這些子問題的解組合為原問題的解。
  • 快排的基本思想是:
    在序列中找一個劃分值,通過一趟排序將未排序的序列排序成 獨立的兩個部分,其中左邊部分序列都比劃分值小,右邊部分的序列比劃分值大,此時劃分值的位置已確認,然后再對這兩個序列按照同樣的方法進行排序,從而達到整個序列都有序的目的。
  • 快速排序的Python實現

    先來看一個 我更想稱之為偽快排的快排代碼:

    defquick_sort(array):iflen(array)<2:returnarrayelse:pivot=array[0]less_than_pivot=[xforx inarrayifx<=pivot]more_than_pivot=[xforx inarrayifx>pivot]returnquick_sort(less_than_pivot)+[pivot]+quick_sort(more_than_pivot)

    這段代碼最關鍵的是pivot這個參數,這段代碼里取序列的第一個元素,然后以這個元素為分組的基準,利用列表解析式使得它左邊的值都比它小,右邊的值都比它大。然后再分別對這些序列進行遞歸排序。

    這段代碼雖然短小利于理解,但是其效率很低,主要體現在以下方面:

    • 分組基準的選取過于隨便,不一定可以取到列表的中間值
    • 空間復雜度大,使用了兩個列表解析式,而且每次選取進行比較時需要遍歷整個序列。
    • 若序列長度過于小(比如只有幾個元素),快排效率就不如插入排序了。
    • 遞歸影響性能,最好進行優化。

    下面用Python寫一個C風格的快排(這里可以體會到快排的精髓):

    defquick_sort(L):returnq_sort(L,0,len(L)-1)defq_sort(L,left,right):ifleft<right:pivot=Partition(L,left,right)q_sort(L,left,pivot-1)q_sort(L,pivot+1,right)returnL
    
    defPartition(L,left,right):pivotkey=L[left]whileleft<right:whileleft<rightand L[right]>=pivotkey:right-=1L[left]=L[right]whileleft<rightand L[left]<=pivotkey:left+=1L[right]=L[left]L[left]=pivotkeyreturnleftL=[5,9,1,11,6,7,2,4]printquick_sort(L)

    快速排序需要提供三個參數:待排序序列序列最小下標值left序列最大下標值right。讓用戶提供這三個參數很麻煩。這里寫個函數進行封裝:

    defquick_sort(L):returnq_sort(L,0,len(L)-1)

    下面看一下q_sort函數:

    defq_sort(L,left,right):ifleft<right:pivot=Partition(L,left,right)q_sort(L,left,pivot-1)q_sort(L,pivot+1,right)returnL

    這個函數的核心是pivot = Partition(L, left, right),在執行它之前,列表的值為[5, 9, 1, 11, 6, 7, 2, 4],而Partition函數做的事情是找到一個分組標準,然后進行分組,讓它左邊的值比它小,右邊的值比它大。
    在經過Partition函數分組后,列表變為[4, 2, 1, 5, 6, 7, 11, 9],并把5的下標值(也就是3)返回給pivot,此時列表變成兩個小列表[4, 2, 1]和[5, 6, 7, 11, 9] ,之后調用q_sort,就是調用q_sort(L,0, 2)q_sort(L, 4 ,7),對其進行Partition操作,直到整個列表有序為止。

    下面看看關鍵的Partition函數是如何做的:

    defPartition(L,left,right):pivotkey=L[left]whileleft<right:whileleft<rightand L[right]>=pivotkey:right-=1L[left]=L[right]whileleft<rightand L[left]<=pivotkey:left+=1L[right]=L[left]L[left]=pivotkeyreturnleft

    以一趟排序為例[5, 9, 1, 11, 6, 7, 2, 4]

    • 開始排序時,left=0,right=7,首先用表的第一個下標值作為 分組關鍵字pivot,


                                                                     第一趟排序過程
    進行while left < right and L[right] >= pivotkey:判斷,其中L[right]=4 不滿足條件,跳出循環,執行L[left] = L[right],執行后列表變成:

                            第一趟排序結果

    然后進行while left < right and L[left] <= pivotkey:,L[left] = 4 <= 5,條件成立,left向右邊移動,然后L[left] = 9 不滿足條件,執行L[right] = L[left],執行后列表變為:
                                                     第一趟排序過程
    然后進行while left < right判斷,條件成立,繼續進行判斷while left < right and L[right] >= pivotkey:,L[right] = 9,滿足條件,right向左移動1,繼續判斷,不滿足條件,執行L[left] = L[right],執行后列表變為:
                        第一趟排序過程
    然后進行while left < right and L[left] <= pivotkey:判斷,L[left] = 2,滿足條件,left向右移動,然后L[left] = 1,滿足條件,left向右移動,L[left] = 11,不滿足條件,執行L[right] = L[left],執行后列表變為:
                                    第一趟排序過程
    然后進行while left < right判斷,條件成立,繼續進行判斷:while left < right and L[right] >= pivotkey:,滿足條件,right向左移動,一直移動到這樣的狀態:

                                         第一趟排序過程
    此時不滿足條件:left < right,跳出循環。然后執行L[left] = pivotkey,并返回left下標值。此時序列變為:
                                           第一趟排序結果


    接下來就是用遞歸分別對子列表進行排序。讀者可以自己試試。

    問題的優化

    • 分組基準
      對于上面的代碼,分組基準的選取只是取列表的第一個值,太過于隨便,當取到序列的中間值時,快排效率是最高的,第一個值未必是列表的中間值。為了解決這個問題,我們可以選取列表中的幾個值進行簡單的比較,然后取這幾個值的中間值 作為分組基準。 這里就不寫代碼了,讀者可以自己實現。

    • 空間使用大。
      上面的代碼已經解決了比較次數的問題。

    • 若序列長度過于小(比如只有幾個元素),快排效率就不如插入排序了。
      我們可以設置一個列表元素大小的臨界值,若小于這個值,就用插入排序,大于這個值用快排。



    作者:一根薯條
    鏈接:https://www.jianshu.com/p/2b2f1f79984e
    來源:簡書



    TAG:

     

    評分:0

    我來說兩句

    顯示全部

    :loveliness: :handshake :victory: :funk: :time: :kiss: :call: :hug: :lol :'( :Q :L ;P :$ :P :o :@ :D :( :)

    Open Toolbar
    日本av