Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

preface

This is the fourth in our Elegant series, and we’re going to do manual insertion sorting.

1. How to gracefully implement binary search

2. How to implement bubble sort elegantly

3. How to implement selection sorting elegantly

Algorithm description

  1. Divide the array into two regions, the sorted region and the unsorted region. Each round picks the first element from the unsorted region and places it in the sorted region
  2. Repeat until the array is in order

Algorithm implementation

    private static void insert(int[] a){
        for (int i = 1; i < a.length; i++) {
            int readyToInsert = a[i];
            int j;
            for (j = i; j > 0 && a[j-1] > readyToInsert; j--) {
                a[j] = a[j-1]; } a[j] = readyToInsert; }}Copy the code

The outer loop controls the unsorted region, and each time it takes the first value of the unsorted region that readyToInsert is going to insert into the sorted region. Where? So this is the inner control, and you can see that this is actually optimized, so I’m going to end the inner loop and find a place to insert, and then I’m going to do the actual insert, and this j is actually pointing to where I want to insert in the sorting area.

The I pointer Narrows the unsorted range from left to right, while the j pointer finds the first position that is smaller (or equal to) than the element to be inserted from right to left. Because j needs to perform the real insert logic after the inner for loop ends, it needs to be defined outside the for loop.

Compare insertion sort with selection sort

  1. The average time is n squared
  2. In most cases, the insertion algorithm is slightly better than the selection algorithm
  3. The time complexity of ordered set insertion algorithm is O(n)
  4. Insertion sort belongs to stable sorting algorithm, selection algorithm belongs to unstable sorting algorithm

The last

The idea of sensory insertion algorithm is very similar to that of selection algorithm, selection is to take the smallest region of the unsorted region and put it at the end of the sorted region, while insertion is to take the first region of the unsorted region and orderly insert it into the sorted region. It looks like a pair of symmetric brothers, and the insertion algorithm feels better because it doesn’t swap logic.