Сначала возьмите целое число D1 меньше n в качестве первого приращения и разделите все записи в файле на группы D1. Все записи с несколькими расстояниями DL помещаются в одну и ту же группу. Сначала напрямую вставьте сортировку в каждую группу; Все записи размещены в одной и той же группе и отсортируются напрямую.
Этот метод по сути является методом вставки группировки.
Схема:
исходный код
Кода -копия выглядит следующим образом:
пакет com.zc.manythread;
/**
*
* @author я
*
*/
открытый класс Shellsort {
Public Static Int Count = 0;
public static void shellsort (int [] data) {
// Рассчитайте максимальное значение H
int h = 1;
while (h <= data.length / 3) {
H = H * 3 + 1;
}
while (h> 0) {
для (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;
}
данные [j + h] = tmp;
print (data);
}
}
// Рассчитайте следующее значение H
H = (H - 1) / 3;
}
}
public static void print (int [] data) {
для (int i = 0; i <data.length; i ++) {
System.out.print (data [i] + "/t");
}
System.out.println ();
}
public static void main (string [] args) {
int [] data = new int [] {4, 3, 6, 2, 1, 9, 5, 8, 7};
print (data);
ShellSort (данные);
print (data);
}
}
Результаты работы:
Сортировка оболочки нестабильна, его пространственные накладные расходы также являются O (1), и по оценкам, накладные расходы между O (N3/2) и O (N7/6).