Insérer directement le tri
1 idée de tri:
Le record RI à tri est inséré dans les enregistrements déjà triés R1, R2, ..., R (N-1).
Pour une séquence aléatoire, à partir du deuxième élément, insérant l'élément dans la position correspondante dans l'élément avant lui. Les éléments avant qu'il ait été trié.
Premier ordre: insérez le deuxième élément dans la liste ordonnée dans l'ordre précédent (pour le moment, il n'y a qu'un seul élément dans le précédent, bien sûr, il est ordonné). Après cela, les deux premiers éléments de cette séquence sont ordonnés.
Deuxième tri: insérez le troisième élément dans la liste ordonnée de la longueur précédente 2 afin que les deux premiers éléments soient commandés.
Et ainsi de suite jusqu'à ce que le nième élément soit inséré dans la liste ordonnée de la longueur précédente (N-1).
2 Implémentation de l'algorithme:
// insérer directement le tri void Straight_insert_sort (int num [], int len) {int i, j, key; pour (j = 1; j <len; j ++) {key = num [j]; i = j-1; while (i> = 0 && num [i]> key) {num [i + 1] = num [i]; je--; } num [i + 1] = key; }}3 Analyse des performances:
3.1 Complexité de l'espace: Comme mentionné ci-dessus, une clé d'unité auxiliaire est utilisée et la complexité de l'espace est O (1)
3.2 Complexité du temps:
3.2.1 Meilleur cas: les enregistrements à tri sont déjà commandés, puis les trier en un seul voyage, les mots clés sont comparés une fois et les enregistrements sont déplacés deux fois. Tout le processus
Le nombre de comparaisons est
Le nombre de mouvements d'enregistrements est
Complexité du temps o (n)
3.2.2 Pire des cas: les enregistrements à tri sont déjà dans l'ordre inverse, puis les temps de comparaison des mots clés sont i (de I-1 à 0), et l'enregistrement se déplace (i + 2) fois. Tout le processus
Le nombre de comparaisons est
Le nombre de mouvements d'enregistrements est
Complexité du temps o (n ^ 2)
3.2.3 Complexité du temps moyen: o (n ^ 2)
3.3 Stabilité: stable
Pliez le tri à moitié inséré
1 idée de tri:
Sur la base du tri direct, les enregistrements à tri RI sont insérés dans les enregistrements déjà triés R1, R2, ..., R (N-1). Étant donné que les enregistrements R1, R2, ..., R (N-1) ont été triés, la "demi-recherche" peut être utilisée lors de la recherche de la position d'insertion.
2 Implémentation de l'algorithme:
// pliez à moitié insert le tri void binary_insert_sort (int num [], int len) {int i, j, key, bas, haut, mid; pour (i = 1; i <len; i ++) {key = num [i]; bas = 0; élevé = i-1; mid = (bas + haut) / 2; // Trouvez le point d'insertion, le point d'insertion final est faible tandis que (bas <= haut) {if (key <num [mid]) high = mid-1; sinon bas = mid + 1; mid = (bas + haut) / 2; } // Déplacer l'enregistrement pour (j = i; j> bas; j -) {num [j] = num [j-1]; } // insérer l'enregistrement num [Low] = key; }}3 Analyse des performances:
3.1 Complexité de l'espace: Comme mentionné ci-dessus, une clé d'unité auxiliaire est utilisée et la complexité de l'espace est O (1)
3.2 Complexité du temps: bien que la recherche à moitié finisse réduit le nombre d'enregistrements et de comparaisons, cela ne réduit pas le nombre de mouvements, donc la complexité temporelle est la même que l'algorithme de recherche directe.
3.2.1 Meilleur cas: complexité du temps O (n)
3.2.2 Pire des cas: complexité du temps O (n ^ 2)
3.2.3 Complexité du temps moyen: o (n ^ 2)
3.3 Stabilité: stable