Bubble sorting and optimization

SelectionSort

Heap sort (HeapSort)

Insertion sort and optimization

MergeSort

QuickSort

ShellSort and optimization

core idea

If you have the following set of sequences, you need to use Hill sort to upgrade them.

We divide the sequence into columns in some increment. For example, the above requirement can be divided into 2 columns, 4 columns and 8 columns according to 4, 2 and 1. It then inserts the elements on each of its columns separately. This increment is a series of numbers. Hill himself recommended incremental coefficients of 1, 2, 4, 8, 16… 2 to the k.

If the increment sequence is 1, 2, 4, 8… I take the inverse sequence. Use large ones first. Let’s say 4. We have columns of four elements spaced out.

As shown in the figure above, we can divide the original sequence into 2 rows, which is actually 4 columns. And then we do insert sort for the no columns. After the original sequence becomes

Let’s break it down by increments of 2:

When you sort the original sequenceFinally, it divides into 1 column in increments of 1, which is actually the sequence above. One more round of insertion sort. You end up with an ascending sequence

What we saw with Hill sort is actually using insertion sort. But the outermost layer of insert sort uses a for loop so its average complexity is O(N ^ 2). And our outermost layer is two to the k for the increment, so the average complexity is order NlogN.

You can also think of Hill sort as an optimized way of writing insertion sort.

Code implementation

1. Get delta sequence

    /** * shell recommends the Step column **@returnStep * /
    private List<Integer> shellStepQueue(a) {
        ArrayList<Integer> queue = new ArrayList<>();
        int step = array.length;
        while ((step >>= 1) > 0) {
            queue.add(step);
        }
        return queue;

    }

Copy the code

2. Sort each column incrementally, and then sort each column by insertion.

    private void sort(Integer step) {
        // col: which column ends with step
        for (int col = 0; col < step; col++) {
            // Divide the original data into step columns
            // Note that each column is welcome in the original array position:
            // Insert sort for each column
            for (int begin = col + step; begin < array.length; begin += step) {
                int cur = begin;
                while (cur > col && cmp(cur, cur - step) < 0) { swap(cur, cur -= step); }}}}Copy the code

All codes are as follows:

public class ShellSort<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort(a) {
        // Get the step queue
        List<Integer> stepQueue = shellStepQueue();
        // Perform insert sort on all columns
        for(Integer step : stepQueue) { sort(step); }}private void sort(Integer step) {
        // col: which column ends with step
        for (int col = 0; col < step; col++) {
            // Divide the original data into step columns
            // Note that each column is welcome in the original array position:
            // Insert sort for each column
            for (int begin = col + step; begin < array.length; begin += step) {
                int cur = begin;
                while (cur > col && cmp(cur, cur - step) < 0) { swap(cur, cur -= step); }}}}/** * shell recommends the Step column **@returnStep * /
    private List<Integer> shellStepQueue(a) {
        ArrayList<Integer> queue = new ArrayList<>();
        int step = array.length;
        while ((step >>= 1) > 0) {
            queue.add(step);
        }
        returnqueue; }}Copy the code

To optimize the

Hill sort complexity is O(NlogN), but the logN is caused by the way the delta queue is obtained. We can optimize time-complex pairs simply by optimizing how we get the incremental sequence.

The following method is currently recognized as the best way to obtain incremental sequences.

 /** * Currently recognized as the best way to obtain Step **@return step
     */
    private List<Integer> sedgewickStepSequence(a) {
        List<Integer> stepSequence = new LinkedList<>();
        int k = 0, step = 0;
        while (true) {
            if (k % 2= =0) {
                int pow = (int) Math.pow(2, k >> 1);
                step = 1 + 9 * (pow * pow - pow);
            } else {
                int pow1 = (int) Math.pow(2, (k - 1) > >1);
                int pow2 = (int) Math.pow(2, (k + 1) > >1);
                step = 1 + 8 * pow1 * pow2 - 6 * pow2;
            }
            if (step >= array.length) break;
            stepSequence.add(0, step);
            k++;
        }
        return stepSequence;
    }

Copy the code

Just replace the incremental sequence retrieval method in the first version. Of course, the insertion sort part can be optimized.

The optimized time complexity is O(n^(1.3 — 2)).