Source: Big Data DT

Cet article est à propos de 5200 mots , Suggérer une lecture 10 minutes

L'algorithme de tri est l'un des algorithmes les plus élémentaires de "Structure et algorithme de données". Cet article présente 10 algorithmes de tri internes courants et comment les implémenter en Python.

Les algorithmes de tri peuvent être divisés en tri interne et tri externe. Le tri interne est le tri des enregistrements de données en mémoire, tandis que le tri externe est dû au fait que les données triées sont volumineuses et ne peuvent pas accueillir tous les enregistrements triés en même temps. Dans le processus de tri, vous devez accéder à la mémoire externe.

Les algorithmes de tri internes courants sont: Insérer le tri, le tri en côte, le tri par sélection, le tri par bulles, le tri par fusion, le tri rapide, le tri en tas, le tri par cardinalité, etc.

Résumez avec une image:

À propos de la complexité du temps:

• Tri par ordre carré (O (n2)): toutes sortes de tri simple, insertion directe, sélection directe et tri à bulles;
• Tri par ordre logarithmique linéaire (O (nlog2n)): tri rapide, tri en tas et tri par fusion;
• Tri en côte: O (n1 + §)) tri, § est une constante entre 0 et 1;
• Tri par ordre linéaire (O (n)): tri cardinal, en plus du tri par godet et boîte.

À propos de la stabilité:

• L'ordre des deux clés égales après le tri est le même que l'ordre avant le tri.
• Algorithmes de tri stables: tri à bulles, tri par insertion, tri par fusion et tri par cardinalité.
• Pas un algorithme de tri stable: tri par sélection, tri rapide, tri en côte, tri en tas.

Glossaire:

• n: échelle de données.
• k: le nombre de "barils".
• En place: occupe une mémoire constante, n'occupe pas de mémoire supplémentaire.
• Out-place: Prenez de la mémoire supplémentaire.

01 Tri des bulles

Bubble Sort (Bubble Sort) est également un algorithme de tri simple et intuitif. Il a visité à plusieurs reprises la séquence à trier, comparé deux éléments à la fois et les a échangés s'ils étaient dans le mauvais ordre. Le travail de visite de la séquence est répété jusqu'à ce qu'aucun échange supplémentaire ne soit nécessaire, ce qui signifie que la séquence a été triée. Le nom de cet algorithme vient du fait que plus l'élément «flottera» lentement vers le haut de la séquence par l'échange.

En tant que l'un des algorithmes de tri les plus simples, le tri à bulles me donne le même sentiment qu'Abandon apparaît dans le livre de mots. C'est le premier sur la première page à chaque fois, donc c'est le plus familier. Il existe également un algorithme d'optimisation pour le tri des bulles, qui consiste à définir un drapeau. Lorsque les éléments ne sont pas échangés lors d'un parcours de séquence, il prouve que la séquence est déjà ordonnée. Mais cette amélioration a peu d'effet sur l'amélioration des performances.

Étape d'algorithme

Comparez les éléments adjacents. Si le premier est plus grand que le second, échangez-les tous les deux.

Faites de même pour chaque paire d'éléments adjacents, de la première paire au début à la dernière paire à la fin. Une fois cette étape terminée, le dernier élément sera le plus grand nombre.

Répétez les étapes ci-dessus pour tous les éléments sauf le dernier.

Continuez à répéter les étapes ci-dessus pour de moins en moins d'éléments à chaque fois jusqu'à ce qu'il n'y ait plus de paires de nombres à comparer.

2. Présentation d'animation

3. Code Python

def bubbleSort (arr): pour i dans la plage (1, len (arr)): pour j dans la plage (0, len (arr) -i): si arr >  arr: arr, arr = arr, arr return arr

02 Sélectionner le tri

Le tri par sélection est un algorithme de tri simple et intuitif, quelles que soient les données saisies, il s'agit d'une complexité temporelle O (n²). Ainsi, lorsque vous l'utilisez, plus la taille des données est petite, mieux c'est. Le seul avantage peut être qu'il ne prend pas d'espace mémoire supplémentaire.

Étape d'algorithme

Recherchez d'abord le plus petit (grand) élément dans la séquence non triée et stockez-le au début de la séquence triée.

Continuez ensuite à rechercher le plus petit (grand) élément parmi les éléments non triés restants, puis placez-le à la fin de la séquence triée.

Répétez la deuxième étape jusqu'à ce que tous les éléments soient triés.

2. Présentation d'animation

3. Code Python

def selectionSort (arr): pour i dans la plage (len (arr) -1): # enregistre l'indice du plus petit nombre minIndex = i pour j dans la plage (i + 1, len (arr)): si arr <  arr: minIndex = j # Lorsque i n'est pas le nombre minimum, échangez i et le nombre minimum si i! = minIndex: arr , arr = arr, arr  retour arr

03 Insérer le tri

L'implémentation du code du tri par insertion n'est pas aussi simple et grossière que le tri par bulles et le tri par sélection, mais son principe devrait être le plus facile à comprendre, car quiconque a joué au poker doit pouvoir le comprendre en quelques secondes. Le tri par insertion est l'un des algorithmes de tri les plus simples et les plus intuitifs. Il fonctionne en construisant une séquence ordonnée. Pour les données non triées, il parcourt la séquence triée, trouve la position correspondante et l'insère.

Le tri par insertion est le même que le tri par bulles, et il existe également un algorithme d'optimisation appelé demi-insertion fractionnée.

Étape d'algorithme

Considérez le premier élément de la première séquence à trier comme une séquence ordonnée et traitez le deuxième élément du dernier élément comme une séquence non triée.

Scannez la séquence non triée du début à la fin et insérez chaque élément numérisé dans la position appropriée de la séquence commandée. (Si l'élément à insérer est égal à un élément dans la séquence ordonnée, l'élément à insérer est inséré après l'élément égal.)

2. Présentation d'animation

3. Code Python

def insertionSort (arr): pour i dans la plage (len (arr)): preIndex = i-1 current = arr  tandis que preIndex > = 0 et arr >  courant: arr = arr preIndex- = 1 arr = courant retour arr

04 Hill Hill

Le tri en côte, également connu sous le nom d'algorithme de tri incrémentiel décroissant, est une version plus efficace et améliorée du tri par insertion. Mais le tri Hill est un algorithme de tri instable.

Le tri par colline propose une méthode améliorée basée sur les deux propriétés suivantes du tri par insertion:

• Le tri par insertion a une efficacité élevée lorsqu'il fonctionne sur des données presque triées, c'est-à-dire qu'il peut atteindre l'efficacité du tri linéaire;
• Mais le tri par insertion est généralement inefficace car le tri par insertion ne peut déplacer les données qu'un bit à la fois.

L'idée de base du tri Hill est la suivante: divisez d'abord la séquence entière d'enregistrements à trier en plusieurs sous-séquences et insérez-les directement. Lorsque les enregistrements de la séquence entière sont "fondamentalement ordonnés", puis insérez tous les enregistrements dans l'ordre.

Étape d'algorithme

Choisissez une séquence incrémentale t1, t2, ..., tk, où ti >  tj, tk = 1;

Trier la séquence par k passes en fonction du nombre k de la séquence incrémentale;

Pour chaque tri, selon l'incrément ti correspondant, la séquence à trier est divisée en plusieurs sous-séquences de longueur m, et chaque sous-table est directement insérée et triée. Ce n'est que lorsque le facteur d'incrémentation est 1 que la séquence entière est traitée comme une table et que la longueur de la table est la longueur de la séquence entière.

2. Code Python

def shellSort (arr): importation de l'écart mathématique = 1 tandis que (écart <  len (arr) / 3): écart = écart * 3 + 1 tandis que écart >  0: pour i dans la plage (écart, len (arr)): temp = arr  j = i-gap tandis que j > = 0 et arr >  temp: arr = arr j- = gap arr = temp gap = math.floor (gap / 3) return arr}

05 fusionner le tri

Le tri par fusion (tri par fusion) est un algorithme de tri efficace basé sur l'opération de fusion. L'algorithme est une application très typique utilisant Divide and Conquer.

En tant qu'application d'algorithme typique de l'idée de diviser pour régner, le tri par fusion est implémenté par deux méthodes:

• Récursion descendante (toutes les méthodes récursives peuvent être réécrites par itération, il existe donc une seconde méthode);
• Itération de bas en haut.

Comme le tri par sélection, les performances du tri par fusion ne sont pas affectées par les données d'entrée, mais les performances sont bien meilleures que le tri par sélection, car il s'agit toujours de la complexité temporelle O (nlogn). Le prix est le besoin d'espace mémoire supplémentaire.

Étape d'algorithme

Faites une demande d'espace afin que sa taille soit la somme de deux séquences triées. Cet espace est utilisé pour stocker la séquence fusionnée;

Définissez deux pointeurs, la position initiale est la position de départ de deux séquences triées;

Comparez les éléments pointés par les deux pointeurs, sélectionnez l'élément relativement petit et placez-le dans l'espace fusionné, puis déplacez le pointeur vers la position suivante;

Répétez l'étape 3 jusqu'à ce qu'un pointeur atteigne la fin de la séquence;

Copiez tous les éléments restants d'une autre séquence directement à la fin de la séquence fusionnée.

2. Présentation d'animation

3. Code Python

def mergeSort (arr): importer des maths si (len (arr) < 2): return arr middle = math.floor (len (arr) / 2) left, right = arr, arr return merge (mergeSort (left), mergeSort (right)) def merge (left, right): resultat = while left et à droite: si laissé < = droite: result.append (left.pop (0)); else: result.append (right.pop (0)); tandis que left: result.append (left.pop (0)); tandis que right: result.append (right.pop (0)); retourne le résultat

06 Tri rapide

Quicksort est un algorithme de tri développé par Tony Hall. Dans des conditions moyennes, le tri de n éléments nécessite des comparaisons (nlogn). Dans le pire des cas, des comparaisons (n2) sont nécessaires, mais cette situation n'est pas courante. En fait, le tri rapide est généralement beaucoup plus rapide que les autres algorithmes (nlogn) car sa boucle interne peut être mise en uvre efficacement sur la plupart des architectures.

Quicksort utilise la stratégie Divide and Conquer pour diviser une liste en deux sous-listes.

Le tri rapide est une autre application typique de l'idée diviser pour mieux régner dans les algorithmes de tri. En substance, le tri rapide doit être considéré comme une méthode de division et de conquête récursive basée sur le tri à bulles.

Le nom du tri rapide est simple et grossier, car lorsque vous entendez le nom, vous en connaissez le sens, il est rapide et efficace! Il s'agit de l'un des algorithmes de tri les plus rapides pour le traitement des mégadonnées.

Bien que la complexité temporelle de Worst Case atteigne O (n²), d'autres sont excellentes, et dans la plupart des cas, elle fonctionne mieux que l'algorithme de tri avec une complexité temporelle moyenne de O (n logn), mais pourquoi, Je ne sais pas non plus. Heureusement, mon trouble obsessionnel-compulsif était de nouveau coupable. Après avoir vérifié les données N, j'ai finalement trouvé une réponse satisfaisante au "Concours d'art algorithmique et d'informatique"

Le pire des cas pour le tri rapide est O (n²), comme le tri rapide des nombres séquentiels. Mais son temps d'amortissement attendu est O (nlogn), et le facteur constant impliqué dans la notation O (nlogn) est très petit, ce qui est beaucoup plus petit que l'ordre de tri de fusion dont la stabilité est égale à O (nlogn). Par conséquent, pour la plupart des nombres aléatoires avec une séquence faible, le tri rapide est toujours meilleur que le tri par fusion.

Étape d'algorithme

Choisissez un élément de la séquence, appelé "pivot";

Réorganisez la séquence, tous les éléments plus petits que la valeur de référence sont placés devant la référence et tous les éléments plus grands que la valeur de référence sont placés derrière la référence (le même nombre peut aller de chaque côté). Une fois cette partition terminée, la donnée se trouve au milieu de la séquence. C'est ce qu'on appelle une opération de partition (partition);

Récursivement (récursivement) triez la sous-série d'éléments inférieure à la valeur de référence et la sous-série d'éléments supérieure à la valeur de référence.

Le cas inférieur de la récursivité est que la taille de la séquence est zéro ou un, c'est-à-dire qu'elle sera toujours triée. Bien qu'il ait été récursif, cet algorithme se terminera toujours, car à chaque itération (itération), il mettra au moins un élément à sa dernière position.

2. Présentation d'animation

3. Code Python

def quickSort (arr, left = None, right = None): left = 0 sinon isinstance (left, (int, float)) else left right = len (arr) -1 if not isinstance (right, (int, float) ) sinon à droite si à gauche <  droite: partitionIndex = partition (arr, gauche, droite) quickSort (arr, gauche, partitionIndex-1) quickSort (arr, partitionIndex + 1, droite) partition returnarrdef (arr, gauche, droite): pivot = index gauche = pivot + 1 i = index tandis que i < = droite: si arr   <  arr: swap (arr, i, index) index + = 1 i + = 1 swap (arr, pivot, index-1) return index-1def swap (arr, i, j): arr , arr = arr, arr

07 Tri par tas

Heapsort (Heapsort) fait référence à un algorithme de tri conçu à l'aide de la structure de données du tas. L'empilement est une structure arborescente binaire approximativement complète et répond à la nature de l'empilement en même temps: c'est-à-dire que la valeur clé ou l'index d'un nud enfant est toujours inférieur (ou supérieur à) son nud parent. Le tri par tas peut être considéré comme une sorte de sélection utilisant le concept de tri par tas. Il existe deux méthodes:

• Grand tas supérieur: la valeur de chaque nud est supérieure ou égale à la valeur de ses nuds enfants, utilisée dans l'ordre croissant dans l'algorithme de tri du tas;
• Petit segment supérieur: la valeur de chaque nud est inférieure ou égale à la valeur de ses nuds enfants, utilisée dans l'ordre décroissant dans l'algorithme de tri du segment.

La complexité temporelle moyenne du tri en tas est (nlogn).

Étape d'algorithme

Créez un tas H;

Échangez le début (valeur maximale) et la fin du tas;

Réduisez la taille du tas de 1 et appelez shift_down (0), le but est d'ajuster les données du haut du nouveau tableau à la position correspondante;

Répétez l'étape 2 jusqu'à ce que la taille du tas soit 1.

2. Présentation d'animation

3. Code Python

def buildMaxHeap (arr): importer les mathématiques pour i dans la plage (math.floor (len (arr) / 2), - 1, -1): heapify (arr, i) def heapify (arr, i): left = 2 * i + 1 droite = 2 * i + 2 plus grande = i si gauche <  arrLen et arr >  arr: plus grand = gauche si droit <  arrLen et arr >  arr: le plus grand = à droite si le plus grand! = i: swap (arr, i, le plus grand) heapify (arr, le plus grand) def swap (arr, i, j): arr , arr = arr, arr def heapSort (arr): global arrLen arrLen = len (arr) buildMaxHeap (arr) pour i dans la plage (len (arr) -1,0, -1): swap (arr, 0, i) arrLen- = 1 heapify ( arr, 0) returnarr

08 Comptage et tri

Le noyau du tri de comptage consiste à convertir la valeur des données d'entrée en clé et à la stocker dans l'espace de tableau supplémentaire. En tant que sorte de complexité temporelle linéaire, le tri de comptage nécessite que les données d'entrée doivent être un entier avec une certaine plage.

1. Démo

2. Code Python

def countingSort (arr, maxValue): bucketLen = maxValue + 1 bucket = * bucketLen sortedIndex = 0 arrLen = len (arr) pour i dans la plage (arrLen): sinon, bucket: bucket = 0 bucket + = 1 pour j dans la plage (bucketLen ): tout en seau > 0: arr = j sortedIndex + = 1 bucket- = 1returnarr

09 Tri des godets

Le tri par compartiment est une version améliorée du tri par comptage. Il utilise la relation de cartographie de la fonction, la clé d'une efficacité élevée réside dans la détermination de cette fonction de cartographie. Afin de rendre le tri des seaux plus efficace, nous devons faire deux choses:

Dans le cas d'un espace supplémentaire suffisant, essayez d'augmenter le nombre de barils.

La fonction de mappage utilisée peut répartir uniformément les données d'entrée N dans K compartiments.

Dans le même temps, pour le tri des éléments dans le compartiment, quel algorithme de tri de comparaison est sélectionné est essentiel à l'impact sur les performances.

• Quand est le plus rapide

Lorsque les données d'entrée peuvent être réparties uniformément dans chaque compartiment.

• Quand est le plus lent

Lorsque les données d'entrée sont allouées au même compartiment.

• Code Python

def bucket_sort (s): "" "tri du bucket" "" min_num = min (s) max_num = max (s) # taille du bucket bucket_range = (max_num-min_num) / len (s) # bucket array count_list = # Remplissez le tableau de compartiment avec des nombres pour i dans s: count_list.append (i) s.clear () # Backfill, où le tri interne du compartiment appelle directement trié pour i dans count_list: pour j dans trié (i): s.append (j) si __name__ == __main__: a = bucket_sort (a) print (a) #

10 Tri par cardinalité

Le tri par cardinalité est un algorithme de tri d'entiers non comparatif dont le principe est de découper les entiers en différents nombres en fonction du nombre de chiffres, puis de comparer chaque chiffre séparément. Étant donné que les entiers peuvent également exprimer des chaînes (telles que des noms ou des dates) et des nombres à virgule flottante dans un format spécifique, le tri par cardinalité n'est pas limité aux entiers.

1. Tri par cardinalité, tri par comptage ou tri par compartiment

Il existe deux méthodes de tri par cardinalité:

Ces trois algorithmes de tri utilisent tous le concept de compartiments, mais il existe des différences évidentes dans l'utilisation des compartiments:

• Tri par cardinalité: attribuez des compartiments en fonction de chaque chiffre de la valeur de clé;
• Comptage et tri: chaque compartiment ne stocke qu'une seule valeur de clé;
• Tri des compartiments: chaque compartiment stocke une plage de valeurs.

2. Présentation d'animation

3. Code Python

def RadixSort (liste): i = 0 #Trier initialement par bits n = 1 #Le nombre minimum de chiffres est défini sur 1 (dont 0) max_num = max (liste) #Obtenir le nombre maximum dans le tableau avec sort while max_num >  10 ** n: # Le nombre maximum est de quelques chiffres n + = 1 tandis que i <  n: bucket = () #Utilisez un dictionnaire pour construire un bucket pour x dans la plage (10): bucket.setdefault (x,) #Vider chaque bucket pour x dans la liste: #Trier chaque bit radix = int (( x / (10 ** i))% 10) #Get la cardinalité de chaque bucket de bits.append (x) #Ajouter l'élément de tableau correspondant au bucket correspondant à la cardinalité j = 0 pour k dans la plage (10) : si len (bucket)! = 0: #si le bucket n'est pas vide pour y dans bucket: #list chaque élément dans la bucket list = y #put le remettre dans le tableau j + = 1 i + = 1return list

Editeur: Wang Jing

Relecture: Lin Yilin

-Terminer-

Suivez la plateforme publique officielle WeChat de Tsinghua-Qingdao Data Science Research Institute " THU Data Pie  "Et numéro de sur" Data Pie THU  "Obtenez plus d'avantages de cours et un contenu de qualité.