排序算法之插入排序介绍

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之间)

希尔排序，下次再说。