O Quick Sort é uma espécie de troca de divisão proposta por Crahoare em 1962. A idéia básica desse método é:
1. Primeiro, pegue um número da sequência como o número de referência.
2. No processo de particionamento, coloque todos os números maiores que esse número à sua direita e todos os números menores ou iguais à esquerda.
3. Repita o segundo passo para os intervalos esquerdo e direito até que haja apenas um número em cada intervalo.
O algoritmo tem uma idéia clara, mas se o valor do limite não for bem tratado durante o processo de divisão de intervalo, é fácil causar erros. A seguir, há dois pensamentos mais claros para orientar a redação do código da divisão de intervalo.
O primeiro tipo de pensamento é o chamado pensamento do método de escavação de pit. A seguir, é para analisar o processo do método de escavação de pit analisando um exemplo:
Tomando uma matriz como exemplo, pegue o primeiro número no intervalo como o número de referência.
Inicialmente, esquerda = 0; direita = 9; X = a [esquerda] = 72
Como o número em um [0] foi salvo para x, ele pode ser entendido como cavando um orifício na matriz A [0], e outros dados podem ser preenchidos aqui.
Comece da direita e procure um número de <= x. Obviamente, quando à direita = 8, se as condições forem atendidas, desenterre um [8] e preencha -o no poço anterior a [esquerda]. Tal poço a [0] é resolvido, mas um novo poço a [8] é formado. O que devo fazer? Simples, encontre o número para preencher o poço a [8]. Desta vez, comece da esquerda e encontre um número maior que X. Quando esquerda = 3, atenda às condições, escavar um [3] e preencha -o no poço anterior a [direita];
A matriz se torna:
Repita as etapas acima e a matriz final se tornará o seguinte formulário:
Pode -se observar que os números antes de [5] são menores que ele, e os números após a [5] são maiores que ele. Preencha X no poço de A [5] e os dados se tornam:
Portanto, repita as etapas acima para os dois sub-intervalos A [0… 4] e A [6… 9].
Resumo do número de orifícios cavados
1. I = l; j = r; Desenhe o número de referência para formar o primeiro poço a [i].
2. J-------do lado de trás, encontre o número menor do que ele, desenterre esse número e preencha o poço anterior a [i].
3. I ++ encontra um número maior que ele da frente para trás e, depois de encontrá -lo, desenterre esse número e preencha -o no poço anterior a [j].
4. Repita as etapas 2 e 3 até i == j, e preencha o número de referência em um [i].
Siga este método de partição, o código Java é rapidamente classificado da seguinte forma:
Public Class Partition { / ** * Com base na divisão base, a pequena está à esquerda e a grande está à direita, e toda a sequência não é necessária para ser ordenada * * @param ary * @param base * / STATION VOID STILH (int [] ary, int base) {int left = 0; int certo = ary.length - 1; int leftpoint = esquerda, direita Point = direita; while (true) {// Divida na esquerda e direita para a direita ao mesmo tempo para comparar, da esquerda para a direita, enquanto (LeftPoint <direita && ary [leftpoint ++] <base); // LeftPoint é maior que o direito ou ary [LeftPoint]> Paradas de base em loop while (Rightpoint> = esquerda && ary [Rightpoint--]> base); // no contrário system.out.println ("o índice que precisa ser trocado à esquerda:" + (leftpoint-1)); System.out.println ("O índice que precisa ser trocado à direita:"+ (Rightpoint+ 1)); // Os dois índices que não atendem às condições são obtidos acima, ou seja, os dois índices que precisam ser trocados se (LeftPoint - 1 <ponto direito + 1) {// Swap (ary, Leftpoint - 1, Rightpoint + 1); Util.printary (ary); leftpoint = esquerda; Rightpoint = Right; } else {break; }}} troca de void estático privado (int [] ary, int a, int b) {int temp = ary [a]; ary [a] = ary [b]; ary [b] = temp; } public static void main (string [] args) {int [] ary = util.geReRiTarray (10); System.out.println ("Sequência original:"); Util.printary (ary); classificar (ary, 5); System.out.println ("classificado:"); Util.printary (ary); }} resultado:
Original sequence: [2, 8, 4, 3, 7, 5, 1, 9, 0, 6] Index to exchange on the left: 1 Index to exchange on the right: 8 [2, 0, 4, 3, 7, 5, 1, 9, 8, 6] Index to exchange on the left: 4 Index to exchange on the right: 6 [2, 0, 4, 3, 1, 5, 7, 9, 8, 6] Index to exchange on the left: 5 Index to exchange on the right: 5 After Classificação: [2, 0, 4, 3, 1, 5, 7, 9, 8, 6]
Outro pensamento orientador da divisão de intervalo:
Use o primeiro elemento da matriz como o valor do intervalo, participe -o do segundo elemento até que o resultado mostrado na figura seja formado.
Em seguida, troque os valores do limite direito e T do intervalo L <t para formar o seguinte resultado:
Dessa forma, você pode escrever um código de classificação rápido da seguinte maneira:
public void qsort (int array [], int esquerd, int direito) {if (esquerda <direita) {int key = array [esquerda]; int alto = certo; int low = esquerda+1; while (true) {while (Low <= High && Array [Low] <= key) Low ++; while (baixo <= alto && Array [alto]> = key) alto--; IF (baixa> alta) quebra; troca (matriz, baixa, alta); } troca (matriz, esquerda, alta); PrintArray (Array); Qsort (Array, Esquerda, High-1); Qsort (Array, High+1, à direita); }}