Preface

In this collection, java language will be used to implement all internal sorting algorithms including insertion sort (direct insertion, half insertion, Hill sort), exchange sort (fast sort and bubble sort), selection sort, heap sort, merge sort and cardinal sort. Although they are very simple and can hardly be used in actual development (Arrays.Sort and Collection.Sort can be called directly), these are basic skills of a programmer, so it is necessary to master them.

algorithm

The idea of inserting sorting directly is to insert the elements to be sorted into the previously ordered sequence when it is found that the sequence is not ordered. So how to insert is the core problem. In fact, it is still to find the insertion position of the elements to be sorted. Because of sorting from small to large, you can start to compare from back to front from the previous position of the elements to be sorted. If you find that the elements to be compared are larger than the elements to be sorted, move the elements to back to make up the position. Finally, the element is assigned to the position vacated at the end of sorting.
The characteristic of   edge shift is to compare the edge shift, so it needs to be optimized. The subsequent half insert and Hill sort are both an optimization of direct insert sort. The time complexity is o(n*n).

Example

Take sequence 43125 as an example

Example

Codes

package com.fairy.InnerSort;

import java.util.Scanner;

/**
 * Direct insert sort
 * @author Fairy2016
 *
 */
public class DirectInsertSort {
    
    public static void sort(int a[], int n) {
        int i,j;
        for(i = 2; i <= n; i++) {
            if(a[i-1] > a[i]) {
                a[0] = a[i];//As a probe, a[0] not only stores the elements to be sorted, but also makes a cycle stop flag, which saves if judgment
                for(j = i-1; a[j] > a[0]; j--) {
                    a[j+1] = a[j];//A backward shift larger than a[i] is encountered to make room
                }
                a[j+1] = a[0];//Assign the elements to be sorted to the final position
            }
        }
    }
    
    public static void Print(int a[], int n) {
        for(int i = 1; i <= n; i++) {
            System.out.print(a[i]+" ");
        }
    }

    public static void main(String args[]) {
        int n;
        int a[];
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            n = scanner.nextInt();
            if(n > 0) {
                a = new int[n+1];
                for(int i=1; i <= n; i++) {
                    a[i] = scanner.nextInt();
                }
                sort(a, n);
                Print(a, n);
            }
        }
    }
}