Sorting algorithm is the most common written question, almost all written tests and interviews will be asked, because it reflects the programmer’s algorithm foundation.

Insertion sort

Insertion Sort algorithm is a simple and intuitive sorting algorithm. It works by building an ordered sequence, scanning back to front in the sorted sequence for unsorted data, finding the appropriate location and inserting it.

(At each step, insert an element to be sorted into the appropriate position of the previously sorted group of elements according to its sorting code size, until all elements are inserted)

The specific algorithm is described as follows:

1. The first element of the sequence to be sorted is regarded as an ordered sequence and the second element to the last element is regarded as an unsorted sequence;

2. Take out the next element and scan from back to front in the sorted element sequence;

3. If the element (sorted) is larger than the new element, move the element to the next position;

4. Repeat step 3 until you find the position where the sorted element is less than or equal to the new element.

5. After inserting the new element into the position;

6. Repeat Steps 2 to 5.

convention

The elements to be sorted need to implement Java’s Comparable interface, which has the compareTo() method that can be used to determine the size relationship between two elements.

Use the auxiliary functions less() and swap() to compare and swap, making the code more readable and portable.

The cost model of the sorting algorithm is the number of comparisons and swaps.

packageAlgorithm. Sorting;/* Author :XiangLin Create time :15/05/2020 17:17 file: sort. Java IDE :IntelliJ IDEA */

public abstract class Sort<T extends Comparable<T>>{
    public abstract void sort(T[] nums);

    protected boolean less(T v, T w){
        return v.compareTo(w) < 0;
    }

    protected void swap(T[] a,int i ,int j){ T t = a[i]; a[i] = a[j]; a[j] = t; }}Copy the code

code

packageAlgorithm. Sorting;/* Author :XiangLin Created aT the Insertion. Java IDE :IntelliJ IDEA */

public class Insertion <T extends Comparable<T>> extends Sort<T>{

    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        for (int i = 1; i < N ; i++){for (int j = i; j > 0 && less(nums[j],nums[j-1]); j --){
                swap(nums,j,j - 1); }}}public static void main(String[] args) {
        Integer[] nums = {52.63.14.59.68.35.8.67.45.99};
        System.out.println("Original array:");
        for(int i :nums){
            System.out.print(i+"");
        }
        System.out.println();
        Insertion s = new Insertion();
        s.sort(nums);

        System.out.println("After sorting:");
        for(int i :nums){
            System.out.print(i+""); }}}Copy the code

Analysis of the

The time complexity of insertion sort depends on the initial order of the array. If the array is already partially ordered, there are fewer inversions, fewer swaps, and lower time complexity.

1. On average, insertion ordering requires ~ n2/4 comparison and ~ n2/4 swap;

2. At worst, ~ n2/2 comparisons and ~ n2/2 swaps are required, and at worst, arrays are in reverse order;

3. The best case requires n-1 comparisons and zero swaps, and the best case is that the array is already in order.

In addition, the blogger collects thousands of good commonly used books that he has seen or heard over the years. Maybe the book you want to find is right here, including most books and interview experience topics in the Internet industry and so on. There are artificial intelligence series (commonly used deep learning frameworks TensorFlow, PyTorch, Keras). NLP, machine learning, deep learning, etc.), Big data series (Spark,Hadoop,Scala, Kafka, etc.), programmer required series (C, C++, Java, Data Structures, Linux, Design patterns, databases, etc.

More articles see the original wechat public number “50 cents programmer”, we grow up together, learn together. Always pure, kind, tender love life. Pay attention to reply [ebook] can receive oh.

All coincidences are either destined by god or a person secretly working on it.

Have a harvest? Hope the old iron people come to a triple whammy, give more people to see this article

1, give me a thumbs up, can let more people see this article, thank you dear.

2, dear friends, pay attention to my original wechat public number “fifty cents programmer”, we grow up together, learn together. Always pure, kind, tender love life. There are a lot of resources out there.

Here’s a Github with lots of dry stuff on it:Github.com/XiangLinPro…

To do the useful thing, to say the courageous thing, to contemplate the beautiful thing: That’s enough for one man’s life. To do the useful thing, to say the brave thing, to think the beautiful thing — that’s enough for one life.

2020.5.23 in where