How to further optimize after implementing insertion sort in java

Learning video sharing: java video tutorial

Normal insertion: operate from the second element of the array, when it is found When the previous element is larger than it, a swap operation is performed.

static int[] insertSort(int[] array){
        int len = array.length;
        for (int begin = 1; begin  0 && array[cur] <p><strong>The first step of optimization: operate from the second element of the array. If it is found that the previous element is larger than it, move the previous element back until cur The pointed element is greater than or equal to its previous element. At this time, the position pointed by cur is the position where the element to be inserted should be inserted. </strong><br></p><pre class="brush:php;toolbar:false">    static int[] insertSort2(int[] array){
        int len = array.length;
        for (int begin = 1; begin  0 && array[cur] <p><strong>Second step optimization</strong><br></p><p><strong>The third algorithm is essentially the same as the second one. They all find the position to be inserted and move the elements, but the third algorithm reduces the number of comparisons through binary search, that is, the calls to the cmp function, and also reduces the calls to the swap function. It is faster to find the position where the current element should be inserted, and then move it, which improves efficiency. </strong></p><pre class="brush:php;toolbar:false">static int[] insertSort3(int[] array){
        int len = array.length;

        for (int begin = 1; begin  insertIndex; i--){
                array[i] = array[i-1];
            }
            array[insertIndex] = v;
        }
        return array;
    }
    static int search(int[] array, int index){
        int begin = 0;
        int end = index;
        while(begin > 1;
            if (array[index] <p><strong>It should be noted that after using binary search, only the number of comparisons is reduced, but the average time complexity of insertion sort is still O(n^2)</strong><br></p><p><strong>The effect of separating the moving operations: </strong></p><pre class="brush:php;toolbar:false">    package com.mj.sort.cmp;import com.mj.sort.Sort;public class InsertionSort3<t>> extends Sort<t> {

	//	protected void sort() {//		for (int begin = 1; begin = insertIndex; i--) {							}//			for (int i = begin; i > insertIndex; i--) {//				array[i] = array[i - 1];//			}//			array[insertIndex] = v;//		}//	}
	
	@Override
	protected void sort() {
		for (int begin = 1; begin  dest; i--) {
			array[i] = array[i - 1];
		}
		array[dest] = v;
	}
	
	/**
	 * 利用二分搜索找到 index 位置元素的待插入位置
	 * 已经排好序数组的区间范围是 [0, index)
	 * @param index
	 * @return
	 */
	private int search(int index) {
		int begin = 0;
		int end = index;
		while (begin > 1;
			if (cmp(array[index], array[mid]) <p>Related recommendations: <a href="https://www.php.cn/java/guide/" target="_blank">java introductory tutorial</a></p></t></t>

The above is the detailed content of How to further optimize after implementing insertion sort in java. For more information, please follow other related articles on the PHP Chinese website!