Direct insert sort and shell sort

1、 Direct insert sort

1.1、 Basic introduction and thought

• Insertion sort belongs to internal sort method , It is to find the appropriate position of the pre sorted element by inserting , In order to achieve the purpose of sorting .

• Insertion sort (Insertion Sorting） The basic idea of ： hold n The elements to be sorted look like an ordered table and an unordered table , The ordered table starts with just one element , The unordered table contains n-1 Elements , The first element is taken out of the unordered table every time during sorting , Compare its sort code with the sort code of the ordered table elements in turn , Insert it in place in an ordered table , Make it a new ordered table .

1.2、 Code implementation

// Ascending sort 
public class InsertSort {
    
    public static void main(String[] args) {
    
        int[] arr = {
    9,4,2,6,3,7,4,1};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    // Insertion sort 
    public static void insertSort(int[] arr) {
    
        int insertVal = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
    
            // Define the number to be inserted 
            insertVal = arr[i];
            insertIndex = i - 1;  // namely arr[i] The subscript of the preceding number of 
            // to insertVal  Find where to insert 
            // explain 
            //1.insertIndex >=0 Promise to give insertVal Find insertion location , Don't cross the border 
            //2.insertVal < arr[insertIndex] The number to be inserted , We haven't found the insertion position yet 
            //3. You need to arr[insertIndex] Move backward 
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
     // If sorting from large to small , Change the less than sign to the greater than sign 
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            // When to exit while loop , Indicate where to insert found , namely insertIndex+1
            int curIndex = insertIndex + 1;
            if (insertIndex != i) {
    
                arr[curIndex] = insertVal;
            }
        }

    }
}

2、 Shell Sort

2.1、 Problems with simple insertion sort

• Possible problems with simple insertion sorting .

  • Array arr = {2,3,4,5,6,1} The number to be inserted at this time 1( Minimum ), It's a process like this :

    {2,3,4,5,6,6}

    {2,3,4,5,5,6}

    {2,3,4,4,5,6}

    {2,3,3,4,5,6}

    {2,2,3,4,5,6}

    {1,2,3,4,5,6}

  • Conclusion ： When the number to be inserted is a smaller number , The number of moves back has increased significantly , It has an impact on efficiency .

2.2、 Introduction and basic idea of Hill's sorting method

• The Hill order is Hill （Donald Shell） On 1959 A sort algorithm proposed in . Hill sort is also an insert sort , It's a more efficient version of simple insert sorting with improvements , Also known as Reduced delta sort .

• Hill sort The basic idea ： Hill sort is to group records by a certain increment of subscript , Sort each group using the direct insertion sort algorithm ; As the increments decrease , Each group contains more and more keywords , When the increment is reduced to 1 when , The whole document is just a group , The algorithm terminates

• Hill sort diagram

• Finally, insert and sort all the data .

2.3、 Exchange method code

// Insertion sort - Shell Sort 
public class ShellSort {
    
    public static void main(String[] args) {
    
        int[] arr = {
    8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSort(arr);
    }

    // Shell Sort - Exchange method （ Low efficiency ）
    public static void shellSort(int[] arr) {
    
        int temp = 0;
        int count = 0;
        for (int gap = arr.length/2; gap >0 ; gap /= 2) {
    
            for (int i = gap; i < arr.length; i++) {
    
                // Go through all the elements in each group （ common gap Group , Each group has length/gap Elements ）, In steps of gap
                for (int j = i - gap; j >= 0; j -= gap) {
    
                    // If the current uniform speed is greater than the element after adding the step size , Explain the exchange 
                    if (arr[j] > arr[j + gap]) {
    
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
            System.out.println(" Hill ranked second "+(++count)+" round ="+ Arrays.toString(arr));
        }

       
    }
}

2.4、 Moving method code （ recommend ）

package com.ping.sort;

import java.util.Arrays;

// Insertion sort - Shell Sort 
public class ShellSort {
    
    public static void main(String[] args) {
    
        int[] arr = {
    8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSort2(arr);
        System.out.println(" After ordering "+Arrays.toString(arr));
    }

    // Optimize the Hill sort of exchange  ->  Shift method 
    public static void shellSort2(int[] arr) {
    
        int count = 0;
        // The incremental gap, And gradually reduce the increment 
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
    
            // From gap Elements , Insert and sort the groups one by one 
            for (int i = gap; i < arr.length; i++) {
    
                int j = i;
                int temp = arr[j];
                // This if Just insert the sort directly before ,while The last one inside if Well , Just change positions to improve efficiency 
                if(arr[j] <arr[j-gap]){
    
                    while(j - gap >= 0 && temp <arr[j-gap]){
    
                        // Move 
                        arr[j] = arr[j-gap];
                        j -= gap;
                    }
                    // When to exit while after , Just give it to temp Find where to insert 
                    arr[j] = temp;
                }
            }
        }
    }
}