十大排序之插入排序-技术圈

java实现插入排序（InsertSort）

4.13

简介

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序的时间复杂度是O(n^2) ，空间复杂度是O（1）。

将第一个看成一个有序数列，将后面的数跟前面的数比较，大的就往后移

第一趟排序后：得到一个有序数列，其大小为2

第二趟排序后：得到一个有序数列，其大小为3

第三趟排序后：得到一个有序数列，其大小为4

........每一趟插入排序，都可以将一个无序值插入一个有序数列，直至全部值有序

实现思路：

第一步、将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

第二步、从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。所以插入排序是稳定的排序）。

4.13

图解流程

4.13

代码实现

package com.znzz.insertSort;
import java.util.Arrays;
public class InsertSort {    public static void main(String[] args) {        inserrtSort(new int[]{6,2,0,2,4,7,9,10});    }    public static void inserrtSort(int[] arr) {        int value;  //待插入元素        int index;  //待插入元素的前一个元素的索引
        for (int i = 1; i < arr.length; i++) {            //这里i=1，默认第一个元素是有序的，            //循环条件是小于数组长度            value = arr[i];            index = i - 1;   //前一个元素            while (index >= 0 && value < arr[index]){                //需要保证index合法                //每当前面的元素比待插入元素大，就向后移动                arr[index + 1] = arr[index];                index--;        }        //到这里表示退出循环，说明找到了待插入的位置，        arr[index + 1] = value;    }        System.out.println(Arrays.toString(arr));}}

如果该文章对你有帮助，"再看"和"点赞"是对我最大的鼓励！

扫二维码｜关注我们

谢谢观看

把城市夜晚的喧嚣，点出来

▼