class ShellSort {
public static int[] shellSort(int[] array) {
int N = array.length;
// determine the initial h value
int h = 1;
while (h < N / 3)
h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
while (h >= 1) {
// h-sort the array
for (int i = h; i < array.length; i++) {
// do insertion sort for h-sized array
for (int j = i; j >= h && array[j] < array[j - h]; j -= h)
swap(array, j, j - h);
}
h = h / 3; // reverse the h-size
}
return array;
}
/*
* swaps data elements between 2 indexes of an array
*/
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main
(String args
[]){ ShellSort sSort = new ShellSort();
int[] array = { 77, 99, 44, 55, 22, 88, 11, 0, 66, 33 };
int[] sortedArray = sSort.shellSort(array);
for (int i = 0; i < array.length; i++)
System.
out.
println(sortedArray
[i
]);
}
}
Y2xhc3MgU2hlbGxTb3J0IHsKCiAgICBwdWJsaWMgc3RhdGljIGludFtdIHNoZWxsU29ydChpbnRbXSBhcnJheSkgewoJCWludCBOID0gYXJyYXkubGVuZ3RoOwoJCQoJCS8vIGRldGVybWluZSB0aGUgaW5pdGlhbCBoIHZhbHVlCgkJaW50IGggPSAxOwoJICAgIHdoaWxlIChoIDwgTiAvIDMpIAoJICAgIAloID0gMyAqIGggKyAxOyAvLyAxLCA0LCAxMywgNDAsIDEyMSwgMzY0LCAxMDkzLCAuLi4KCSAgICAKCSAgICB3aGlsZSAoaCA+PSAxKSB7CgkgICAgCS8vIGgtc29ydCB0aGUgYXJyYXkKCSAgICAJZm9yIChpbnQgaSA9IGg7IGkgPCBhcnJheS5sZW5ndGg7IGkrKykgewoJICAgIAkJLy8gZG8gaW5zZXJ0aW9uIHNvcnQgZm9yIGgtc2l6ZWQgYXJyYXkKCSAgICAJCWZvciAoaW50IGogPSBpOyBqID49IGggJiYgYXJyYXlbal0gPCBhcnJheVtqIC0gaF07IGogLT0gaCkKCSAgICAJCQlzd2FwKGFycmF5LCBqLCBqIC0gaCk7CgkgICAgCX0KCSAgICAJCgkgICAgCWggPSBoIC8gMzsgLy8gcmV2ZXJzZSB0aGUgaC1zaXplCgkgICAgfQoJICAgIAoJICAgIHJldHVybiBhcnJheTsKCX0KCQoJLyoKCSAqIHN3YXBzIGRhdGEgZWxlbWVudHMgYmV0d2VlbiAyIGluZGV4ZXMgb2YgYW4gYXJyYXkKCSAqLwoJcHJpdmF0ZSBzdGF0aWMgdm9pZCBzd2FwKGludFtdIGFycmF5LCBpbnQgaSwgaW50IGopIHsKCQlpbnQgdGVtcCA9IGFycmF5W2ldOwoJCWFycmF5W2ldID0gYXJyYXlbal07CgkJYXJyYXlbal0gPSB0ZW1wOwoJfQkKICAgIAogICAgcHVibGljIHN0YXRpYyB2b2lkICBtYWluKFN0cmluZyBhcmdzW10pewogICAgCVNoZWxsU29ydCBzU29ydCA9IG5ldyBTaGVsbFNvcnQoKTsKICAgIAlpbnRbXSBhcnJheSA9IHsgNzcsIDk5LCA0NCwgNTUsIDIyLCA4OCwgMTEsIDAsIDY2LCAzMyB9OwogICAgCWludFtdIHNvcnRlZEFycmF5ID0gc1NvcnQuc2hlbGxTb3J0KGFycmF5KTsKICAgIAlmb3IgKGludCBpID0gMDsgaSA8IGFycmF5Lmxlbmd0aDsgaSsrKQogICAgICAgIAlTeXN0ZW0ub3V0LnByaW50bG4oc29ydGVkQXJyYXlbaV0pOwogICAgCQogICAgfQp9