Introdução
A complexidade de Mergesort para entradas que foram classificadas ao reverso é O (n^2), e o timsort é gerado pela otimização de Mergesort para essa situação. A complexidade média é n*o (log n), o melhor caso é o (n) e o pior caso é n*o (log n). E Timsort é um tipo de estabilidade. A idéia é dividir a coluna classificada primeiro e depois mesclar as partições, que parecem iguais à etapa de mesclagem, mas existem algumas otimizações para dados reversos e em larga escala.
Ideia de otimização de classificação de mesclagem
Existem vários métodos de otimização para a classificação de mesclagem:
Como a classificação rápida, você pode usar a classificação Inserir ou selecionar classificação para pequenas matrizes para evitar chamadas recursivas.
Antes de ser chamado Merge (), você pode determinar se um [MID] é menor ou igual a um [MID+1]. Nesse caso, não há necessidade de se fundir, a matriz já está encomendada. O motivo é muito simples. Como os dois subarrays já estão ordenados, um [MID] é o valor máximo do primeiro subarray e um [MID+1] é o valor mínimo do segundo subarray. Quando A [MID] <= A [MID+1], a matriz é ordenada como um todo.
Para economizar tempo, copiar elementos para a matriz auxiliar, os papéis da matriz original e a matriz auxiliar podem ser trocados em cada nível da chamada recursiva.
O processo de mesclagem no método Merge () precisa determinar se eu e J cruzei o limite, ou seja, metade da borda foi usada. Outra maneira de remover o código que detecta se uma metade do lado foi esgotada. A etapa específica é copiar a segunda metade da matriz A [] para aux [] em ordem descendente e depois se fundir de ambas as extremidades. Para matrizes {1,2,3} e {2,3,5}, o primeiro subarray é copiado como de costume e o segundo é copiado por trás para a frente, e o elemento final em aux [] é {1,2,3,5,3,2}. A desvantagem desse método é que ele torna a classificação de mesclagem se tornar uma classificação instável. A implementação do código é a seguinte:
Merge void (int [] a, int lo, int mid, int hi, int [] aux) {for (int k = lo; k <= mid; k ++) {Aux [k] = a [k];} para (int k = mid+1; k <= hi; k ++) {Aux [k] = a [hi - k+1]; // das duas extremidades para o meio para (int k = lo; k <= hi; k ++) se (aux [i] <= aux [j]) a [k] = aux [i ++]; caso contrário, [k] = aux [j--];}Etapas de Timsort
Partição
A idéia de particionamento é digitalizar a matriz uma vez e usar a sequência positiva contínua (se for classificada ordem ascendente, a sequência positiva é uma sequência ascendente) ou [estritamente] (para garantir a estabilidade do algoritmo de classificação) como uma partição (execução). Se for uma sequência reversa, inverta os elementos da partição. Por exemplo
1, 2, 3, 6, 4, 5, 8, 6, 4 Os resultados de particionamento são
[1,2,3,6], [4,5,8], [6,4]
Em seguida, reverta a sequência reversa
[1,2,3,6], [4,5,8], [4,6]
mesclar
Considere um exemplo extremo, por exemplo, os comprimentos das partições são 10000, 10, 1000, 10, 10 e 10, é claro que esperamos mesclar 10 10 em 20, 20 e 1000 em 1020 primeiro. Se nos fundirmos da esquerda para a direita, usaremos a matriz 10000 e a combinação de números pequenos a cada vez, o que é muito caro. Portanto, podemos usar uma estratégia para otimizar a ordem das mescladas.
Exemplo
Tomando comparabableTimsort.sort () em java como exemplo, uma pilha de execução é usada para determinar se deve ser mesclada.
if (nremaining <min_merge) {int initRunlen = countryndmakeascending (a, lo, oi); bináriosort (a, lo, hi, lo + initrunlen); retornar; }Classifique menos que min_merge (32) e classifique diretamente com a inserção binária após a partição
int minrun = minrunlength (nremaining); Do {// Descubra a posição inicial da próxima partição e também vira a sequência reversa int runlen = countrymandmakeascending (a, lo, hi); // Certifique -se de que as corridas na pilha de corrida sejam maiores que o MinRun. Se a partição atual for muito pequena, retire os elementos da parte traseira para compensar if (runlen <minrun) {int force = nremaining <= minrun? NREMING: Minrun; bináriosort (a, lo, lo + force, lo + runlen); runlen = force; } // coloque a pilha de execução ts.pushrun (lo, runlen); // julga se deve ser mesclado. Começo no topo da pilha e sei que ela não pode ser mesclada // 1. runlen [i - 3]> runlen [i - 2] + runlen [i - 1] // 2. runlen [i - 2]> runlen [i - 1] ts.MerGecollapse (); lo += runlen; nremaining -= runlen; } while (nremaining! = 0); // mescla todas as execuções restantes para concluir a classificação de classificação afirmam lo == oi; // mescla a execução restante ts.mergeforceCollapse (); afirmar ts.stacksize == 1;Olhando para uma função mais importante
/ *** Se os comprimentos das últimas 2 execuções forem adicionadas mais longas que as anteriores, use a corrida na posição intermediária e a corrida com comprimentos mais curtos da frente e traseira para se fundir*se os comprimentos das últimas 2 execuções forem adicionadas mais curtas que as anteriores (pilhas> 1). if (n> 0 && runlen [n-1] <= runlen [n] + runlen [n + 1]) {if (runlen [n-1] <runlen [n + 1]) n--; mergeat (n); } else if (runlen [n] <= runlen [n + 1]) {mergeat (n); } else {break; // invariante está estabelecido}}