Implementar pesquisa dicotômica
O método de pesquisa binária requer uma sequência ordenada na matriz. A pesquisa binária é mais do que a pesquisa linear: quanto mais elementos a matriz for, mais óbvia é a eficiência. A eficiência da pesquisa binária é expressa: o (log2n) n está na faixa de potência M de 2; portanto, o número máximo de pesquisas é M. log2n significa que a potência M de 2 é igual a n, omita a constante e abreviada como O (logn)
Se houver uma matriz ordenada de 200 elementos, o número máximo de pesquisas binárias:
2^7 = 128, 2^8 = 256, pode -se observar que o poder de 7 não pode atingir 200 e o poder de 8 inclui, portanto o número máximo de pesquisas é igual a 8
// loop, pesquisa binária estática int binária (int [] matriz, int data) {int start = 0; int end = array.length - 1; int mid = -1; while (start <= end) {System.out.println ("número de pesquisas"); MID = (Start + End) >>> 1; if (matriz [mid] <data) {start = mid + 1; } else if (array [mid]> dados) {end = mid - 1; } else {return mid; } System.out.println ("start ="+start+", end ="+end+", mid ="+mid); } retornar -1; } // Pesquisa binária recursiva Início inicial = 0, end = Array.Length - 1 estático int bininaresearch4Recursion (Array int [], int, int, int start, int end) {int mid = -1; System.out.println ("Número de pesquisas"); if (start> final) {return mid; } mid = (start + end) >>> 1; if (Array [MID] <data) {return binarySearch4Recursion (Array, Data, Mid + 1, End); } else if (array [mid]> data) {return binarySearch4Recursion (Array, Data, Start, Mid - 1); } else {return mid; }}Classificação de inserção dicotômica
Existe uma sequência a [0], a [1] ... a [n]; onde um [i-1] já está encomendado antes dele. Ao inserir um [i], use dicotomia para procurar a posição de uma eficiência de inserção [i]: o (n^2). Para seqüências iniciais basicamente ordenadas, a eficiência não é tão boa quanto a classificação de inserção direta; Para sequências aleatórias e desordenadas, a eficiência é maior que a classificação de inserção direta.
/** Bipartido (dobrado e metade) Classificação de inserção* Uma sequência a [0], a [1] ... a [n]; onde um [i-1] já está encomendado antes dele. Quando um [i] for inserido, use a dicotomia para procurar a posição de uma [i] inserção*/ classe pública BinaryInsertSort {public static void main (string [] args) {int len = 10; int [] ary = new int [len]; Aleatório aleatório = novo aleatório (); for (int j = 0; j <len; j ++) {ary [j] = aleatom.nextInt (1000); } binaryInsert (ary); / * * Análise de complexidade: na melhor das hipóteses, ou seja, todos foram classificados, não há necessidade de se mover corretamente. Neste momento, a complexidade do tempo é: O (n lg n) O pior caso é que toda a ordem reversa e, neste momento, a complexidade é O (n^2) * A complexidade do pior caso não pode ser melhorada para O (n | logn). */ // imprima o array printArray (ary); } / *** Inserir classificar* @param ary* / private estático void binaryInsert (int [] ary) {int setValuECount = 0; // classificação do segundo elemento da matriz, porque o primeiro elemento deve ser classificado para (int j = 1; j <ary.length; j ++) {// complexidade n // salve o valor atual int key = ary [j]; // ∆ use pesquisa binária para localizar a posição de inserção // int index = bininaresearchascc (ary, ary [j], 0, j - 1); // complexidade: o (logn) // int index = bininaresearchdesc (ary, [j], 0, J - 1); 1); // complexidade: o (logn) printArray (ary); System.out.println ("" +j +"índices a serem inseridos na posição:" +índice); // Insira o alvo na posição e mude o elemento para a direita da posição alvo, ao mesmo tempo para (int i = j; i> index; i-) {// complexidade, pior caso: (n-1)+(n-2)+...+n/2 = o (n^2) ary [i] = ary [i-1]; // i-1 <==> Index setValuEcount ++; } ary [index] = key; setValuECount ++; } System.out.println ("/n número de valores (setValuEcount) =====>" + setValuEcount); } /** * Binary search ascending recursion* * @param a ary * Given the sorted array to be looked up* @param target * Find the target* @param from * The starting point of the range of the current search* @param to * The return end point of the current search* @return Return the target in the array, where it should be in order*/ private static int binarySearchAsc(int[] ary, int target, int from, int to) {int range = para - de; // Se o intervalo for maior que 0, ou seja, há mais de dois elementos, continue a se separar se (intervalo> 0) {// selecione o bit intermediário int mid = (para + de) / 2; // Se o bit crítico não estiver satisfeito, continue pesquisando binário se (ary [mid]> alvo) {/ * * MID> alvo, regra ascendente, o alvo é menor e a posição deve ser trocada, isto é, o alvo está posicionado no meio do meio 1/ de acordo com a idéia de busca, do Mid-1, é considerado ordenado, para = Mid-1/ Return/ Return Binary Binarys; } else { / * * MID <destino, regra ascendente, o alvo é grande e nenhuma posição é trocada. A posição inicial para a busca de comparação deve ser MID + 1 */ Return binarySearchascc (ary, alvo, meio + 1, para); }} else {if (ary [de]> alvo) {// por exemplo, 5,4, o que é inserir é 4 retorno de; } else {retorna de + 1; }}} / *** Pesquisa binária Ordem descendente, recursiva* / private estático int bininaresearchDesc (int [] ary, int alvo, int, int para) {int range = para - de; if (intervalo> 0) {int mid = (de + a) >>> 1; if (ary [mid]> alvo) {return binarySearchDesc (ary, alvo, meio + 1, para); } else {return binarySearchDesc (ary, alvo, de, meados - 1); }} else {if (ary [de]> alvo) {// por exemplo, 5,4, o que deve ser inserido é 4 retorno de + 1; } else {retorna de; }}} / *** Pesquisa binária Ordem descendente, não recursiva* / private estático int binárioSearchDesc2 (int [] ary, int alvo, int de, int para) {// while (de <para) {for (; de <para;) {int mid = (de + a) >>> 1; if (ary [mid]> alvo) {de = MID + 1; } else {para = MID -1; }} // de <==> para; if (ary [de]> alvo) {// se 5,4, aquele a ser inserido é 4 retornar de + 1; } else {retorna de; }} private estático void PrintArray (int [] ary) {for (int i: ary) {System.out.print (i + ""); }}}Imprimir
918 562 442 531 210 216 931 706 333 132 A posição de inserção do elemento no primeiro índice é: 1 918 562 442 531 210 216 931 706 333 132 A posição da inserção do elemento no segundo Índice é: 2 918 562 42 42 42 42 42 52 52 52 52 52 52 53 53 53 52 53 53 53 233 333 52 52 53 233 33 233 33 23 213 333 333 132. A inserção do elemento no terceiro índice é: 2 918 562 531 442 210 216 931 706 333 132 A posição de inserção do elemento no quarto índice é: 4 918 562 531 442 210 216 931 706 333 132 A posição da inserção do o elemento do elemento 4416. 931 706 333 132 The position of insertion of the element on the sixth index is: 0 931 918 562 531 442 216 210 706 333 132 The position of insertion of the element on the seventh index is: 2 931 918 706 562 531 442 216 210 333 132 The position of insertion of the element on the eighth index is: 6 931 918 706 562 531 442 333 216 210 132 O local onde o elemento no 9º índice deve ser inserido é: 9
SetValuEcount =====> 24
931 918 706 562 531 442 333 216 210 132