2025年插入排序

插入排序一 插入排序 InsertSort 插入排序从第二个数开始 拿出第二个数进行向前插入排序 一直到最后一个数向前做插入排序 算法稳定 插入排序的时间复杂度为 O n 2 空间复杂度为 O 1 最好的时间复杂度是 O n 最坏也就是平均是 O n 2 二 图解

大家好,我是讯享网,很高兴认识大家。

一、插入排序(InsertSort)

插入排序从第二个数开始,拿出第二个数进行向前插入排序,一直到最后一个数向前做插入排序。算法稳定。

插入排序的时间复杂度为O(n^2),空间复杂度为O(1)。最好的时间复杂度是O(n),最坏也就是平均是O(n^2)

 

二、图解

对于一串数字(3,5,2,1,4,10)进行插入从小到大排序,如下图演示

 


讯享网

 

三、算法分析

 / * 插入排序 * 1、确定插入排序的数,从第二个开始选择 * 2、选择插入排序的数,保存为num * 3、计算num前一个数的索引 * 4、进行检查,如果num小于前面的数,则将前一个数往后移,若比前一个数大,则结束此次循环 * 5、结束时的位置保存num * @param arr */ public static void insertSort(int[] arr) { for (int i = 1; i < arr.length; i++) { //选择插入排序的数,保存为num int num = arr[i]; //计算num前一个数的索引 int preIndex = i - 1; for (; preIndex >= 0; preIndex--) { //进行检查,如果num小于前面的数,则将前一个数往后移,若比前一个数大,则结束此次循环 if (num < arr[preIndex]) arr[preIndex + 1] = arr[preIndex]; else break; } //结束时的位置保存num if (num != arr[i]) arr[preIndex + 1] = num; }

讯享网

 

四、算法实现

讯享网package com.arithmetic.sort; / * @Description * 功能:实现插入排序 * 从第二个数开始,拿出第二个数进行向前插入排序,一直到拿到最后一个数向前做插入排序 * 时间复杂度O(n^2);空间复杂度O(1);稳定;算法复杂度最好O(n),不需要加条件实现,最坏情况是O(n^2) * @Author xuexue * @Date 2019/11/9 22:25 */ public class InsertSort { public static void main(String[] args) { int[] arrs = new int[]{3, 5, 2, 1, 4, 10}; insertSort(arrs); for (int arr : arrs) { System.out.println(arr); } } / * 算法:插入排序 * 需要选择作为插入的数:从第二个开始,共n-1个数 * 每次将选择作为插入的数与前面比较,如果小于则前面的数往后移动一位,否则插入到这个位置 * @param arr */ public static void insertSort(int[] arr) { for (int i = 1; i < arr.length; i++) {//总共需要选择作为插入的数为n-1个 int num = arr[i];//选择作为插入的数 /* int leftIndex = i -1;//插入的数前一个位置索引 //插入排序算法实现 while (leftIndex >= 0 && num < arr[leftIndex]) { arr[leftIndex + 1] = arr[leftIndex];//交换位置 leftIndex--; } if (num != arr[i]) arr[leftIndex + 1] = num;*/ int j = i - 1;//记录插入的数前一个位置的索引 for (; j >= 0; j--) {//从插入元素的前一个开始 //进行比较 如果作为插入的数小于则前面的数往后移动一位,否则进入else插入到这个位置 if (num < arr[j]) arr[j + 1] = arr[j];//前面的数往后移动一位 else break; } if (num != arr[i])//说明移动了位置,需要插入 arr[j + 1] = num;//将作为比较的数插入数组中,形成新的片段有序数组 } } } 

 

运行结果:

 

 

 

小讯
上一篇 2025-03-13 15:21
下一篇 2025-04-04 13:19

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/115548.html