Maison > Problème commun > le corps du texte

tri en tas

(*-*)浩
Libérer: 2019-06-15 18:05:19
original
2239 Les gens l'ont consulté

Tri par tas

Le tri par tas est un algorithme de tri conçu en utilisant la structure de données d'un tri par tas est un tri par sélection, son pire et son meilleur, la complexité temporelle moyenne est O. (nlogn), qui est également un tri instable. Tout d’abord, comprenons brièvement la structure du tas.

tri en tas

Tas

Un tas est un arbre binaire complet avec les propriétés suivantes : la valeur de chaque nœud est supérieure ou égale à ses enfants gauche et droit La valeur d'un nœud est appelée un grand tas supérieur ; ou la valeur de chaque nœud est inférieure ou égale à la valeur de ses nœuds enfants gauche et droit, qui est appelé un petit tas supérieur.

Cours recommandé : Tutoriel PHP.

Comme indiqué ci-dessous :

tri en tas

En même temps, nous numérotons les nœuds du tas par couche pour cartographier cette structure logique Cela ressemble à ceci dans le tableau

tri en tas

Le tableau est logiquement une structure de tas Nous utilisons une formule simple pour décrire la définition d'un tas :

Grand. tas supérieur : arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

Petit tas supérieur : arr[i]

L'idée de base du tri par tas est :

Construire la séquence à trié Il forme un grand tas supérieur. À ce stade, la valeur maximale de la séquence entière est le nœud racine en haut du tas. Échangez-le avec le dernier élément, la dernière valeur est alors la valeur maximale. Reconstruisez ensuite les n-1 éléments restants en un tas, de sorte que la plus petite valeur suivante de n éléments soit obtenue. Si vous exécutez ceci à plusieurs reprises, vous obtiendrez une séquence ordonnée

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal