首页 > 代码库 > 《直接插入排序》算法设计之三
《直接插入排序》算法设计之三
直接插入排序
每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的序列中,知道全部记录插入完成。
排序过程
1.每次插入的数值都要与自己前面的做比较
A.如果大于前面的数,则停止。因为每次都是排好的序列
B.如果小于前面的数,接着向前比较,指导找到自己的位置,插入即可
如右图所示
当插入2时,需要与前面做比较,直到找到自己合适的位置即可
当插入1时,用现在插入的数值依次与前面做比较,直到找到合适的位置即可
代码分析
通过以上的分析,因此我们可以采取以下思路来处理直接插入排序
方法一
找位置
让插入的数值与前一个数做比较,比如上图中插入的1与6做比较,如果小的话,继续执行,知道找到自己该放的位置。
整体移动
让该位置到最后的数值整体向后移动,最后把要插入的数字放到该位置即可
<span style="font-family:SimSun;font-size:18px;"> /// <summary> /// 直接插入排序 /// </summary> /// <param name="a">数组,用来保存数值</param> /// <param name="n">数组中元素个数</param> static void Insertsort(int[] a, int n) { int i, j, k; for (i = 1; i < n; i++) { //用来帮插入的数值找到合适的位置 for (j = i - 1; j >= 0; j--) { //如果小于的话,直接退出,因为排序已经完成 if (a[j] < a[i]) { break; } } //如果找到了一个合适的位置 if (j != i - 1) { //保存插入的变量 int temp = a[i]; //从插入的后一个,到合适的位置的所有数值整体向后移动 for (k = i - 1; k > j; k--) { //向后移动 a[k + 1] = a[k]; } //把插入的数值,放到该位置上 a[k + 1] = temp; } } }</span>
方法二
看上面的代码我们还可以做一下优化,比如如果刚插入的数值大于满足整体排序的话,就应该直接退出里层循环,而上述代码并没有,因此我们可以换一种思路
先比较
类似于先把要插入的数字放到一个格子里,依次与前面的比较。如果小于前者,则让前者向后移动
再移动
如果插入的数值小于前者,如上图所示刚插入的1小于6的话,6向后移动,接着再进行比较
......................................................................................................
<span style="font-family:SimSun;font-size:18px;"> //直接插入排序法 static void Insertsort(int []a,int n) { int i, j; //数组中默认是由一个数的 //for循环来放置后面的N个数 for(i=1;i<n;i++) { //依次与前者比较 //如果小的话,执行迁移 if(a[i]<a[i-1]) { //先保存插入的数值 int temp = a[i]; //内层采用循环来一边执行移动,一边比较 for(j=i-1;j>=0&&a[j]>temp;j--) { a[j + 1] = a[j]; } //最后还是把插入的数值放到合适的位置 a[j + 1] = temp; } } }</span>
《直接插入排序》算法设计之三
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。