Bubble sorting and optimization

SelectionSort

Heap sort (HeapSort)

Insertion sort and optimization

ascending

Insertion sort is similar to the sorting of cards in play

The average time is order N ^ 2.

core idea

  1. Divide the sequence into two parts, with the head sorted and the tail to be sorted.

  2. Scan each element from the beginning, and when an element is scanned, insert it into the appropriate position in the header so that the header data is still in order.

Code implementation

public class InsertionSort<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort(a) {
        for (int begin = 1; begin < array.length; begin++) {
            int cur = begin;
            while (cur > 0 && cmp(cur, cur - 1) < 0) { swap(cur, --cur); }}}}Copy the code

The reverse of

The number of inversions is proportional to the time complexity of insertion sort.

If the element were all retrograde, it would be order n by n.

If there is no reverse pair, that is, the array is completely ascending, the time is order n.

Test input:

【HeapSort】 stability:falseTime:0.002 s (2 ms) :1.68All exchange:999-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - 【 InsertionSort 】 stability:trueTime:0.006 s (6 ms) :24.39All exchange:24.29M -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - 【 SelectionSort 】 stability:falseTime:0.007 s (7 ms) :49.95All exchange:999-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the BubbleSort 】 【 stability:trueTime:0.008 s (ms) :21.81All exchange:13.84M -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - the Process finished with exit code0

Copy the code

Optimization of a

As can be seen, the performance of the above writing method is poor, mainly because there are too many swaps.

Solution: Change the exchange to move:

  1. Backs up the elements to be inserted.
  2. Move any header element larger than the element to be inserted back one.
  3. Insert the backup element in the appropriate location.

It’s a lot less than swapping code, swapping takes three steps, moving only takes one.

private void sort2(a) {
        for (int begin = 1; begin < array.length; begin++) {
            int cur = begin;
            E element = array[cur];
            while (cur > 0 && cmp(element, array[cur - 1]) < 0) { array[cur] = array[--cur]; } array[cur] = element; }}Copy the code

Optimized output:

InsertionSort2 uses transposition instead of exchange stability:trueTime:0.006 s (6 ms) :25.43All exchange:0-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the most primitive InsertionSort1 】 【 stability:trueTime:0.009 s (ms) :25.43All exchange:25.33M -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - the Process finished with exit code0

Copy the code

You can see that there is an increase, the number of swaps is gone.

The more the while loop executes, the better the performance of the optimization. The more inversions you have, the better the optimization will be.

Optimization of two

Optimization can be achieved by optimizing the number of comparisons.

Insert sort 2: scan each element from the beginning, every time an element is scanned, insert it into the appropriate position in the header, so that the header data is still in order.

So we’ve done this for loop, which is O(n). We can improve the time by optimizing the way we find the location.

Note that the ** header sequence is actually sorted, so we can use binary search to find the appropriate location. ** The time complexity of binary lookup is O(logN).

		/** * find the position where the index element is to be inserted * <p> * the already arranged area is [0,index) **@paramIndex Position of the element to be inserted *@returnWhere it should be inserted */
    private int search(int index) {
        E v = array[index];
        int begin = 0;
        int end = index;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (cmp(v, array[mid]) < 0) {
                end = mid;
            } else {
                begin = mid + 1; }}return begin;

    }
Copy the code

Note that the code above is a bit different from binary search. Search for the position to insert, which should be nearest greater than the position of the element to be inserted.

Once we know where to insert, we also need to move all the data from that position to the tail back one bit to make room to insert the target value.

 private void insert(int begin, int insertIndex) {
        / / backup
        E element = array[begin];
        // put [insertIndex,begin] behind
        for (int i = begin; i > insertIndex; i--) {
            array[i] = array[i - 1];
        }
        array[insertIndex] = element;
    }


Copy the code

The overall code is:

		private void sort3(a) {
        for (int begin = 1; begin < array.length; begin++) {
            // The header is ordered, using binary search, complexity is O(logn)
            intinsertIndex = search(begin); insert(begin, insertIndex); }}private void insert(int begin, int insertIndex) {
        / / backup
        E element = array[begin];
        // put [insertIndex,begin] behind
        for (int i = begin; i > insertIndex; i--) {
            array[i] = array[i - 1];
        }
        array[insertIndex] = element;
    }

    /** * find the position where the index element is to be inserted * <p> * the already arranged area is [0,index) **@paramIndex Position of the element to be inserted *@returnWhere it should be inserted */
    private int search(int index) {
        E v = array[index];
        int begin = 0;
        int end = index;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (cmp(v, array[mid]) < 0) {
                end = mid;
            } else {
                begin = mid + 1; }}return begin;

    }

Copy the code

Compare the output of the three methods:

Stability of binary search optimizationtrueTime:0.003 s (3 ms) :8559Exchange:0-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - use little bit instead of InsertionSort2 】 【 exchange stability:trueTime:0.006 s (6 ms) :25.43All exchange:0-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the most primitive InsertionSort1 】 【 stability:trueTime:0.009 s (ms) :25.43All exchange:25.33M -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - the Process finished with exit code0
Copy the code

After using binary search, it only reduces the number of comparisons to find the insertion position, but the time complexity of moving the position is still O(N), so the average time complexity of insertion sort is still O(N ²).