作品展示的网站,情人节网站源码下载,中国公路建设行业协会网站,南宁网站建设加王道下拉一、原理
在待排序的数组里#xff0c;从数组的第二个数字开始#xff0c;通过构建有序序列#xff0c;对于未排序数据#xff0c;在已排序序列中从后向前扫描#xff0c;找到相应位置并插入。
二、代码部分 #includestdio.h #includestdlib.h int ma…一、原理
在待排序的数组里从数组的第二个数字开始通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。
二、代码部分 #includestdio.h #includestdlib.h int main() { int arr[10] { 9,2,1,3,5,4,10,8,6,7 }; int flag 0, i 0,j 0; printf(排列前); for (int i 0; i 10; i) { printf(%d , arr[i]); } printf(\n\n); for (i 1; i 10; i) { flag arr[i]; //记录arr[i] 的值 for (j i - 1; j 0 arr[j] flag;j--) //当arr[i]前面的一个数字比a[i]大时 { arr[j 1] arr[j]; //将arr[i] 和其前一个数字进行交换 } arr[j 1] flag; } printf(排列后); for (int i 0; i 10; i) { printf(%d , arr[i]); } printf(\n\n); system(pause); return 0; } 代码输出结果 三、代码解析
1、核心代码 for (i 1; i 10; i) { flag arr[i]; //记录arr[i] 的值 for (j i - 1; j 0 arr[j] flag;j--) //当arr[i]前面的一个数字比arr[i]大时 { arr[j 1] arr[j]; //将arr[i] 和其前一个数字进行交换 } arr[j 1] flag; } ①因为插入排序的执行轮次为 N-1次所以这里 i 的循环只有 9 次。
② j 循环的作用通俗来讲就是每次将大于 a[i] 的数字往后各移一个位置。
2、 代码的部分运行过程带图解
首先见如下原数组各元素的分布情况 ①i 1j 0,flag 2,进入 j 的循环后要执行一次使 arr[1] 9然后再执行 arr[j 1] flag让 arr[0] 2最后的结果如下 ②i 2j 1,flag 1,进入 j 的循环后要执行两次第一次使 arr[2] 9第二次使 arr[1] 2,然后再执行 arr[j 1] flag让 arr[0] 1最后的结果如下 ③i 3j 2,flag 3,进入 j 的循环后要执行一次使 arr[3] 9然后再执行 arr[j 1] flag让 arr[2] 3最后的结果如下 ④i 4j 3,flag 5,进入 j 的循环后要执行一次使 arr[4] 9然后再执行 arr[j 1] flag让 arr[3] 5最后的结果如下 ⑤i 5j 4,flag 4,进入 j 的循环后要执行两次第一次使 arr[5] 9第二次使arr[4] 5,然后再执行 arr[j 1] flag让 arr[3] 4最后的结果如下 ⑥i 6j 5,flag 10,因为不满足 j 的条件所以直接执行 arr[j 1] flag让 arr[6] 10arr[6] 原本就等于10这步并未对原数组造成影响。
⑦i 7j 6,flag 8,进入 j 的循环后要执行两次第一次使 arr[7] 10第二次使arr[6] 9,然后再执行 arr[j 1] flag让 arr[5] 8最后的结果如下 ⑧i 8j 7,flag 6,进入 j 的循环后要执行三次第一次使 arr[8] 10第二次使arr[7] 9,第三次使arr[6] 8,然后再执行 arr[j 1] flag让 arr[5] 6最后的结果如下 ⑨最后一次i 9j 8,flag 7,进入 j 的循环后要执行三次第一次使 arr[9] 10第二次使arr[8] 9,第三次使arr[7] 8,然后再执行 arr[j 1] flag让 arr[6] 7最后的结果如下排列完成 四、总结
插入排序的优点如果是进行相对有序的数组效率会非常高。不占额外空间是一种稳定的算法编写过程也相对简单时间复杂度高。
插入排序的缺点遇到数据过多的情况下不是很适用。
