[GO] Blasensortierung, Sortierung auswählen, Sortierung einfügen, Shell sortieren, Sortierung zusammenführen, schnelle Sortierung, Sortierung zählen (Python)

Ich werde den Sortieralgorithmus in Python zusammenfassen.

Blasensortierung

Durchschnittliche Berechnungsmenge: $ O (n ^ 2) $ Schlechteste Berechnung: $ O (n ^ 2) $

bubble.py

for i in range(N-1, 0, -1):
    for j in range(i):
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783238

Auswahl Sortieren

Durchschnittliche Berechnungsmenge: $ O (n ^ 2) $ Schlechteste Berechnung: $ O (n ^ 2) $

selection.py

for i in range(N):
    minj = i
    for j in range(i, N):
        if a[j] < a[minj]:
            minj = j

    a[i], a[minj] = a[minj], a[i]

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783283

Sortieren durch Einfügen

Durchschnittliche Berechnungsmenge: $ O (n ^ 2) $ Schlechteste Berechnung: $ O (n ^ 2) $

insertion.py

for i in range(1, N):
    v = a[i]
    j = i - 1

    while j >= 0 and a[j] > v:
        a[j+1] = a[j]
        j -= 1

    a[j+1] = v

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783260

Shell Sort

[Wikipedia-Artikel](https://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%A7%E3%83%AB%E3%82] als Intervallspalte für die intern verwendete Einfügungssortierung $ H = \ frac, wie in% BD% E3% 83% BC% E3% 83% 88 #% E8% A8% 88% E7% AE% 97% E6% 99% 82% E9% 96% 93) Die Ganzzahl, die {3 ^ i - 1} {2} $ erfüllt, wird von der größten übernommen.

Durchschnittlicher Rechenaufwand: Wenn das oben Gesagte als Intervallspalte verwendet wird, wird ein Wert von $ O (n ^ {1,25}) $ erwartet. Schlechteste Berechnung: $ O (n ^ {1.5}) $, wenn das Obige als Intervallspalte übernommen wird

shell.py

def insertion_sort(h):
    for i in range(h, N):
        v = a[i]
        j = i - h

        while j >= 0 and a[j] > v:
            a[j+h] = a[j]
            j -= h

        a[j+h] = v

hs = []
h = 1
while h < N+1:
    hs.append(h)
    h = 3 * h + 1

hs.reverse()

for h in hs:
    insertion_sort(h)

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783355

Zusammenführen, sortieren

Durchschnittliche Berechnungsmenge: $ O (n \ log n) $ Schlechteste Berechnung: $ O (n \ log n) $

merge.py

INF = 1e10  #Größer als der maximal mögliche Wert eines Array-Elements

def merge(left, mid, right):
    l = a[left:mid]
    r = a[mid:right]

    l.append(INF)
    r.append(INF)

    i = 0
    j = 0

    for k in range(left, right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1

def merge_sort(left, right):
    if right - left >= 2:
        mid = (left + right) // 2
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)

merge_sort(0, N)

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783399

Schnelle Sorte

Durchschnittliche Berechnungsmenge: $ O (n \ log n) $ Schlechteste Berechnung: $ O (n ^ 2) $

quick.py

def partition(left, right):
    x = a[right]
    i = left-1

    for j in range(left, right):
        if a[j] <= x:
            i += 1
            a[i], a[j] = a[j], a[i]

    a[i+1], a[right] = a[right], a[i+1]
    return i+1

def quick_sort(left, right):
    if right - left >= 2:
        pivot = partition(left, right-1)
        quick_sort(left, pivot)
        quick_sort(pivot, right)

quick_sort(0, N)

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783489

Sortierung zählen

** Es ist auch eine Art Bucket Sort, Bin Sort **

Durchschnittliche Berechnungsmenge: $ O (n + k) $ Schlechteste Berechnung: $ O (n + k) $

counting.py

K = 100000 #Größer als die Anzahl der möglichen Arten von Array-Elementen

b = [0 for i in range(len(a))]
c = [0 for i in range(K)]

for v in a:
    c[v] += 1

for i in range(K-1):
    c[i+1] += c[i]

for j in reversed(range(N)):
    b[c[a[j]]-1] = a[j]
    c[a[j]] -= 1

#b ist ein sortiertes Array

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783628