欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

排序算法之插入排序介绍

程序员文章站 2022-03-03 11:02:47
1.插入排序 插入排序的原理很简单,就是将待排序的元素和已排序好的元素进行比较,找到合适的位置进行插入。 例子:2 1 5 3 6 4(升序排序) 1)将第一个元素看成已排序好的序列,从第二个元素开始比较,先用一个临时变量 temp 存放第二个元素的值。开始比较,1 比 2 小,所以把2赋值给1的位 ......

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("%d\n",arr[i]);
26     return 0;
27 } 

排序算法之插入排序介绍

 

 时间复杂度o(n^2)

插入排序可以改进,变成另一种排序算法-----希尔排序

希尔排序的时间复杂度o(n^1.3到n^2之间)

希尔排序,下次再说。