public class ShellSort {
public static void main(String[] args) {
int[] array = new int[]{5, 3, 9, 1, 6, 4, 10, 2, 8, 7, 15, 3, 2};
System.out.println("Before: " + Arrays.toString(array));
sort1(array);
System.out.println("After: " + Arrays.toString(array));
array = new int[]{5, 3, 9, 1, 6, 4, 10, 2, 8, 7, 15, 3, 2};
sort2(array);
System.out.println("After: " + Arrays.toString(array));
}
public static void sort1(int[] arr) {
int len = arr.length;
for (int gap = len / 2; gap > 0; gap /= 2) {
for (int j = 0; j <= len / gap; j++) {
for (int k = 0; (k + gap) < len; k += gap) {
if (arr[k] <= arr[k + gap]) {
continue;
}
swap(arr, k, k + gap);
}
}
}
}
public static void sort2(int[] arr) {
int gap = 1;
int len = arr.length;
while (gap < len / 3) {
gap = gap * 3 + 1;
}
for (; gap > 0; gap /= 3) {
for (int i = gap; i < len; i++) {
int tmp = arr[i];
int j;
for (j = i - gap; j >= 0 && arr[j] > tmp; j -= gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = tmp;
}
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}