Complexidade do tempo
Média: O (NLGN)
Pior caso: o (n*n), ocorre quando os dados já estão no estado de classificação.
1. Selecione um valor a [i] dos dados como referência
2. Tomando um [i] como referência, divida os dados em 2 partes: P1 e P2. Todos os dados em p1≤a [i], todos os dados em p2> a [i] e os dados se tornam {{p1} {a [i]} {p2}}
3. Repita as etapas acima com P1 e P2 até que apenas 1 dados sejam deixados em cada parte.
4. Os dados são classificados em ordem crescente
Exemplo básico:
Dados brutos:
{3, 9, 8, 5, 2, 1, 6} Etapa 1: selecione os primeiros dados: 3
Etapa 2: Divida os dados em 2 partes, o lado esquerdo é ≤3 e o lado direito é maior que> 3:
{2,1} {3} {9,8,5,6} Etapa 3: Repita as etapas acima para cada parte até que haja apenas 1 dados em cada parte:
{2,1} => {1} {2} {9, 8, 5, 6} => {8, 5, 6} {9} => {5, 6} {8} {9} => {5} {6} {8} {9}} Etapa 4: Os dados são classificados em ordem crescente:
{1} {2} {3} {5} {6} {8} {9}Os dados no programa geralmente são armazenados em uma matriz. Tomando uma variedade de tipos int como exemplo, você pode escrever as etapas acima em um protótipo da função Quicksort:
QuickSort (int Begin, int end) {// Begin é o valor do índice dos primeiros dados da matriz, o final é o valor do índice dos últimos dados da matriz +1 // se houver apenas 1 dados ou 0 dados, o programa retorna se (Begin == end || BEGIN == (END-1)) Return; int p = in [BEGIN]; // p é os dados de referência selecionados, selecione os primeiros dados int a = comece +1; // a como o valor do índice da linha de divisão de dados em duas partes int b = a; // b é o valor do índice dos dados a serem comparados para (; b <end; b ++) {// compare os dados na matriz com os dados de referência na sequência se (em [b] <p) {// se os dados <referência, mova-o para a esquerda se (a == a == continue;} // Se os dados já estiverem à esquerda, eles não moverão int temp = em [a]; // mova os dados para a esquerda em [a] = em [b]; em [b] = temp; a ++; // mova a linha divisória direita}} em [BEGIN] = em [a-1]; // chame o valor de referência para o meio de 2 conjuntos de dados em [a-1] = p; if (a-1> BEGIN) {// Se houver dados à esquerda, repita as etapas acima QuickSort (BEGIN, A); } if (end-1> a) {// Se houver dados à direita, repita as etapas acima QuickSort (a, final); } retornar; // Se não houver dados} Otimização de algoritmo
Pode -se dizer que o algoritmo de classificação rápido acima é a classificação rápida mais básica, pois não leva em consideração nenhum dado de entrada. No entanto, é fácil encontrar as falhas desse algoritmo: é quando nossos dados de entrada são basicamente ordenados ou até completamente ordenados, o algoritmo degenera na classificação de bolhas, não mais O (nn), mas O (n^2).
A causa raiz é que, em nossa implementação de código, começamos apenas a partir da primeira matriz por vez. Se usarmos o "três cabeçalhos", ou seja, os valores medianos de arr [baixa], arr [alta], arr [(baixa+alta)/2] como registro do pivô, o desempenho da classificação rápida no pior cenário pode ser bastante aprimorada. No entanto, ainda não podemos melhorar seu desempenho para O (n) no caso ordenado pela matriz. Também existem maneiras de melhorar o desempenho do tempo de classificação rápida no pior cenário em graus variados.
Além disso, a classificação rápida requer uma pilha recursiva, que geralmente não é muito profunda e está no nível de log (n). No entanto, se o comprimento das duas matrizes divididas por vez for severamente desequilibrado, na pior das hipóteses, a profundidade da pilha aumentará para O (n). Neste momento, a complexidade espacial trazida pelo espaço da pilha não pode ser ignorada. Se a sobrecarga de variáveis adicionais for adicionada, poderá até atingir uma complexidade espacial aterrorizante (n^2) aqui. Portanto, a pior complexidade espacial de classificação rápida não é um valor fixo e pode nem estar no mesmo nível.
Para resolver esse problema, podemos comparar os comprimentos das extremidades após cada divisão e classificar as seqüências curtas primeiro (o objetivo é acabar com essas pilhas primeiro para liberar espaço), o que pode reduzir a profundidade máxima para o nível O (n).
Aqui estão três idéias de otimização para classificação rápida:
Para pequenas matrizes, a classificação de inserção pode ser usada para evitar chamadas recursivas. Por exemplo, quando (hi <= lo + m), você pode ir para inserir classificação.
Use a mediana de um subarray para cortar a matriz. Isso resulta em melhor fatiamento, mas ao custo de calcular a mediana.
Se a matriz contiver um grande número de elementos repetidos, poderá ser usado o fatiamento de três vias. Divida a matriz em três partes, correspondendo aos elementos da matriz menor que, igual a e maior que os elementos de corte, respectivamente. A implementação do código é a seguinte:
private estático void sort1 (int [] a, int lo, int hi) {if (hi <= lo) return; int lt = lo, i = lo + 1, gt = hi; int v = a [lo]; while (i <= gt) {if (a [i] <v) {swap (a, lt ++, i ++); } else if (a [i]> v) {swap (a, i, gt--); } else {i ++; } classificar (a, lo, lt - 1); classificar (a, gt + 1, oi); }}