[PYTHON] Fusionner le tri en utilisant récursif

Comment fusionner le tri en utilisant récursif

• Cela ressemble à un mémorandum (j'ai oublié quand je regarde en arrière, je pense qu'il y a des choses que je ne peux pas comprendre avec juste le code)

Données du tableau = [3, 1, 9, 4, 2, 5, 7, 6, 8, 10]

1. Diviser en gauche et droite au milieu du tableau => Gauche [3,1,9,4,2] Droite [5,7,6,8,10] Milieu: 5

2. Divisez davantage par la gauche et la droite (utilisez récursif) => Gauche [3,1,9,4,2] -> Gauche [3,1] Droite [9,4,2] Milieu: 2 Droite [5,7,6,8,10] -> Gauche [5,7] Droite [6,8,10] ....

3. Enfin, ce sera [3], [1], [9], [4], [2], [5], [7], [6], [8], [10](préparation terminée) !)

4. Cette fois, les valeurs divisées en deux sont affectées aux nouvelles variables (result_sort) dans l'ordre de gauche (car il commence à 0). [3,1], [4,2] => Each Trier [1,3] [2,4]

• Il n'y a pas de [9] et [6]! Pourquoi? => Lors de la division de [9,4,2] Puisque le centre est "1", à droite: [9] À gauche: [4,2], donc le traitement commence à [4,2] en premier. (Pour la récurrence, procédez comme 1-> 2-> 3-> 4-> 5, puis rembobinez tout en rembobinant comme 5-> 4-> 3-> 2-> 1) => * * Pour approfondir votre compréhension, étudiez la récidive **

5. [9] et [4,2] sont triés par-> [9] et [4,2] -> result_sort => [2,4,9]
6. [3,1] et [9,4,2] sont triés par -> [3,1] et [9,4,2] -> result_sort => [1,2,3,4,9]
7. Le droit est complet. Ensuite, faites 4 à 6 à partir de la gauche 8 [3,1,9,4,2] et droite [5,7,6,8,10] sont comparés 9 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Explication en code (python)

sample.py

data = [3, 1, 9, 4, 2, 5, 7, 6, 8, 10]

Attribuer des données à des variables

sample.py

def merge_sort(data):
    if len(data) <= 1: #Vrai si le contenu du tableau est égal ou inférieur à 1
        return data
    center = len(data) // 2 #Centre du tableau
    left = merge_sort(data[:center])#Divisé à gauche[3,1,9,4,2] => [3,1] => [3]
    right = merge_sort(data[center:]) #Divisé à droite[5,7,6,8,10] => [9,4,2] => [1]
    return left, right #=> [3], [1]Est passé

Vous pouvez faire 1 ~ 3 avec ce code.

sample.py

def merge_sort(data):
    if len(data) <= 1: #Vrai si le contenu du tableau est égal ou inférieur à 1
        return data
    center = len(data) // 2 #Centre du tableau
    left = merge_sort(data[:center])#Divisé à gauche[3,1,9,4,2] => [3,1] => [3]
    right = merge_sort(data[center:]) #Divisé à droite[5,7,6,8,10] => [9,4,2] => [1]
    return merge(left, right)

Ajoutez simplement return merge (gauche, droite)

sample.py

def merge(left, right):
    result_sort = [] #Résultat combiné
    left_i, right_j = 0, 0
    print(left + right) #=>Connaissez la séquence que vous essayez de trier
    while(left_i < len(left)) and (right_j < len(right)):
        if left[left_i] <= right[right_j]:
            result_sort.append(left[left_i]) #Ici, comparez la droite et la gauche que vous essayez de combiner et frappez le résultat.
            left_i += 1
        else:
            result_sort.append(right[right_j]) #Ici, comparez la droite et la gauche que vous essayez de combiner et frappez le résultat.
            right_j += 1
    if len(left[left_i:]) != 0: #=>Vrai si le nombre dans le tableau de gauche qui a été trié mais qui reste n'est pas 0(left_Vérifiez avec i)
        result_sort.extend(left[left_i:])
    if len(right[right_j:]) != 0:
        result_sort.extend(right[right_j:]) #Vrai (à droite) si le nombre dans le tableau de droite qui a été trié mais qui reste n'est pas 0_Confirmer avec j)
    print(result_sort) #=>Vous pouvez voir la séquence triée
    return result #Valeur de retour finale

Faire 4 ~ 8

Citation (merci)

• https://medium-company.com/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88/
• https://qiita.com/woolon/items/4cff50de7e697cb2664f