importar java.util.Random;
/**
* Classificando classe de teste
*
* A classificação dos algoritmos de classificação é a seguinte: 1. Classificação por inserção (classificação por inserção direta, classificação por meia inserção, classificação por Hill 2. Classificação por troca (classificação por bolha, classificação rápida);
* 3. Classificação por seleção (classificação por seleção direta, classificação por heap);
*
* Em relação à escolha do método de classificação: (1) Se n for pequeno (como n≤50), a classificação por inserção direta ou seleção direta pode ser usada.
* Quando o tamanho do registro é pequeno, a classificação por inserção direta é melhor, caso contrário, como o número de registros movidos pela seleção direta é menor que o da inserção direta, a classificação por seleção direta é melhor;
* (2) Se o estado inicial do arquivo estiver basicamente em ordem (referindo-se à ordem positiva), deve-se usar inserção direta, bolha ou classificação rápida aleatória;
* (3) Se n for grande, um método de classificação com complexidade de tempo de O(nlgn) deve ser usado: classificação rápida, classificação por heap ou classificação por mesclagem.
*
*/
classe pública Classificar {
/**
* Método para inicializar array de teste
*
* @return um array inicializado
*/
public int[] createArray() {
Aleatório aleatório = new Aleatório();
int[] matriz = novo int[10];
for (int i = 0; i < 10; i++) {
array[i] = random.nextInt(100) - random.nextInt(100); // Gere dois números aleatórios e subtraia-os para garantir que haja números negativos nos números gerados.
}
System.out.println("==========sequência original==========");
printArray(matriz);
matriz de retorno;
}
/**
* Imprima os elementos do array no console
*
* @param fonte
*/
public void printArray(int[] dados) {
for (int i: dados) {
System.out.print(i + " ");
}
System.out.println();
}
/**
* Troque as posições dos dois elementos especificados no array
*
* @param dados
* @paramx
* @param y
*/
private void swap(int[] dados, int x, int y) {
temperatura interna = dados[x];
dados[x] = dados[y];
dados[y] = temp;
}
/**
* Bubble sort ---- um tipo de classificação de troca
* Método: compare dois elementos adjacentes e troque-os, se necessário. Após a conclusão de cada ciclo, o maior elemento é classificado por último (como classificar de pequeno para grande). O próximo ciclo realizará operações semelhantes em outros números.
* Desempenho: número de comparações O(n^2),n^2/2; número de trocas O(n^2),n^2/4;
*
* @param dados
* Array a ser classificado
* @param sortType
* Tipo de classificação
* @retornar
*/
public void bubbleSort(int[] dados, String sortType) {
if (sortType.equals("asc")) { // Classificação positiva, de pequeno a grande
//Número de rodadas de comparação
for (int i = 1; i < data.length; i++) {
// Compare dois números adjacentes e o número maior aparecerá.
for (int j = 0; j < data.length - i; j++) {
if (dados[j] > dados[j + 1]) {
//Troca dois números adjacentes
trocar(dados, j, j + 1);
}
}
}
} else if (sortType.equals("desc")) { // Classifica na ordem inversa, do maior para o menor
//Número de rodadas de comparação
for (int i = 1; i < data.length; i++) {
// Compare dois números adjacentes e o número maior aparecerá.
for (int j = 0; j < data.length - i; j++) {
if (dados[j] <dados[j + 1]) {
//Troca dois números adjacentes
trocar(dados, j, j + 1);
}
}
}
} outro {
System.out.println("O tipo de classificação que você digitou está errado!");
}
printArray(data); // Mostra o valor do array após a classificação por bolha
}
/**
* Método de classificação por seleção direta ---- um tipo de classificação por seleção
* Método: Em cada passagem, o menor (ou maior) elemento é selecionado dos elementos de dados a serem classificados e a ordem é colocada no final da matriz classificada até que todos os elementos de dados a serem classificados sejam organizados.
* Desempenho: Número de comparações O(n^2),n^2/2
* Número de trocas O(n),n
* O número de trocas é muito menor que o da classificação por bolha. Como a troca requer mais tempo de CPU do que a comparação, a classificação por seleção é mais rápida do que a classificação por bolha.
* Mas quando N é relativamente grande, o tempo de CPU necessário para comparação domina, então o desempenho neste momento não é muito diferente daquele do tipo bolha, mas é sem dúvida mais rápido.
*
* @param dados
* Array a ser classificado
* @param sortType
* Tipo de classificação
* @retornar
*
*/
public void selectSort(int[] dados, String sortType) {
if (sortType.equals("asc")) { // Classificação positiva, de pequeno a grande
índice interno;
for (int i = 1; i < data.length; i++) {
índice = 0;
for (int j = 1; j <= data.length - i; j++) {
if (dados[j] > dados[índice]) {
índice = j;
}
}
//Troca os dois números na posição data.length-i e índice (valor máximo)
swap(dados, data.length - i, índice);
}
} else if (sortType.equals("desc")) { // Classifica na ordem inversa, do maior para o menor
índice interno;
for (int i = 1; i < data.length; i++) {
índice = 0;
for (int j = 1; j <= data.length - i; j++) {
if (dados[j] <dados[índice]) {
índice = j;
}
}
//Troca os dois números na posição data.length-i e índice (valor máximo)
swap(dados, data.length - i, índice);
}
} outro {
System.out.println("O tipo de classificação que você digitou está errado!");
}
printArray(data); // Mostra o valor do array após a classificação por seleção direta
}
/**
*
* Classificação de inserção
*
* Método: Inserir um registro em uma lista ordenada ordenada (possivelmente uma lista vazia), obtendo assim uma nova lista ordenada com o número de registros aumentado em 1.
* Desempenho: número de comparações O(n^2),n^2/4
* Número de cópias O(n),n^2/4
* O número de comparações é a média entre os dois primeiros, e a cópia requer menos tempo de CPU do que a troca, portanto, o desempenho é mais que o dobro do da classificação por bolha e mais rápido do que a classificação por seleção.
*
* @param dados
* Array a ser classificado
* @param sortType
* Tipo de classificação
*/
public void insertSort(int[] dados, String sortType) {
if (sortType.equals("asc")) { // Classificação positiva, de pequeno a grande
//Número de rodadas de comparação
for (int i = 1; i < data.length; i++) {
//Garante que os primeiros números i+1 estejam classificados
for (int j = 0; j <i; j++) {
if (dados[j] > dados[i]) {
//Troca os dois números nas posições j e i
trocar(dados, i, j);
}
}
}
} else if (sortType.equals("desc")) { // Classifica na ordem inversa, do maior para o menor
//Número de rodadas de comparação
for (int i = 1; i < data.length; i++) {
//Garante que os primeiros números i+1 estejam classificados
for (int j = 0; j <i; j++) {
if (dados[j] <dados[i]) {
//Troca os dois números nas posições j e i
trocar(dados, i, j);
}
}
}
} outro {
System.out.println("O tipo de classificação que você digitou está errado!");
}
printArray(data); //Sai o valor do array após ordenação por inserção
}
/**
*
* Método para reverter um array
*
* @param dados
* matriz de origem
*/
público void reverso(int[] dados) {
comprimento interno = data.length;
int temp = 0;//variável temporária
for (int i = 0; i < comprimento / 2; i++) {
temperatura = dados[i];
dados[i] = dados[comprimento - 1 - i];
dados[comprimento - 1 - i] = temp;
}
printArray(data); //Sai o valor para o array convertido
}
/**
*
* Classificação rápida
*
* A classificação rápida usa a estratégia de dividir e conquistar para dividir uma sequência (lista) em duas subsequências (sublistas).
*
*As etapas são:
* 1. Escolha um elemento da sequência, chamado "pivot",
* 2. Reordene a sequência 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 ser colocado em qualquer lado). Após esta divisão, o dado está na sua posição final. Isso é chamado de operação de partição.
* 3. Classifique recursivamente a submatriz de elementos menor que o valor base e a submatriz de elementos maior que o valor base.
*
* O caso inferior da recursão é quando o tamanho do array é zero ou um, ou seja, ele sempre foi ordenado. Embora continue recorrendo, esse algoritmo sempre terminará, pois a cada iteração (iteração), ele moverá pelo menos um elemento para sua posição final.
*
* @param dados
* Array a ser classificado
* @param baixo
* @param alto
* @see SortTest#qsort(int[], int, int)
* @see SortTest#qsort_desc(int[], int, int)
*
*/
public void quickSort(int[] dados, String sortType) {
if (sortType.equals("asc")) { // Classificação positiva, de pequeno a grande
qsort_asc(dados, 0, data.length - 1);
} else if (sortType.equals("desc")) { // Classifica na ordem inversa, do maior para o menor
qsort_desc(dados, 0, data.length - 1);
} outro {
System.out.println("O tipo de classificação que você digitou está errado!");
}
}
/**
*
* Implementação específica de classificação rápida, classificação na ordem correta
*
* @param dados
* @param baixo
* @param alto
*/
private void qsort_asc(int dados[], int baixo, int alto) {
int eu, j, x;
if (low <high) { // Esta condição é usada para encerrar a recursão
eu = baixo;
j = alto;
x = dados[i];
enquanto (eu < j) {
enquanto (i < j && dados[j] > x) {
j--; // Encontre o primeiro número menor que x da direita para a esquerda
}
se (eu < j) {
dados[i] = dados[j];
eu++;
}
enquanto (i <j && dados[i] <x) {
i++; // Encontre o primeiro número maior que x da esquerda para a direita
}
se (eu < j) {
dados[j] = dados[i];
j--;
}
}
dados[i] = x;
qsort_asc(dados, baixo, i - 1);
qsort_asc(dados, i + 1, alto);
}
}
/**
*
* Implementação específica de classificação rápida, classificação em ordem inversa
*
* @param dados
* @param baixo
* @param alto
*
*/
private void qsort_desc(int dados[], int baixo, int alto) {
int eu, j, x;
if (low <high) { // Esta condição é usada para encerrar a recursão
eu = baixo;
j = alto;
x = dados[i];
enquanto (eu < j) {
enquanto (i <j && dados[j] <x) {
j--; // Encontre o primeiro número menor que x da direita para a esquerda
}
se (eu < j) {
dados[i] = dados[j];
eu++;
}
enquanto (i < j && dados[i] > x) {
i++; // Encontre o primeiro número maior que x da esquerda para a direita
}
se (eu < j) {
dados[j] = dados[i];
j--;
}
}
dados[i] = x;
qsort_desc(dados, baixo, i - 1);
qsort_desc(dados, i + 1, alto);
}
}
/**
*
* Pesquisa binária pela posição de um inteiro específico em uma matriz de inteiros (recursiva)
*
* A lista linear de pesquisa deve ser uma lista ordenada
*
* @paramdataset
* @paramdata
* @parambeginIndex
* @paramendIndex
* @returnindex
*
*/
public int binarySearch(int[] conjunto de dados, int data, int beginIndex,int endIndex) {
int midIndex = (beginIndex + endIndex) >>> 1; // Equivalente a mid = (low + high)
// / 2, mas a eficiência será maior
if (dados < conjunto de dados[beginIndex] || dados > conjunto de dados[endIndex] || inícioIndex > endIndex)
retornar -1;
if (dados <conjunto de dados[midIndex]) {
retornar pesquisabinária(conjunto de dados, dados, startIndex, midIndex - 1);
} else if (dados > conjunto de dados[midIndex]) {
retornar pesquisabinária(conjunto de dados, dados, midIndex + 1, endIndex);
} outro {
retornar índice médio;
}
}
/**
*
* Pesquisa binária pela posição de um inteiro específico em uma matriz de inteiros (não recursiva)
*
* A lista linear de pesquisa deve ser uma lista ordenada
*
* @paramdataset
* @paramdata
* @returnindex
*
*/
public int binarySearch(int[] conjunto de dados, dados int) {
int índiceInício = 0;
int endIndex = conjunto de dados.comprimento - 1;
int índice médio = -1;
if (dados < conjunto de dados[beginIndex] || dados > conjunto de dados[endIndex] || inícioIndex > endIndex)
retornar -1;
while (beginIndex <= endIndex) {
midIndex = (beginIndex + endIndex) >>> 1; // Equivalente a midIndex =
// (beginIndex +
//endIndex)/2, mas a eficiência será maior
if (dados <conjunto de dados[midIndex]) {
endIndex = midIndex - 1;
} else if (dados > conjunto de dados[midIndex]) {
começarIndex = midIndex + 1;
} outro {
retornar índice médio;
}
}
retornar -1;
}
public static void main(String[] args) {
Classificar sortTest = new Sort();
int[] array = sortTest.createArray();
System.out.println("==========Após classificação por bolha (ordem positiva)==========");
sortTest.bubbleSort(array, "asc");
System.out.println("==========Após classificação por bolha (ordem inversa)==========");
sortTest.bubbleSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========Depois de reverter a matriz==========");
sortTest.reverse(matriz);
array = sortTest.createArray();
System.out.println("==========Após a classificação da seleção (ordem positiva)==========");
sortTest.selectSort(array, "asc");
System.out.println("==========Após a classificação da seleção (ordem inversa)==========");
sortTest.selectSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========Após classificação por inserção (sequência positiva)==========");
sortTest.insertSort(array, "asc");
System.out.println("==========Após classificação de inserção (ordem inversa)==========");
sortTest.insertSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========Após classificação rápida (ordem positiva)==========");
sortTest.quickSort(array, "asc");
sortTest.printArray(matriz);
System.out.println("==========Após classificação rápida (ordem inversa)==========");
sortTest.quickSort(array, "desc");
sortTest.printArray(matriz);
System.out.println("==========Pesquisa binária no array==========");
System.out.println("O número que você está procurando está em" + sortTest.binarySearch(array, 74)
+ "assentos. (Subscrito calculado a partir de 0)");
}
}