python高速ソートの様々な実装方法

いつも速い列が奇妙だと思って、速い列の思想は区分にほかならない.頭の中にもダイナミックな図を形成することができて、それから速い列の実現は1つの統一的な言い方がなくて、大丈夫な時に速い列を練習しても収穫があります.
1.よく使われる方法は便器に座ってアルゴリズムを読む:この文章の構想ははっきりしているが、実はステップにはいくつかの小さな問題が存在し、速い列の原理を理解するのに役立つだけで、実際に実現する時の論理にはいくつかの小さな違いがある.手順まとめ:*配列をaに並べ替え、カーソルleftをaの一番左から、カーソルrightを一番右から*pivotを配列の最初の数(すなわちa[left])とし、配列の左右の境界値として*カーソルを右から左に移動(right=right-1)してpivotより小さい数が見つかるまで、A[left]に格納*カーソルを左から右に移動(left=left+1)pivotより大きい最初の数が見つかるまで、a[right]に格納*上記の2つのステップを2つ繰り返す*カーソルが出会うまでpivotをa[left]位置に配置*その後pivotの左右2つの部分を再帰的に並べ替える

def quicksort(lists,low,high):
    if low < high:
        l = low
        r = high
        pivot = lists[l]
        while l < r:
            while l < r and lists[r] >= pivot:
                r -= 1
            lists[l] = lists[r]
            while l < r and lists[l] <= pivot:
                l += 1
            lists[r] = lists[l]
        lists[l] = pivot
        quicksort(lists, low, l-1)
        quicksort(lists, l + 1,high)
    return lists

2018.05.25ランダムに選択するpivot要素は、実際のシーンの配列の大部分が順序付けられているシーン(O(n^2)の複雑さに劣化しにくい)に適合する.しかし、乱数を生成するプロセスは時間の消費を増加させ、対応する解決方法があります(例えば、ランダムテーブルを事前に生成し、テーブルで選択するたびに擬似ランダムを実現します).

def ranqsort(a, low, high):
    if low < high:
        l, r = low, high
        #random and swap
        rand = random.randint(low,high)
        a[rand], a[l] = a[l], a[rand]
        p = a[l]
        while l < r:
            while l < r and a[r] >= p:
                r -= 1
            a[l] = a[r]
            while l < r and a[l] <= p:
                l += 1
            a[r] = a[l]
        a[l] = p
        qsort(a, low, l-1)
        qsort(a, l+1, high)

知識関連可変タイプと可変タイプ:書く再帰が最も恐れられるのはreturnの処理であり、処理が悪いと無限再帰を生じる.ここではpythonにおける可変タイプと可変タイプを理解する、可変タイプにはlist,dict,setなどが含まれ、可変タイプにはstring,int,tupleなどが含まれる.データ型の可変と可変は、関数における値の伝達方式の違いを決定し、pythonではc++のように様々な参照とポインタの値を記憶する必要はなく、可変型の値が関数にコピーされたことを覚えていれば、可変型の値の関数数での修正は変数自体を直接変更する.リストは可変タイプなので、戻り値の問題を考慮する必要はありません.入力したリストを下付きで並べ替えるだけでいいです.
2.もっとpythonicの書き方

def pythonicqs(a):
    if len(a) <= 1:
        return a
    else:
        pivot = a[0]
        pivots = [n for n in a if n == pivot]
        return pythonicqs([n for n in a if n < pivot]) + pivots + pythonicqs([n for n in a if n > pivot])

この方式は、コードをほとんど見ることができるソート原理まで直感的で便利であるべきであり、pythonにおけるリスト生成式という特性を用いるが、空間的複雑さから、追加のオーバーヘッド記憶配列が増加する.時間的複雑さは方法1の2倍であるべきであるが,O(Nlogn)と見なすことができる.

##     
import time
a = [random.randint(0,1000) for _ in range(100)]

import time
t = time.clock()
quicksort(a,0,len(a)-1)
print('Time consumed:',time.clock()-t)

Time consumed: 0.0004520551756286295

a = [random.randint(0,1000) for _ in range(100)]

t = time.clock()
pythonicqs(a)
print('Time consumed:',time.clock()-t)

Time consumed: 0.0005797025805804878

長さ100の配列をざっと試験すると、ほぼ同じ桁にあることがわかるが、方法2は方法1よりも時間がやや長い.方法2はもっと直観的だが、論理ステップには違いがあり、方法1はもっと通用すべきで、少し修正すればJAVAバージョン、C++バージョンであり、面接では方法1を答えとして記入すべきで、方法2はpython面接の加点項目とすることができる.
3.アルゴリズム導論上の高速列の実現(2018.05.25更新)

def algqsort(a, l ,r):
    if l < r:
        p = a[r]
        i = l - 1
        for j in range(l,r):
            if a[j] <= p:
                i += 1
                a[i],a[j] = a[j], a[i] #           p    ,i==j       
        i += 1
        a[i],a[r] = a[r],a[i]
        algqsort(a,l,i-1)
        algqsort(a,i+1,r)

聡明で便利な方法だ.主な違いは、最左端を主元(pivot)とし、最右端を主元とすることにある.