データ構造(python言語の説明)--ベース・ソート・アルゴリズム

各pythonソート関数は整数の1つのリストで動作し、リストの2つの位置を1つのswap関数で交換します.

def swap(lyst, i ,j):
    temp = lyst[i]
    lyst[i] = lyst[j]
    lyst[j] = temp

exchange the items at the positions i and j.
ソートの選択
ソートの最も簡単なポリシーは、リスト全体を検索し、最小アイテムの場所を見つけることです.リストの最初のビットにいない場合、アルゴリズムはこのアイテムと最初のアイテムの位置を交換します.その後、アルゴリズムは2番目の位置に戻り、このプロセスを繰り返す.アルゴリズムが最後の項目に達すると、リストはソートされます.このアルゴリズムをselection sortと言います.

def ss(lyst):
    i = 0
    while i < len(lyst) - 1:
        minIndex = i
        j = i + 1
        while j < len(lyst):
            if lyst[j] < lyst[minIbdex]:
                minIndex = j
            j += 1
        if minIndex != i:
            swap(lyst, minIndex, i)
        i += 1

ネストループ,i,jはpositionを表す.例:i=0.j=1 jがlist長より小さい場合、リストの2番目の項目から最初の項目(minIndex)とサイズを比較し、最後の項目から次の項目と比較し、最後の項目まで2番目の項目からループを再開します.
バブルソート
リストの先頭から開始し、リストの末尾に移動するまで、データ・アイテムのペアを比較します.ペアの2つの間の順序が正しくないたびに,アルゴリズムはその位置を交換する.このプロセスは、最大項目を泡のように最後の項目に並べることができる.その後、アルゴリズムは2番目の項目から最後の項目から実行されるまで繰り返され、リストはソートされます.

def bs(lyst):
    n = len(lyst):
    while n > 1:
        i = 1
        while i < n:
            if lyst[i] < lyst[i-1]:
                swap(lyst, i , i-1)
            i += 1
        n -= 1

ソートの挿入
ポリシー:

i番目のラウンドがリストを通過するとき、i番目の項目はリストの前のi番目の項目の正しい位置に挿入されるべきである.

第iラウンドの後、前のi項目は順番に並べられているはずです.

私たちが手にしたトランプのように、私たちは捕まえたi-1枚のトランプを順番に置いた.それでは、捕まえたi枚目のトランプは、手にしたこれらのトランプと比較して、適切な位置を見つけるまで

だった.

挿入ソートには、2つのループが含まれます.周辺のループは1からn−1までの位置を遍歴する.このループの各位置iについて、項目を保存し、位置i−1から内部ループを開始する.このループの各位置jについて、保存された項目(i番目の項目)への挿入位置が見つかるまで、項目を位置j+1に移動する.

def is(lyst):
    i = 1
    while i < len(lyst):
        itemtoinsert = lyst[i]
        j = i - 1
        while j >= 0:
            if itemtoinsert < lyst[j]:
                lyst[j+1] = lyst[j]
                j -= 1
            else:
                break
        lyst[j+1] = itemtoinsert
        i += 1

以上の3つの方法はいずれもソートを実現できるが,効率は高くない.最悪の場合と平均の場合、性能はいずれもO(n 2)である.