Java希尔排序

电玩女神 2023-09-27 16:25 123阅读 0赞

/**
     * 希尔排序
     * 希尔排序是对插入排序的优化
     *
     * @author 小流慢影
     * @date 2023年3月21日
     */
    public class ShellSort {
    
        public static void main(String[] args) {
            int[] array = {5, 4, 3, 1, 2, 13, 12, 10, 11, 9, 7, 8, 6, 3, 5};
            System.out.println("原数组：" + Arrays.toString(array));
            shellSort(array);
            System.out.println("排序后数组：" + Arrays.toString(array));
        }
    
        /**
         * 希尔排序
         *
         * @param array 待排数组
         */
        private static void shellSort(int[] array) {
            // 取初始间隔为数组的长度
            int gap = array.length;
            // 当间隔为1时，就是最小间隔了，就不用再继续循环了
            while (gap != 1) {
                // 每次循环将间隔缩小
                gap = gap / 2;
                // 从0到间隔点之间的每个位置都要跨间隔（gap）进行插入排序
                for (int startIndex = 0; startIndex < gap; startIndex++) {
                    insertionSort(array, startIndex, gap);
                }
            }
        }
    
        /**
         * 插入排序
         * 具体插入排序的代码解释看插入排序博文
         * <a href="https://blog.csdn.net/qq_35893873/article/details/129664322">插入排序</a>
         *
         * @param array      数组
         * @param startIndex 开始下标
         * @param gap        间隔
         */
        private static void insertionSort(int[] array, int startIndex, int gap) {
            for (int gapStart = startIndex + gap; gapStart < array.length; gapStart = gapStart + gap) {
                for (int compareStart = gapStart - gap; compareStart >= 0; compareStart = compareStart - gap) {
                    if (array[compareStart + gap] < array[compareStart]) {
                        swap(array, compareStart, gap);
                    } else {
                        break;
                    }
                }
            }
        }
    
        /**
         * 比较
         *
         * @param array        数组
         * @param compareStart 比较开始的位置
         */
        public static void swap(int[] array, int compareStart, int gap) {
            int temp = array[compareStart];
            array[compareStart] = array[compareStart + gap];
            array[compareStart + gap] = temp;
        }
    }