a copy isn’t as time-consuming as a swap
Confrontiamo una copia in uno scambio:
int[] a = ...
int idx = ...
// copy:
a[idx] = a[idx + 1];
// swap:
int temp = a[idx];
a[idx] = a[idx + 1];
a[idx + 1] = temp;
Swap assegna una variabile temporanea esegue e tre copie, una dall'array alla variabile temporanea, una da un indice all'array a un'altra e una dalla variabile temporanea all'array. Pertanto uno swap è almeno 3 volte più costoso di una copia.
Spostare elementi in un array (al contrario dei bit di spostamento in un tipo intero primitivo) è costoso perché viene ripetuto copiando:
for (int i = shiftEnd - 1; i >= shiftStart; i--) {
a[i + 1] = a[i];
}
Puoi vedere qui quando (shiftEnd - shiftStart) > 3 a turno eseguirà più operazioni di copia rispetto a uno scambio.
Diamo un'occhiata allo stesso esempio con una serie di puntatori agli oggetti invece di primitive int:
Object[] a = ...
// copy the pointer to an object from one array element to another
a[idx] = a[idx + 1];
// swap the pointer to an object between array elements
Object temp = a[idx];
a[idx] = a[idx + 1];
a[idx + 1] = temp;
Noterai che queste operazioni sono esattamente le stesse sia che si tratti di oggetti primitivi o primitivi. La versione List è più costosa a causa del overhead di chiamata metodo di accesso all'elenco. La maggior parte delle implementazioni di List utilizza matrici multiple per consentire il ridimensionamento dell'elenco che è più costoso rispetto all'utilizzo di una matrice primitiva a lunghezza fissa singola.