Shell Sort in Java

    <span style="background-color: #ffffff;"><span style="font-family: 'Times New Roman'; line-height: 18px;">基本思想：</span><br style=""><span style="">　??? 先取一个小于n的整数d</span><sub style="">1</sub><span style="">作为第一个增量，把文件的全部记录分成d</span><sub style="">1</sub><span style="">个组。所有距离为d</span><sub style="">l</sub><span style="">的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d</span><sub style="">2</sub><span style=""><d</span><sub style="">1</sub><span style="">重复上述的分组和排序，直至所取的增量d</span><sub style="">t</sub><span style="">=1(d</span><sub style="">t</sub><span style=""><d</span><sub style="">t-l</sub><span style=""><…<d</span><sub style="">2</sub><span style=""><d</span><sub style="">1</sub><span style="">)，即所有记录放在同一组中进行直接插入排序为止。?</span><span style="">该方法实质上是一种分组插入方法。</span></span>

import java.util.Random;

/**
 * Shell sort in Java.
 * @author Sun Kui
 */
public class ShellSort {
    private long[] theArr;
    private int nElems;

    public ShellSort(int max) {
        theArr = new long[max];
        nElems = 0;
    }

    public void insert(long value) {
        theArr[nElems++] = value;
    }

    public void display() {
        System.out.print("A=");
        for (int j = 0; j < nElems; j++) {
            System.out.print(theArr[j] + " ");
            if (j % 10 == 0) {
                System.out.println();
            }
        }
        System.out.println();
    }

    public void shellSort() {
        int inner, outer;
        long temp;

        // select increment in, start from 1
        int h = 1;
        while(h <= nElems / 3) {
            h = h * 3 + 1;
        }

        while (h > 0) {
            for (outer = h; outer < nElems; outer++) {
                temp = theArr[outer];
                inner = outer;

                while (inner > h - 1 &amp;&amp; theArr[inner - h] >= temp) {
                    theArr[inner] = theArr[inner - h];
                    inner -= h;
                }
                theArr[inner] = temp;
            }
            // decrease increment in each step
            h = (h - 1) / 3;
        }
    }

    public static void main(final String... args) {
        Random rand = new Random();
        ShellSort ss = new ShellSort(100);
        for (int i = 0; i < 100; i++) {
            ss.insert(rand.nextInt(10000));
        }
        ss.shellSort();
        ss.display();
    }
}

?

end