1.插入排序
插入排序的原理很简单,就是将待排序的元素和已排序好的元素进行比较,找到合适的位置进行插入。
例子:2 1 5 3 6 4(升序排序)
1)将第一个元素看成已排序好的序列,从第二个元素开始比较,先用一个临时变量 temp 存放第二个元素的值。开始比较,1 比 2 小,所以把2赋值给1的位置,继续向前比较
这时前面已经没有元素了,比较结束,将temp的值赋值给2的位置
序列变成:1 2 5 3 6 4
2)继续按1)的方法对元素5进行同样的操作,5不小于2,此时不用继续比较了,因为序列是有序的 5 不小于2 那就不可能小于1 .
序列变成:1 2 5 3 6 4
3)3 比 5 小,将5的赋值给3的位置,继续向前比较,3不小于2,比较结束,将temp的值赋值给5的位置
序列变成: 1 2 3 5 6 4
4)6 不小于 5 不用比较
序列:1 2 3 5 6 4
5)4 比6小,将6赋值给4的位置,继续向前比较,4 比 5小 将5的值赋值给6的位置,继续向前比较4不小于3,比较结束,将temp值赋值给5的位置
序列:1 2 3 4 5 6
2.代码
代码看上去有点难理解,但是只要自己在脑子里按步骤过一遍就懂了。
1 #include<stdio.h> 2 void insertsort(int *arr,int num) 3 { 4 int i,j; 5 int temp; 6 //从第二个元素开始比较 7 for(i=1;i<num;i++) 8 { 9 temp=arr[i];//保存要插入元素的值 10 j=i-1; 11 while(j>=0&&arr[j]>temp) 12 { 13 arr[j+1]=arr[j]; 14 j--; 15 } 16 arr[j+1]=temp;//找到合适位置 17 } 18 } 19 int main() 20 { 21 int i; 22 int arr[10]={1,3,-9,0,10,2,8,9,19,-1}; 23 insertsort(arr,10);//插入排序 24 for(i=0;i<10;i++) 25 printf("%dn",arr[i]); 26 return 0; 27 }
时间复杂度o(n^2)
插入排序可以改进,变成另一种排序算法—–希尔排序
希尔排序的时间复杂度o(n^1.3到n^2之间)
希尔排序,下次再说。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/599821.html