美文网首页
入门算法:插入排序

入门算法:插入排序

作者: 半理想主义 | 来源:发表于2020-02-26 18:39 被阅读0次

上手难度:★☆

算法复杂度:O(n^2),但在数组近乎有序的情况下,插入排序的性能相对比较高,甚至比O(nlogn)还要高

insertionSort.gif

排序思想:
两层循环
第一层循环从1到arr.length,前闭后开
最开始记录arr[i]的值为temp,也就是红色标记块
然后再以i为最大值进行倒序遍历
将temp与arr[j-1]进行比较不断往前挪动,挪动条件是小于前面的值,直到挪到挪不动的位置,就将temp放到这个位置

代码实现:

public class InsertSort {

    public static void insertSort(int[] arr) {
        for(int i = 1; i < arr.length; i++){
            int temp = arr[i];//使用temp记录i对应位置的值
            int j;

            for(j = i; j > 0 && temp < arr[j - 1]; j--){
            //每次与j前面的数进行比较,如果小于前面的值,就让arr[j]等于前一位的值,
            //由于temp记录了arr[i],最开始的j等于i,因此起初的值不会丢失
                arr[j] = arr[j - 1];//接收前一个元素的值
            }//从逻辑上来说,这里是将temp的值在小于arr[j-1]时,往前挪动
            
            arr[j] = temp;//到这一步,j自减到了temp>arr[j-1]的位置,
            //由于j的值在循环过程中已经被j+1接收了,因此让arr[j] = temp就完成了交换
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        insertSort(arr);

        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }
    }

}

运行结果


排序结果

优点:
第二层循环由于是从i开始进行倒序循环,循环不用每次都完整循环,提高了效率,在面对一个近乎有序数组时,内层循环甚至只需要循环一次就能完成,例如 1 2 3 4这种,内层循环只需要循环一次即可,算法复杂度最高效的时候接近O(n)。

相关文章

  • 算法入门——插入排序、快速排序

    上篇文章学习了算法入门——冒泡排序、选择排序,这篇文章我们学习算法入门——插入排序。 插入排序 插入排序是在一组列...

  • 算法入门——堆排序

    上篇文章我们学习了算法入门——插入排序、快速排序,这篇文章我们学习算法入门——堆排序。 堆 堆是一种特殊的完全二叉...

  • 算法-插入排序

    算 法:插入排序算法时间复杂度: 插入排序算法描述 插入排序伪代码 插入排序实现 插入排序算法概述 插入排...

  • 入门算法:插入排序

    上手难度:★☆ 算法复杂度:O(n^2),但在数组近乎有序的情况下,插入排序的性能相对比较高,甚至比O(nlogn...

  • python 冒泡排序和选择排序算法

    插入排序算法 冒泡排序算法

  • c算法O(n)^2(一)

    选择排序 插入排序 优化插入排序算法

  • Chapter 2 Foundation of Algorith

    Chapter 2 插入排序 线性查找 选择算法 归并排序算法 二分查找算法 冒泡排序 插入排序 循环不...

  • 算法入门(2)插入排序

    插入排序:就是把一个无序数组按照从小到大或者从大到小排序为有序数组。1.首先将无序数组中的第一个元素设为有序数组的...

  • 算法入门-排序算法-插入排序-详解

    一、核心思想 首先:把要排序的数组看作两部分:有序部分和无序部分初始情况:有序数组只有一个元素即第一个元素主要操作...

  • 插入排序算法实现

    排序算法是最常见,最基础的算法,作者文集中记录了两种排序算法(插入排序,归并排序) 插入排序算法实现很简单直接,附...

网友评论

      本文标题:入门算法:插入排序

      本文链接:https://www.haomeiwen.com/subject/amibchtx.html