插入排序（常见经典排序算法）

た入场券 2023-09-28 08:06 133阅读 0赞

> ### **基本思路：** ###
> 
> 1.  **从第二个元素开始进行排序，第二个元素与前面的第一个元素进行比较，如果大就保持不动，如果小于第一个元素就往前移。**
> 2.  **然后第三个元素与前面已经排序好的元素（前两个）从右到左（从大到小）依次进行比较，直到被比较的数小于或等于第三个元素，然后插入到这个元素的后面。**
> 3.  **重复上面的过程，直到最后一个元素比较完成，一共进行了n-1趟。**
> 
> **平均时间复杂度：O（![n^\{^\{2\}\}][n_2]）**

##  **图示展示：** ##

![faaec4d7563ca86e3f8867aa58dc1254.gif][]

import java.util.Arrays;
    
    public class InsertSort {
        public static void main(String[] args) {
            int[] arr = {5,4,3,2,1,-1,-5,-3};
            System.out.println("未排序数组："+ Arrays.toString(arr));
            insertSort(arr);
            System.out.println("未排序数组："+ Arrays.toString(arr));
        }
    
        public static void insertSort(int[] arr){
            for (int i=1;i<arr.length;i++){//插入排序从第二个元素开始进行，// 所以这里i（作为索引）设为1，循环次数为arr.length-1;
                int insertIndex = i;
                int insertValue = arr[i];
                while (insertIndex > 0 && insertValue < arr[insertIndex-1]){//当要排序的元素比前一个元素大时，进入循环
                    arr[insertIndex] = arr[insertIndex-1];//每次arr[i]<arr[i-1],就把arr[i-1]的值往后移，直到arr[i]>arr[i-1]
                    insertIndex--;
                }
                arr[insertIndex] = insertValue;
                //insertValue 在比较过程中一直没变，最后一步将insertValue的值赋给insertIndex所指的元素
            }
        }
    }

**---end---**

**扫描下方二维码**

**添加好友，备注【交流】**

**可私聊相互学习，共同进步，资源共享**

![b1255cc64e154f8692750c853a2f4402.jpeg][]

[n_2]: https://latex.csdn.net/eq?n%5E%7B%5E%7B2%7D%7D
[faaec4d7563ca86e3f8867aa58dc1254.gif]: https://img-blog.csdnimg.cn/img_convert/faaec4d7563ca86e3f8867aa58dc1254.gif
[b1255cc64e154f8692750c853a2f4402.jpeg]: https://img-blog.csdnimg.cn/b1255cc64e154f8692750c853a2f4402.jpeg