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;

        // make it arr relatively sorted
        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;

        // len = 13, gap = 4
        while (gap < len / 3) {
            gap = gap * 3 + 1;
        }

        for (; gap > 0; gap /= 3) {
            for (int i = gap; i < len; i++) {
                // move arr[i] to proper position, the method is same with insertion sort
                int tmp = arr[i];

                int j;

                // assume gap = 4, compare arr[0] with arr[4]
                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;
    }
}
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 14:52:36

results matching ""

    No results matching ""