Esiste un algoritmo di ordinamento denominato "ordinamento binario"? Come unire ordinamento, selezione sort o altri tipi di ordinamento, esiste un ordinamento binario?Esiste un algoritmo di "ordinamento binario"?
C'è this e c'è binary insertion sort. I due sono piuttosto simili. Sono entrambi algoritmi di tempo quadratici (O(n^2)).
Entrambi gli algoritmi eseguono il numero di confronti O(n log n), ma in pratica dovresti spostare anche gli elementi, il che renderebbe l'intero algoritmo quadratico.
Voglio scrivere un algoritmo (questo non è un lavoro a casa) e voglio prima ordinare e poi usare binary serach per trovare due elementi che la loro somma uguale a 9 e il tempo di esecuzione di questo algoritmo dovrebbe essere theta (nlogn) posso usare l'unisci sort per l'ordinamento e la ricerca binaria per la ricerca? – user355002
grazie anche per il tuo aiuto !!! – user355002
@ matin1234: nope.but puoi rimuovere i numeri più di 8. e ordinare i numeri a sinistra, loop da su e giù (è un po 'strano) per i numeri che risultano una somma di nine.it è O (n). – Behrooz
Ci sono alcuni tipi che comportano la suddivisione in due parti (unire sort), ma non credo che esista un ordinamento chiamato esattamente "ordinamento binario".
Non abbiamo un algoritmo di ordinamento binario, ma abbiamo una ricerca binaria su un array ordinato.
Non sai cosa stai cercando, ma se stai cercando un algoritmo di ordinamento binario adatto, allora vuoi essere consapevole delle tue esigenze. Ogni algoritmo ha i suoi punti di forza e di debolezza.
Ad esempio, si sta cercando un algoritmo che fornisca prestazioni medie più veloci (ad esempio ricerca su heap) o prestazioni del caso peggiore (operazione più lenta) (ad esempio albero binario bilanciato). Alcuni sono lenti se si deve anche iterare da un oggetto a quello successivo. Se stai facendo molte operazioni casuali probabilmente sei più interessato alle prestazioni medie, ma se hai la necessità di assicurarti che qualsiasi operazione sia più veloce di X millisecondi, allora potresti volere un algoritmo diverso. Alcuni possono essere lento se si sempre l'aggiunta di elementi alla fine della raccolta ecc
in modo da avere un Google per parole chiave come:
Tutto si riduce a quello che ti serve.
Un ordinamento binario è un algoritmo molto veloce che prevede il test di bit. Ha un singolo passaggio per ogni bit nell'oggetto ordinabile. Per ogni passaggio, se il bit è impostato, l'elemento ordinabile è impilato su un'estremità del buffer. Se il bit non è impostato, l'elemento viene impilato all'altra estremità del buffer. L'avvio dell'ordinamento al bit meno significativo e la gestione dei bit successivi in ordine ascendente comporterà la lista ordinata. Ne scrissi uno di questi all'inizio dell'8086 nel 1983 per il Dipartimento di educazione scozzese. Steve Pitts
Sembra un ordinamento digitale. Vuoi ulteriori chiarimenti su come l'algo che descrivi differisce da radix? – javadba
Il JDK utilizza un "ordinamento binario" per gli array < dimensione 32 all'interno del suo metodo Arrays.sort(). Ecco il codice da JDK7
private static void binarySort(Object[] a, int lo, int hi, int start) {
assert lo <= start && start <= hi;
if (start == lo)
start++;
for (; start < hi; start++) {
@SuppressWarnings("unchecked")
Comparable<Object> pivot = (Comparable) a[start];
// Set left (and right) to the index where a[start] (pivot) belongs
int left = lo;
int right = start;
assert left <= right;
/*
* Invariants:
* pivot >= all in [lo, left).
* pivot < all in [right, start).
*/
while (left < right) {
int mid = (left + right) >>> 1;
if (pivot.compareTo(a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
assert left == right;
/*
* The invariants still hold: pivot >= all in [lo, left) and
* pivot < all in [left, start), so pivot belongs at left. Note
* that if there are elements equal to pivot, left points to the
* first slot after them -- that's why this sort is stable.
* Slide elements over to make room for pivot.
*/
int n = start - left; // The number of elements to move
// Switch is just an optimization for arraycopy in default case
switch (n) {
case 2: a[left + 2] = a[left + 1];
case 1: a[left + 1] = a[left];
break;
default: System.arraycopy(a, left, a, left + 1, n);
}
a[left] = pivot;
}
}
Questa è una parte di TimSort Algo. Ma sembra sfocato. qualcuno può spiegarlo? Come si differenzia con l'ordinamento di fusione? –
Non ci può essere una sorta binario, ma la matrice reale ordinato dovrebbe essere in senso opposto. (Vale a dire, diciamo che si desidera ordinare un array di interi in ordine crescente ... per questo , è necessario disporre l'array effettivo in ordine decrescente.)
L'ordinamento heap è un algoritmo di ordinamento concettualizzando un albero binario e eseguendo il set-up e quindi il set-down su di esso. Può essere fatto sul posto.
Forse intendi [Ricerca binaria] (http://en.wikipedia.org/wiki/Binary_search_algorithm)?In ogni caso, la tua domanda non fornisce informazioni sufficienti per risposte significative. Si prega di prendere il vostro tempo e riscrivere la domanda per includere informazioni utili/dettagli. –
@Paul @pst Non vedo i tuoi problemi nel comprendere la risposta: esiste un algoritmo di ordinamento popolare il cui nome è "ordinamento binario"? –
@Dave: stavo rispondendo alla domanda originale, che era ancora più breve e più vaga della versione attuale - ripercorri le modifiche. –