// lista original desordenada
int[] lista = {8, 587, 5, 18, 9, 445, 37, 709, 687};
// definir a variável h do Knuth
int h = 1;
while (h < lista.length / 3) {
h = 3 * h + 1;
}
// aplicar o algoritmo ShellSort com a variável h
while (h >= 1) {
for (int i = h; i < lista.length; i++) {
int temp = lista[i];
int j;
for (j = i; j >= h && lista[j - h] > temp; j -= h) {
lista[j] = lista[j - h];
}
lista[j] = temp;
}
h = h / 3;
}
// imprimir a lista ordenada
for (int i = 0; i < lista.length; i++) {
System.out.println(lista[i]);
}