Insert sort

The content of the article comes from Data structure Textbook (C Language version )
The textbook explains 4 An insertion sort algorithm , Respectively
1、 Direct insert sort
2、 Binary Insertion Sort
3、2- Path insertion sort
4、 Table insertion sort
There is also a hill sort ( It belongs to insert sort classification )
This article will only 1、2, Two algorithms are practiced and explored , Among them the first 4 The insertion sorting of tables is based on linked lists .1-3 It's based on arrays .

Two algorithms Java The implementation is as follows

	/** *  Direct insert sort (Straight Insertion Sort) * *  Its basic operation is to insert a record into an ordered table , Thus, we can get a new ordered table with one record added . * *  Spatial complexity O(1) *  Time complexity O(n^2) * *  When the number of records to be sorted n When I was very young , This is a good sorting method . however , Usually, the number of records in the sequence to be sorted n *  It's big , It is not suitable to use direct insertion sorting . * * @param arr */
	void insertSortV1(int[] arr) {
    
		for (int i = 1; i < arr.length; i++) {
    
			if (arr[i] <= arr[i - 1]) {
    
				int temp = arr[i];
				arr[i] = arr[i - 1];
				int j;
				for (j = i - 2; j >= 0 && temp <= arr[j]; j--) {
    
					arr[j + 1] = arr[j]; //  Record back 
				}
				arr[j + 1] = temp; //  Insert in the correct position 
			}

		}
	}// insertSortV1
	
	/** *  Binary Insertion Sort (Binary Insertion Sort) * *  Because the basic operation of insert sort is to search and insert in an ordered table , Then this " Search operation " You can use " Binary search " To achieve  * , The insertion sort thus performed is called a half insertion sort . * *  The complexity of half insert sort space is still O(1) *  Compare... In terms of time , Half insertion sorting only reduces the number of keyword comparisons , The number of moves recorded remains the same . therefore  *  The time complexity is still 0 O(n^2) * * @param arr */
	void BInsertSort(int[] arr) {
    
		for (int i = 1; i < arr.length; i++) {
    
			int temp = arr[i];
			int low = 0;
			int high = i - 1;
			while (low <= high) {
    
				int m = (low + high) / 2;
				if (temp <= arr[m]) {
    
					high = m - 1;
				} else {
    
					low = m + 1;
				}
			} // while

			for (int j = i - 1; j >= high + 1; j--) {
    
				arr[j + 1] = arr[j];
			}
			arr[high + 1] = temp;
		}
	}// BInsertSort
	
	@Test
	public void fun1() {
    
		int[] arr = {
     49, 38, 65, 97, 76, 13, 27, 49 };
		// insertSortV1(arr);
		BInsertSort(arr);
		System.out.println(Arrays.toString(arr));
	}

this 2 The space complexity of the implementation of the insertion sort algorithm is O(1), Time complexity is O($n^2$). Half insertion sorting only reduces the number of element comparisons , The number of moves recorded remains the same .