Trier par méthode, fonction intégrée

Tout d'abord, pensez à trier la liste suivante.

data = [5, 3, 2, 4, 1, 6]

Il existe deux façons de trier les types de liste par ordre croissant ou décroissant en Python: sort () et sorted (). --List type method sort (): Trie la liste elle-même --Fonction intégrée triée (): renvoie une liste triée en tant que nouvelle valeur de retour

Méthode de type liste sort ()

Réécrivez la liste d'origine elle-même.

data.sort()
print(data)
# [1, 2, 3, 4, 5, 6]

La valeur par défaut est le tri croissant. Définissez l'argument reverse sur True pour trier par ordre décroissant.

data.sort(reverse = True)
print(data)
# [6, 5, 4, 3, 2, 1]

Notez que sort () renvoie None.

x = data.sort()
print(x)
# None

Fonction intégrée triée ()

Si vous spécifiez la liste que vous souhaitez trier dans l'argument, une nouvelle liste triée est générée et renvoyée en tant que valeur de retour.

new_data1 = sorted(data)
print(new_data1)
# [1, 2, 3, 4, 5, 6]

Comme sort (), sorted () est par défaut dans l'ordre croissant. Définissez l'argument reverse sur True pour trier par ordre décroissant.

new_data2 = sorted(data, reverse = True)
print(new_data2)
# [6, 5, 4, 3, 2, 1]

Algorithme de tri

Résumons les trois algorithmes de tri. Je me fiche de la vitesse, de l'utilisation de la mémoire, etc. car je ne les regarde que tous ensemble. La valeur par défaut est l'ordre croissant, et en changeant en commentaire, il devient l'ordre décroissant.

Algorithme de tri de réflexion

Tri des bulles --Tri par insertion --Tri par fusion

Tri à bulles

Il répète la comparaison de deux valeurs adjacentes et le tri selon les conditions.

`bubble_sort`


for i in range(len(data)):
    for j in range(len(data) - 1):
        if data[j] > data[j+1]: # data[j] < data[j+1]
            data[j], data[j+1] = data[j+1], data[j]
print(data)
# [1, 2, 3, 4, 5, 6]

Insérer un tri

Placez (insérez) la cible dans la position appropriée pour les données alignées. Cette fois, la recherche de 2 minutes n'est pas utilisée.

`insert_sort`


for i in range(1, len(data)):
    j = i - 1
    target = data[i]
    while data[j] > target and j >= 0: # data[j] < target
        data[j + 1] = data[j]
        j -= 1
    data[j + 1] = target
print(data)
# [1, 2, 3, 4, 5, 6]

Tri par fusion

Divisez la liste en unités plus petites, comparez les débuts des deux listes et combinez-les en une seule.

`merge_sort`


import math

def merge(x,y):
    m = []
    i = 0
    while i < len(x):
        i += 1
        j = 1
        while j < len(x):
            if x[j-1] > x[j]: # x[j-1] < x[j]
                x[j-1] , x[j] = x[j] , x[j-1]
            j += 1
    i = 0
    while i < len(y):
        i += 1
        j = 1
        while j < len(x):
            if x[j-1] > x[j]: # x[j-1] < x[j]
                x[j-1] , x[j] = x[j] , x[j-1]
            j += 1

    while x != [] and y != []:
        if x[0] < y[0]: # x[0] > y[0]
            m.append(x.pop(0))
        else:
            m.append(y.pop(0))
    if x == []:
        m += y
    else:
        m += x
    return m

data=[7,4,2,8,1,5,3,9,6]
n = 0
i = math.log2(len(data))
while n < i+1:
    tmp = []
    k=0
    while k < len(data):
        tmp = tmp
        m=merge(data[k:k+2**n],data[k+2**n:k+2**(n+1)])
        tmp += m
        k += 2**(n+1)
    data.clear()
    data += tmp
    n += n+1

print(data)
# [1, 2, 3, 4, 5, 6]

À la fin

Comme il s'agit du premier article de Qiita, je pense qu'il y a de nombreux points qui ne peuvent pas être atteints, alors veuillez le souligner. Les types de bulles et d'insertions étaient relativement rapides, mais les tris par fusion prenaient un certain temps.

Trier en Python. Pensons ensuite à l'algorithme.