estabilidade (estabilidade)
Um algoritmo de ordenação é estável, ou seja, quando existem dois registros iguais das chaves R e S, e R aparece antes de S na lista original, R também aparecerá antes de S na lista ordenada.
Classificação do algoritmo de classificação
Os mais comuns incluem inserção (classificação por inserção/classificação por colina), troca (classificação por bolha/classificação rápida), seleção (classificação por seleção), mesclagem (classificação por mesclagem), etc.
1. Classificação por inserção
A classificação por inserção (classificação por inserção) funciona construindo uma sequência ordenada. Para dados não classificados, ela verifica de trás para frente na sequência classificada para encontrar a posição correspondente e inseri-la. Na implementação da classificação por inserção, geralmente é usada a classificação no local (ou seja, a classificação que usa apenas O(1) espaço extra, portanto, durante o processo de digitalização de trás para frente, é necessário deslocar repetidamente e gradualmente o). elementos classificados para trás, fornecendo espaço de inserção para o elemento mais recente.
De modo geral, a classificação por inserção é implementada em arrays usando in-place. O algoritmo específico é descrito a seguir:
A partir do primeiro elemento, os elementos podem ser considerados ordenados.
Obtenha o próximo elemento e digitalize de trás para frente na sequência classificada de elementos.
Se o elemento (classificado) for maior que o novo elemento, mova o elemento para a próxima posição.
Repita a etapa 3 até encontrar uma posição onde o elemento classificado seja menor ou igual ao novo elemento.
Depois de inserir o novo elemento nessa posição.
Repita as etapas 2 a 5.
Copie o código do código da seguinte forma:
public static void insertSort(int[] dados) {
for (int índice = 1; índice <data.length; índice++) {
chave int = dados[índice];
posição interna = índice;
//desloca valores maiores para a direita
while (posição > 0 && dados[posição - 1] > tecla) {
dados[posição] = dados[posição - 1];
posição--;
}
dados[posição] = chave;
}
}
2. Classificação de colinas
Shell Sort é um tipo de classificação por inserção. É uma melhoria no algoritmo de classificação por inserção direta. Este método também é chamado de redução da classificação incremental, porque DL. Shell foi nomeado após ter sido proposto em 1959.
A classificação Hill propõe um método aprimorado baseado nas duas propriedades de classificação por inserção a seguir:
A ordenação por inserção é altamente eficiente ao operar em dados quase ordenados, ou seja, pode atingir a eficiência da ordenação linear.
Mas a classificação por inserção geralmente é ineficiente porque a classificação por inserção só pode mover dados um bit por vez.
Copie o código do código da seguinte forma:
static <E estende Comparable<? super E>> void shellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) por Knuth, 1973>: 1, 4, 13, 40, 121, . ..
para (; h >= 1; h /= 3)
for (int i = h; i < a.size(); i++)
para (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Coleções.swap(a, j, jh);
}
3. Classificação de bolhas
Bubble Sort (Bubble Sort, traduzido de Taiwan como: Bubble Sort ou Bubble Sort) é um algoritmo de classificação simples. Ele percorre repetidamente a sequência a ser classificada, comparando dois elementos por vez e trocando-os se estiverem na ordem errada. O trabalho de visitar o array é repetido até que não sejam necessárias mais trocas, o que significa que o array foi ordenado. O nome desse algoritmo vem do fato de que elementos menores irão lentamente "flutuar" até o topo do array por meio de troca.
O algoritmo de classificação por bolha funciona da seguinte maneira:
Compare os elementos adjacentes e, se o primeiro for maior que o segundo, troque os dois.
Faça o mesmo para cada par de elementos adjacentes, começando com o primeiro par e terminando com o último par, ponto em que o último elemento deve ser o maior número.
Repita as etapas acima para todos os elementos, exceto o último.
Continue repetindo as etapas acima para cada vez menos elementos até que não haja mais pares de números para comparar.
Copie o código do código da seguinte forma:
public static void bubbleSort(int[] dados) {
temperatura interna = 0;
for (int i = data.length - 1; i > 0; --i) {
booleano isSort = falso;
for (int j = 0; j <i; ++j) {
if (dados[j + 1] <dados[j]) {
temperatura = dados[j];
dados[j] = dados[j + 1];
dados[j + 1] = temperatura;
isSort = verdadeiro;
}
}
// Se ocorrer uma troca em um loop interno, continua a comparação; se nenhuma troca ocorrer em um loop interno, ela será considerada classificada.
se (!isSort)
quebrar;
}
}
4. Classificação rápida
Quicksort é uma melhoria na classificação por bolha. Proposto por CAR Hoare em 1962. Sua ideia básica é dividir os dados a serem classificados em duas partes independentes por meio de uma classificação. Todos os dados em uma parte são menores do que todos os dados na outra parte e, em seguida, usar este método para separar rapidamente as duas partes dos dados. . Classificação, todo o processo de classificação pode ser executado recursivamente, de modo que todos os dados se tornem uma sequência ordenada.
A classificação rápida usa a estratégia de dividir e conquistar para dividir uma lista em duas sublistas.
As etapas são:
Escolher um elemento da sequência é chamado de "pivô".
Reordene a matriz para que todos os elementos menores que o valor base sejam colocados na frente da base e todos os elementos maiores que o valor base sejam colocados atrás da base (o mesmo número pode ir para qualquer um dos lados). Após a saída desta partição, a base estará no meio da sequência. Isso é chamado de operação de partição.
Classifique recursivamente a submatriz de elementos menor que o valor base e a submatriz de elementos maior que o valor base.
Copie o código do código da seguinte forma:
/*
* implementos mais eficientes para quicksort.
* use o valor mediano esquerdo, central e direito (@see #median()) para o pivô, e
* o loop interno mais eficiente para o núcleo do algoritmo.
*/
classe pública Quicksort {
público estático final int CUTOFF = 11;
/**
* algoritmo de classificação rápida.
*
* @param arr um array de itens comparáveis.
*/
public static <T estende Comparable<?
quickSort(arr, 0, arr.length - 1);
}
/**
*obter a mediana da esquerda, centro e direita.
* ordene-os e oculte o pivô colocando-o no final do array <br />.
*
* @param arr um array de itens comparáveis.
* @param deixou o índice mais à esquerda do subarray <br />.
* @param right o índice mais à direita do subarray.<br />
* @returnT
*/
public static <T estende Comparable<? super T>> T median(T[] arr, int left, int right) {
int centro = (esquerda + direita) / 2;
if (arr[esquerda].compareTo(arr[centro]) > 0)
swapRef(arr, esquerda, centro);
if (arr[esquerda].compareTo(arr[direita]) > 0)
swapRef(arr,esquerda,direita);
if (arr[centro].compareTo(arr[direita]) > 0)
swapRef(arr, centro, direita);
swapRef(arr, centro, direita - 1);
return arr[direita - 1];
}
/**
* método interno para classificar o array com algoritmo de classificação rápida.
*
* @param arr um array de itens comparáveis.
* @param saiu do índice mais à esquerda do subarray <br />.
* @param right o índice mais à direita do subarray <br />.
*/
private static <T estende Comparable<? super T>> void quickSort(T[] arr, int left, int right) {
if (esquerda + CUTOFF <= direita) {
//encontra o pivô
Pivô T = mediana (arr, esquerda, direita);
//inicia o particionamento
int i = esquerda, j = direita - 1;
para (;;) {
while (arr[++i].compareTo(pivot) < 0);
while (arr[--j].compareTo(pivot) > 0);
se (eu <j)
swapRef(arr, i, j);
outro
quebrar;
}
// troca a referência pivot de volta para a coleção pequena.
swapRef(arr, i, direita - 1);
quickSort(arr, left, i - 1); // classifica a pequena coleção.
quickSort(arr, i + 1, right); // classifica a coleção grande.
} outro {
// se o número total for menor que CUTOFF usamos ordenação por inserção
// em vez disso (porque é muito mais eficiente).
Sort(arr, inserção esquerda, direita);
}
}
/**
* método para trocar referências em um array.<br />
*
* @param arr um array de objetos <br />
* @param idx1 o índice do primeiro elemento.
* @param idx2 o índice do segundo elemento.
*/
public static <T> void swapRef(T[] arr, int idx1, int idx2) {
T tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
/**
* método para classificar um subarray do início ao fim com classificação por inserção
*algoritmo.
*
* @param arr um array de itens comparáveis.
* @param inicia a posição inicial.
* @param finaliza a posição final.
*/
public static <T estende Comparable<? super T>> void insertSort(T[] arr, int start, int end) {
int eu;
for (int j = início + 1; j <= fim; j++) {
T tmp = arr[j];
for (i = j; i > start && tmp.compareTo(arr[i - 1]) < 0; i--) {
arr[i] = arr[i - 1];
}
arr[i] = tmp;
}
}
private static void printArray(Integer[] c) {
for (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
public static void main(String[] args) {
Dados inteiros[] = {10, 4, 9, 23, 1, 45, 27, 5, 2};
System.out.println("bubbleSort...");
printArray(dados);
classificação rápida(dados);
printArray(dados);
}
}
5. Classificação de seleção
A classificação por seleção é um algoritmo de classificação simples e intuitivo. Veja como funciona. Primeiro, encontre o menor (grande) elemento na sequência não classificada e armazene-o no início da sequência classificada. Em seguida, continue a encontrar o menor (grande) elemento dos elementos não classificados restantes e, em seguida, coloque-o no final da sequência. sequência ordenada. E assim por diante até que todos os elementos estejam classificados.
Como cada processo de determinação de elementos terá um subprocesso de seleção do valor mínimo, as pessoas chamam isso de classificação por seleção.
Por exemplo, na sequência 5 8 5 2 9, sabemos que o primeiro elemento 5 será trocado por 2 na primeira passagem. Então a ordem relativa dos dois 5s na sequência original será destruída, então a ordenação por seleção é. algoritmo de classificação não estável.
Copie o código do código da seguinte forma:
public static void selectSort(int[] dados) {
int minIndex = 0;
temperatura interna = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; //O índice mínimo da matriz de dados da área não ordenada
for (int j = i + 1; j < data.length; j++) { // Encontre os menores dados na área não ordenada e salve seu subscrito da matriz
if (dados[j] <dados[minIndex]) {
índicemin = j;
}
}
if (minIndex != i) { // Se a posição mínima da área não ordenada não for o primeiro dado padrão, troque-o.
temperatura = dados[i];
dados[i] = dados[índicemin];
dados[índicemin] = temp;
}
}
}
6. Mesclar classificação
Merge sort é um algoritmo de classificação eficaz baseado em operações de mesclagem. Este algoritmo é uma aplicação muito típica que usa o método dividir e conquistar (Divide and Conquer).
O processo de operação de mesclagem é o seguinte:
Solicite espaço para que seu tamanho seja a soma das duas sequências classificadas. Esse espaço é usado para armazenar a sequência mesclada.
Defina dois ponteiros, as posições iniciais são as posições iniciais das duas sequências classificadas.
Compare os elementos apontados pelos dois ponteiros, selecione o elemento relativamente pequeno e coloque-o no espaço de mesclagem e mova o ponteiro para a próxima posição.
Repita a etapa 3 até que um ponteiro chegue ao final da sequência.
Copia todos os elementos restantes da outra sequência diretamente no final da sequência mesclada.
Copie o código do código da seguinte forma:
public static int[] mergeSort(int[] arr) {//Mesclar classificação--recursão
if (arr. comprimento == 1) {
retornar chegada;
}
int metade = arr.comprimento/2;
int[] arr1 = novo int[metade];
int[] arr2 = novo int[arr.length - metade];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mesclarSort(arr1);
arr2 = mesclarSort(arr2);
retornar mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {//Mesclar sub-rotina de classificação
int[] resultado = novo int[arr1.length + arr2.length];
int eu = 0;
int j = 0;
int k = 0;
enquanto (verdadeiro) {
se (arr1[i] <arr2[j]) {
resultado[k] = arr1[i];
if (++i > arr1.length - 1) {
quebrar;
}
} outro {
resultado[k] = arr2[j];
if (++j > arr2.length - 1) {
quebrar;
}
}
k++;
}
for (; i < arr1.length; i++) {
resultado[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
resultado[++k] = arr2[j];
}
resultado de retorno;
}
Código completo (exceto QuickSort)
Copie o código do código da seguinte forma:
pacote com.clzhang.sample.thinking;
importar java.util.*;
/**
* Implementação Java de vários algoritmos de classificação comuns
* @autor acer
*
*/
classe pública CommonSort {
/**
* O algoritmo específico de classificação por inserção é descrito a seguir:
* 1. A partir do primeiro elemento, o elemento pode ser considerado classificado
* 2. Retire o próximo elemento e digitalize de trás para frente na sequência de elementos classificados
* 3. Se o elemento (classificado) for maior que o novo elemento, mova o elemento para a próxima posição
* 4. Repita a etapa 3 até encontrar a posição onde o elemento classificado é menor ou igual ao novo elemento
* 5. Após inserir o novo elemento nesta posição
* 6. Repita as etapas 2 a 5
*/
public static void insertSort(int[] dados) {
for (int índice = 1; índice <data.length; índice++) {
chave int = dados[índice];
posição interna = índice;
//desloca valores maiores para a direita
while (posição > 0 && dados[posição - 1] > tecla) {
dados[posição] = dados[posição - 1];
posição--;
}
dados[posição] = chave;
}
}
/**
* Classificação de colinas, consulte a Wikipedia para ideias de implementação de algoritmos adequadas para um grande número de operações de classificação;
*/
static <E estende Comparable<? super E>> void shellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) por Knuth, 1973>: 1, 4, 13, 40, 121, . ..
para (; h >= 1; h /= 3)
for (int i = h; i < a.size(); i++)
para (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Coleções.swap(a, j, jh);
}
/**
* A operação do algoritmo de classificação por bolha é a seguinte:
* 1. Compare elementos adjacentes. Se o primeiro for maior que o segundo, troque os dois.
* 2. Faça o mesmo trabalho para cada par de elementos adjacentes, desde o primeiro par no início até o último par no final. Neste ponto, o último elemento deve ser o maior número.
* 3. Repita as etapas acima para todos os elementos, exceto o último.
* 4. Continue repetindo as etapas acima para cada vez menos elementos até que não haja pares de números para comparar. [1]
*/
public static void bubbleSort(int[] dados) {
temperatura interna = 0;
for (int i = data.length - 1; i > 0; --i) {
booleano isSort = falso;
for (int j = 0; j <i; ++j) {
if (dados[j + 1] <dados[j]) {
temperatura = dados[j];
dados[j] = dados[j + 1];
dados[j + 1] = temperatura;
isSort = verdadeiro;
}
}
// Se ocorrer uma troca em um loop interno, continua a comparação; se nenhuma troca ocorrer em um loop interno, ela será considerada classificada.
se (!isSort)
quebrar;
}
}
/**
* A ideia básica da classificação por seleção é:
* 1. Durante o processo de percorrer o array, se i representa o número de sequência atual que precisa ser classificado, você precisa encontrar o valor mínimo entre os restantes [i+1...n-1].
* 2. Em seguida troque o valor mínimo encontrado pelo valor apontado por i.
* Como cada processo de determinação de elementos terá um subprocesso de seleção do valor mínimo, as pessoas chamam isso de classificação por seleção.
* @param dados
*/
public static void selectSort(int[] dados) {
int minIndex = 0;
temperatura interna = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; //O índice mínimo da matriz de dados da área não ordenada
for (int j = i + 1; j < data.length; j++) { // Encontre os menores dados na área não ordenada e salve seu subscrito da matriz
if (dados[j] <dados[minIndex]) {
índicemin = j;
}
}
if (minIndex != i) { // Se a posição mínima da área não ordenada não for o primeiro dado padrão, troque-o.
temperatura = dados[i];
dados[i] = dados[índicemin];
dados[índicemin] = temp;
}
}
}
/**
* O processo de operação de mesclagem é o seguinte:
* 1. Solicite espaço para que seu tamanho seja a soma das duas sequências classificadas. Este espaço é usado para armazenar a sequência mesclada.
* 2. Defina dois ponteiros, as posições iniciais são as posições iniciais das duas sequências classificadas.
* 3. Compare os elementos apontados pelos dois ponteiros, selecione o elemento relativamente pequeno e coloque-o no espaço de mesclagem e mova o ponteiro para a próxima posição
* 4. Repita a etapa 3 até que um ponteiro chegue ao final da sequência
* 5. Copie todos os elementos restantes da outra sequência diretamente para o final da sequência mesclada
*/
public static int[] mergeSort(int[] arr) {//Mesclar classificação--recursão
if (arr. comprimento == 1) {
retornar chegada;
}
int metade = arr.comprimento/2;
int[] arr1 = novo int[metade];
int[] arr2 = novo int[arr.length - metade];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mesclarSort(arr1);
arr2 = mesclarSort(arr2);
retornar mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {//Mesclar sub-rotina de classificação
int[] resultado = novo int[arr1.length + arr2.length];
int eu = 0;
int j = 0;
int k = 0;
enquanto (verdadeiro) {
se (arr1[i] <arr2[j]) {
resultado[k] = arr1[i];
if (++i > arr1.length - 1) {
quebrar;
}
} outro {
resultado[k] = arr2[j];
if (++j > arr2.length - 1) {
quebrar;
}
}
k++;
}
for (; i < arr1.length; i++) {
resultado[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
resultado[++k] = arr2[j];
}
resultado de retorno;
}
private static void printArray(int[] c) {
for (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
public static void main(String []args){
int[] dados = {10,4,9,23,1,45,27,5,2};
System.out.println("bubbleSort...");
int[] a = dados.clone();
printArray(a);
bolhaSort(a);
printArray(a);
System.out.println("selectSort...");
int[] b = dados.clone();
printArray(b);
selecioneClassificar(b);
printArray(b);
System.out.println("inserçãoSort...");
int[] c = dados.clone();
printArray(c);
inserçãoSort(c);
printArray(c);
System.out.println("shellSort...");
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<data.length;i++)
lista.add(dados[i]);
System.out.println(lista);
shellSort(lista);
System.out.println(lista);
System.out.println("mergeSort...");
int[] d = dados.clone();
printArray(d);
printArray(mergeSort(d));
}
}