https://chikuwa-tech-study.blogspot.com/2021/05/java-shell-sort.html

ShellSort.java

public class ShellSort {

    private static int roundStepCount = 0;
    private static int allStepCount = 0;

    public static void sort(int[] data) {
        for (int gap = data.length / 2; gap > 0; gap /= 2) {
            for (int startIndex = 0; startIndex < gap; startIndex++) {
                insertionSort(data, startIndex, gap);
            }
            reportRoundEnd();
        }
        System.out.printf("總步驟數: %d\n", allStepCount);
    }

    private static void insertionSort(int[] array, int startIndex, int gap) {
        for (int currentIndex = startIndex + gap; currentIndex < array.length; currentIndex += gap) {
            int currentValue = array[currentIndex];
            int newIndex = lastIndexOfLowerOrEqualData(array, startIndex, currentIndex - gap, gap, currentValue) + gap;

            for (int i = currentIndex; i > newIndex; i -= gap) {
                roundStepCount++;
                array[i] = array[i - gap];
            }

            array[newIndex] = currentValue;
        }
    }

    private static int lastIndexOfLowerOrEqualData(int[] array, int startIndex, int endIndex, int gap, int value) {
        for (int i = endIndex; i >= startIndex; i -= gap) {
            roundStepCount++;
            if (array[i] <= value) {
                return i;
            }
        }
        return startIndex - gap;
    }
    
    private static void reportRoundEnd() {
        System.out.printf("回合步驟數: %d\n", roundStepCount);
        allStepCount += roundStepCount;
        roundStepCount = 0;
    }
}