Fusionner le tri en utilisant récursif

Comment fusionner le tri en utilisant récursif

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]

  1. [9] et [4,2] sont triés par-> [9] et [4,2] -> result_sort => [2,4,9]
  2. [3,1] et [9,4,2] sont triés par -> [3,1] et [9,4,2] -> result_sort => [1,2,3,4,9]
  3. 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)

Recommended Posts

Fusionner le tri en utilisant récursif
Fusionner le tri expliqué
Tri à bulles sans utiliser le tri
Tri rapide sans utiliser le tri
Récursif
Trier
Ecrire FizzBuzz en utilisant map (), reduction (), filter (), récursif