Lösen der Einführung von AOJ in Algorithmen und Datenstrukturen in Python -Part2-

Einführung

Hallo. Es ist zäh und zäh. Wir werden die Einführung in die Algorithmen und Datenstrukturen von AOJ lösen. Es ist einfach, aufzuzeichnen, was Sie gelernt haben.

Es ist weniger als ein halbes Jahr her, seit ich anfing, mich selbst mit dem Programmieren zu beschäftigen AtCoder ist grün, also bin ich kein starker Mann. Lass uns hart zusammenarbeiten.

Kyapee

Inhaltsverzeichnis

Diesmal ist es TEIL 2: Elementare Sortierung. Ich möchte mein Bestes geben und es bis zum Ende tun.

ALDS1_2_A: Blasensortierung ALDS1_2_B: Selektive Sortierung ALDS1_2_C: Stabile Sortierung ALDS1_2_D: Shell-Sortierung

ALDS1_2_A: Blasensortierung

Blasensorte

def bubbleSort(A, N):
    bit = True
    i = 0
    count = 0
    while bit:
        bit = False
        for j in range(n-1,i,-1):
            if A[j] < A[j-1]:
                A[j],A[j-1] = A[j-1],A[j]
                count += 1
                bit = True
    
    return A , count
        

n = int(input())
A = list(map(int,input().split()))

A,count = bubbleSort(A,n)
print(*A)
print(count)

ALDS1_2_B: Selektive Sortierung

 def SelectionSort(A,n):
    count = 0
    for i in range(n):
        minv = i
        for j in range(i,n):
            if A[j] < A[minv]:
                minv = j
        
        A[i],A[minv] = A[minv],A[i]
        if i!=minv:
            count += 1

    return A,count

n = int(input())
A = list(map(int,input().split()))

A1,count1 = SelectionSort(A,n)

print(*A1)
print(count1)

ALDS1_2_C: Stabile Sortierung

Als Tupel speichern, um die ursprüngliche Liste nicht zu ändern Die Beurteilung der Stabilität ist ein exploratives Denken

def bubbleSort(A, N):
    A = list(A)
    bit = True
    i = 0
    while bit:
        bit = False
        for j in range(n-1,i,-1):
            if int(A[j][1]) < int(A[j-1][1]):
                A[j],A[j-1] = A[j-1],A[j]
                bit = True
    
    return A 

def SelectionSort(A,n):
    A = list(A)
    for i in range(n):
        minv = i
        for j in range(i,n):
            if int(A[j][1]) < int(A[minv][1]):
                minv = j
        
        A[i],A[minv] = A[minv],A[i]

    return A

def is_stable(A_in, A_out):
    n = len(A_in)
    for i in range(n):
        for j in range(i+1,n):
            for a in range(n):
                for b in range(a+1,n):
                    if A_in[i][1] == A_in[j][1] and A_in[i]==A_out[b] and A_in[j]==A_out[a]:
                        return "Not stable"
    return "Stable"

n = int(input())
A = list(input().split())
A_ans = tuple(A)

A1 = bubbleSort(A_ans,n)
print(*A1)
print(is_stable(A_ans, A1))

A2 = SelectionSort(A_ans,n)
print(*A2)
print(is_stable(A_ans, A2))

ALDS1_2_D: Shell-Sortierung

Es ist schwierig ...

def insertionSort(A,n,g):
    global count
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j]>v:
            A[j+g] = A[j]
            j -= g
            count += 1
        A[j+g] = v



def ShellSort(A, n):
    global count
    count = 0
    g = 1
    G = [g]
    while 3 * g + 1 < n:
        g = 3 * g + 1
        G.append(g)
    m = len(G)
    G = G[::-1]
    
    print(m)
    print(*G)

    for j in G:
        insertionSort(A,n,j)



n = int(input())
A = []
for i in range(n):
    a = int(input())
    A.append(a)

ShellSort(A, n)
print(count)

for i in A:
    print(i)

abschließend

Wenn Sie eine falsche Antwort haben, wenden Sie sich bitte an Goto

p.s.p Qitta Ich habe noch nie einen netten Kerl bekommen Wir freuen uns auf die ersten denkwürdigen Verwandten. ↑ Ich habe es das letzte Mal geschrieben, aber ich lobe es