title: Insert sort
date: 2019-07-21 09:58:02
Summy: Insertion-Sort
categories: Data structures and algorithms
tags: [LeetCode, Introduction to Algorithms]

Title:

leetcode(912):
	Given an integer array nums, the array is arranged in ascending order.
		Example 1:   
			Input: [5, 2, 3, 1]
			Output: [1, 2, 3, 5]
		Example 2:
			Input: [5, 1, 1, 2, 0, 0]
			Output: [0, 0, 1, 1, 2, 5]
	Tips:
		1 <= A.length <= 10000
		-50000 <= A[i] <= 50000
	Source: LeetCode
	Link: https://leetcode-cn.com/problems/sort-an-array
	Copyright belongs to the seizure network. For commercial reprints, please contact the official authorization. For non-commercial reprints, please indicate the source.

Ideas for solving problems:

	(Summary later)

Specific code:

class Solution {
	public int[] sortArray(int[] nums) {
        if(nums == null || nums.length == 1){
            return nums;
        }

        for(int currentInsetIndex = 1; currentInsetIndex < nums.length; currentInsetIndex++){
            // CurrtInset: Number currently inserted
            int currentInset = nums[currentInsetIndex];
            
            // Subscripts for current comparison
            int currentCompareIndex = currentInsetIndex - 1;

            // Dichotomy Finds the Right Location
            int index = Solution.binarySearch(nums, 0, currentCompareIndex, currentInset);

            // Insert in the right place
            Solution.insertNum(nums, 0, currentInsetIndex, index);
        }

        return nums;
    }

    /**
     * Binary lookup value with correct subscript in sorted array
     * @param array Array for lookup
     * @param lower Find the lower bound
     * @param up Find the upper bound
     * @param num Find numbers
     * @return subscript
     */
    public static int binarySearch(int[] array, int lower, int up, int num){

        int lowerSearch = lower;
        int upSearch = up;

        int middle = (upSearch - lowerSearch)/2 + lowerSearch;
        while(lowerSearch <= upSearch){

            if(array[middle] > num){
                upSearch = middle - 1;
            }else{
                lowerSearch = middle + 1;
            }
            middle = (upSearch - lowerSearch)/2 + lowerSearch;
        }

        return middle;
    }

    /**
     * Insert values into an array (an array within the range of an array is inserted into another position in the array)
     * @param array An array for insertion
     * @param lower Lower bound of insertion range
     * @param up The upper bound of the insertion range (also the value to insert)
     * @param index Insert Subscripts
     */
    public static void  insertNum(int[] array, int lower, int up, int index){
        // unlawfulness
        if(up <= index && index < lower){
            return;
        }

        // save a value of insert
        int num = array[up];

        // move inserted value of last to last
        for (int i = up; i > index && i > lower; i--){
            array[i] = array[i-1];
        }

        // insert value
        array[index] = num;
    }
}

Operation results:

Implementation results:
	By displaying details
	Execution time:
		314 ms, beating 8.58% of all Java submissions
	Memory consumption:
		52.1 MB, beating 100.00% of all Java submissions

Result analysis:

	Great expectations have been placed on this algorithm:
		1. Using the dichotomy search method, the linear time needed for linear search is solved, and the search time is reduced to lg(n).
		2. Replace recursion with iteration, and solve the problem of java. lang. StackOverflow Error when array length is too long.
	For the first time, the sorting calm analysis is carried out in the way of algorithm combination.
		1. Memory consumption is well understood, in-situ sorting.
		2. For execution, although the linear search is replaced by the dichotomy search method, it still can not change that the algorithm itself is the insertion sort, and for the insertion sort, the most fearful is the array length.