Introduction
La complexité de Mergesort pour les entrées qui ont été triées à l'envers est O (n ^ 2), et TimSort est généré en optimisant Mergesort pour cette situation. La complexité moyenne est n * o (log n), le meilleur cas est O (n), et le pire des cas est n * o (log n). Et Timsort est un type de stabilité. L'idée est de partitionner d'abord la colonne triée, puis de fusionner les partitions, ce qui ressemble à l'étape Mergesort, mais il existe des optimisations pour les données inverses et à grande échelle.
Idée d'optimisation du tri de fusion
Il existe plusieurs méthodes d'optimisation pour la fusion du tri:
Comme le tri rapide, vous pouvez utiliser le tri insert ou sélectionner le tri pour les petits tableaux pour éviter les appels récursifs.
Avant que Merge () ne soit appelé, vous pouvez déterminer si un [mid] est inférieur ou égal à un [MID + 1]. Si c'est le cas, il n'est pas nécessaire de fusionner, le tableau est déjà commandé. La raison est très simple. Étant donné que les deux sous-réseaux sont déjà commandés, un [mid] est la valeur maximale du premier sous-réseau, et un [MID + 1] est la valeur minimale du deuxième sous-réseau. Lorsque A [mid] <= a [mid + 1], le tableau est commandé dans son ensemble.
Pour gagner du temps à copier des éléments sur le tableau auxiliaire, les rôles du réseau d'origine et du tableau auxiliaire peuvent être échangés à chaque niveau de l'appel récursif.
Le processus de fusion dans la méthode Merge () doit déterminer si I et J ont franchi la frontière, c'est-à-dire la moitié du bord a été utilisée. Une autre façon de supprimer le code qui détecte si la moitié du côté a été épuisée. L'étape spécifique consiste à copier la seconde moitié du tableau A [] à Aux [] dans l'ordre descendant, puis à fusionner des deux extrémités. Pour les tableaux {1,2,3} et {2,3,5}, le premier sous-réseau est copié comme d'habitude, et le second est copié de derrière à l'avant, et l'élément final de Aux [] est {1,2,3,5,3,2}. L'inconvénient de cette méthode est qu'il fait que le tri de fusion devient un tri instable. L'implémentation du code est la suivante:
void fusiter (int [] a, int lo, int mid, int hi, int [] aUx) {for (int k = lo; k <= mid; k ++) {aux [k] = a [k];} pour (int k = mid + 1; k <= hi; k ++) {aUx [k] = a [hi - k + mid + 1];} int i = lo, j = hi; // des deux extrémités au milieu pour (int k = lo; k <= hi; k ++) if (aux [i] <= aux [j]) a [k] = aux [i ++]; else a [k] = Aux [J--];}Les étapes de Timsort
Partition
L'idée de partitionnement est de scanner le tableau une fois et d'utiliser la séquence positive continue (si elle est triée de l'ordre croissant, alors la séquence positive est une séquence ascendante), ou [strictement] (pour assurer la stabilité de l'algorithme de tri) en tant que partition (RUN). S'il s'agit d'une séquence inverse, inversez les éléments de la partition. Par exemple
1, 2, 3, 6, 4, 5, 8, 6, 4 Les résultats de partitionnement sont
[1,2,3,6], [4,5,8], [6,4]
Puis inverser la séquence inverse
[1,2,3,6], [4,5,8], [4,6]
fusionner
Considérez un exemple extrême, par exemple, les longueurs des partitions sont de 10000, 10, 1000, 10, 10 et 10, bien sûr, nous espérons fusionner 10 10 en 20, 20 et 1000 en 1020 en premier. Si nous fusions de gauche à droite, nous utiliserons le tableau 10000 et la combinaison de petits nombres à chaque fois, ce qui est trop cher. Nous pouvons donc utiliser une stratégie pour optimiser l'ordre des fusions.
Exemple
Prenant ComparableTeMsort.Sort () dans Java à titre d'exemple, une pile d'exécution est utilisée pour déterminer si elle doit être fusionnée.
if (nreminging <min_merge) {int initrunlen = CountunandMakeascending (a, lo, hi); BinarySort (a, lo, hi, lo + initrunlen); retour; }Trier moins que min_merge (32) et trier directement avec l'insertion binaire après le partitionnement
int minrun = minrunLength (nReMinging); faire {// découvrez la position de départ de la partition suivante, et retournez également la séquence inverse int runlen = CountrunandMakeascending (a, lo, hi); // Assurez-vous que les exécutions dans la pile de course sont supérieures à Minrun. Si la partition actuelle est trop petite, retirez les éléments de l'arrière pour maquiller si (runlen <minrun) {int force = nReMinging <= minrun? Nreminging: Minrun; BinarySort (a, lo, lo + force, lo + runlen); runlen = force; } // Mettez la course dans la pile de run ts.pushrun (lo, runlen); // jugera s'il doit être fusionné. Je commence par le haut de la pile et je sais qu'il ne peut pas être fusionné // 1. runlen [i - 3]> runlen [i - 2] + runlen [i - 1] // 2. runlen [i - 2]> runlen [i - 1] ts.mergecollapse (); lo + = runlen; Nreminging - = Runlen; } while (nReMinging! = 0); // fusionner toutes les exécutions restantes pour terminer le tri ASSERT LO == HI; // fusionner le run restant t.mergeforceCollapse (); affirmer t.stacksize == 1;En regardant une fonction plus importante
/ *** Si les longueurs des 2 derniers exécutions sont ajoutées plus longtemps que la précédente, utilisez l'exécution en position centrale et que l'exécution avec une longueur avant et arrière plus courte pour fusionner * Si les longueurs des 2 dernières exécutions sont ajoutées plus courtes que la précédente, fusionnez les deux exécutions * / Private Void MergeCollapse () {While (StackSize> 1) {int n = stackSize - 2; if (n> 0 && runlen [n-1] <= runlen [n] + runlen [n + 1]) {if (runlen [n - 1] <runlen [n + 1]) n--; fusion (n); } else if (runlen [n] <= runlen [n + 1]) {Mergeat (n); } else {break; // invariant est établi}}