Prenez d'abord un entier D1 plus petit que n comme premier incrément, et divisez tous les enregistrements dans le fichier en groupes de D1. Tous les enregistrements avec des multiples de distance DL sont placés dans le même groupe. Tout d'abord, insérez directement le tri dans chaque groupe; alors, prenez le deuxième incrément D2 <D1 et répétez le groupe et le tri ci-dessus jusqu'à l'incrément DT = 1 (dt <dt-l <;… <d2 <d1), c'est-à-dire, c'est-à-dire, Tous les enregistrements sont placés dans le même groupe et triés directement.
Cette méthode est essentiellement une méthode d'insertion de regroupement.
Schématique:
code source
La copie de code est la suivante:
Package com.zc.ManyThread;
/ **
*
* @author je suis
*
* /
classe publique ShellSort {
public static int count = 0;
public static void shellort (int [] data) {
// Calculez la valeur H maximale
int h = 1;
while (h <= data.length / 3) {
H = H * 3 + 1;
}
while (h> 0) {
pour (int i = h; i <data.length; i + = h) {
if (data [i] <data [i - h]) {
int tmp = data [i];
int j = i - h;
while (j> = 0 && data [j]> tmp) {
data [j + h] = data [j];
j - = h;
}
data [j + h] = tmp;
imprimer (données);
}
}
// Calculez la valeur H suivante
h = (h - 1) / 3;
}
}
Public Static Void Print (int [] data) {
for (int i = 0; i <data.length; i ++) {
System.out.print (données [i] + "/ t");
}
System.out.println ();
}
public static void main (String [] args) {
int [] data = new int [] {4, 3, 6, 2, 1, 9, 5, 8, 7};
imprimer (données);
shellSort (data);
imprimer (données);
}
}
Résultats en cours:
Le tri des coquilles est instable, son surcharge d'espace est également O (1) et la surcharge de temps est estimée entre O (N3 / 2) et O (N7 / 6).