关于希尔排序的一点简单看法

妖狐艹你老母 2022-02-05 01:43 215阅读 0赞

其实只是有一点问题的是关于Knuth间隔序列的问题，之前希尔建议初期间距为n/2，简单的把排序分成两半，对于部分数据的分析可能会使复杂度降低到O(N^2) ，这并不比插入排序的效率高，所以我们在使用希尔排序的时候选择间隔数字互质的情况更好，虽然Knuth间隔序列算是一个可以通用的间隔序列，但是在不同的数据中我们依然可以找到更好的间隔序列，希尔排序的时间级从O(N^3/2)到 O(N^7/6)。对于我们大多数数据来说，评估值越高，那么越真实。因此我们在使用希尔排序中型大小的数据的时候应该注意一下间隔序列的问题，不要盲目的直接使用N/2，这样可能会使我们排序变得更加缓慢。

代码是通过Java数据结构与算法第二版 电力出版社中的希尔排序进行修改出来的

public class ShellSort {
        private long[] theArray;
        private int nElems;
    
        public ShellSort(int max) {
            theArray = new long[max];
            nElems=0;
        }
    
        public void insert(long value) {
            theArray[nElems]=value;
            nElems++;
        }
    
        public void display() {
            System.out.print("A=");
            for (int i = 0; i < nElems; i++) {
                System.out.print(theArray[i]+" ");
            }
            System.out.println("");
        }
    
    	//排序方法
        public void shellSort() {
            int inner,outer;
            long temp;
    
            //Knuth间隔序列
            int h=1;
            while(h<=nElems/3)
                h=h*3+1;
    		
    		//希尔排序通过间隔h的值进行比对,进行插入排序
            while (h > 0) {
                for(outer=h;outer<nElems;outer++) {
                    temp = theArray[outer];
                    inner=outer;
    
                    while (inner > h - 1 && theArray[inner - h] >= temp) {
                        theArray[inner] = theArray[inner - h];
                        inner-=h;
                    }
                    theArray[inner]=temp;
                }
                h=(h-1)/3;
            }
        }
    }