希尔排序真的比插入排序快吗？

Question

问题遇到的现象和发生背景

对插入排序和希尔排序进行同样的10万次测试，插入排序耗时约19s，希尔排序耗时约30s

插入排序代码：

public static void insertionSort(int[]arr){
        if (arr == null || arr.length == 0) return;
        int N = arr.length-1;
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j > 0; j--) {
                if (arr[j] < arr[j-1]){
                    swap(arr,j,j-1);
                }
            }
        }
    }

希尔排序代码：

public static  void shellSort(int[]arr){
        if (arr == null || arr.length < 2 ) return;
        int N = arr.length;
        int h = N/2;
        while(h >= 1){
            for (int i = h; i <N; i ++){
                for (int j = i; j>= h; j-=h){
                    if (arr[j] <arr[j-h]){
                        swap(arr,j,j-h);
                    }
                }
            }

            h /= 2;


        }

测试insertionSort

 public static void main(String[] args) {
        int testTime = 100000;
        int maxSize = 1000, maxvale = 200;
        System.out.println("开始测试insertionSort");
        Long start = System.currentTimeMillis();

        for (int i = 0; i < testTime; i++) {
            int[]arr = generateRandomArr(maxSize,maxvale);
            int[] copyArr1 = copyArr(arr);
            int[] copyArr2 = copyArr(arr);
            Arrays.sort(copyArr2);
            Sort.insertionSort(copyArr1);
            for (int i1 = 0; i1 < arr.length; i1++) {
               if (copyArr1[i1] != copyArr2[i1]) {
                   System.out.println("出错啦");
                   System.out.println("originArr = "+ Arrays.toString(arr));
                   System.out.println("Arrays.sort = "+ Arrays.toString(copyArr2));
                   System.out.println("afterSort   = "+ Arrays.toString(copyArr1));
                   break;
               }

            }
        }
        System.out.println("测试结束");
        long time = System.currentTimeMillis()-start;
        System.out.println("测试用时： " + time);

    }

public static void main(String[] args) {
        int testTime = 100000;
        int maxSize = 1000, maxvale = 200;
        System.out.println("开始测试shellSort");
        Long start = System.currentTimeMillis();
        for (int i = 0; i < testTime; i++) {
            int[]arr = generateRandomArr(maxSize,maxvale);
            int[] copyArr1 = copyArr(arr);
            int[] copyArr2 = copyArr(arr);
            Arrays.sort(copyArr2);
            ShellSort.shellSort(copyArr1);
            for (int i1 = 0; i1 < arr.length; i1++) {
               if (copyArr1[i1] != copyArr2[i1]) {
                   System.out.println("出错啦");
                   System.out.println("originArr = "+ Arrays.toString(arr));
                   System.out.println("Arrays.sort = "+ Arrays.toString(copyArr2));
                   System.out.println("afterSort   = "+ Arrays.toString(copyArr1));
                   break;
               }

            }
        }
        System.out.println("测试结束");
        long time = System.currentTimeMillis()-start;
        System.out.println("测试用时： " + time);


    }

操作环境、软件版本等信息

win10，IntelliJ Idea

Answer 1

chatgpt:希尔排序和插入排序的性能取决于输入数据的特征。对于某些特定的数据集，希尔排序可以比插入排序更快，但在其他情况下，插入排序可能更快。

希尔排序的主要优点在于，它可以提高插入排序的性能，因为它会首先对数据进行较大的跨度排序，从而使数据变得更加有序。这种增量排序的方法可以在一定程度上减少插入排序中的比较和交换操作，从而提高性能。

然而，希尔排序的性能还受到增量序列的选择的影响。不同的增量序列可能导致不同的性能表现。此外，在排序过程中需要不断地移动元素，因此在实现时需要使用适当的数据结构来提高性能。