[C语言] 插入排序之直接插入排序的特性及实现

[C语言] 插入排序之直接插入排序的特性及实现

1、算法特性

　　直接插入是一种简单、稳定的插入排序方法，属于最为基础的排序方法之一。

　　其时间复杂度最好情况为O（n）、最差与平均情况为O（n²），空间复杂度为O（1）。

2、算法思路：

　　以升序排列为例，先设置一个临时变量存储将要移动的插入值，再将其与其之前的数据依次比较。当比较值比插入值大时，比较值后移一位，插入值继续向前检索；当比较值小于等于插入值时，插入值插入比较值的后一位。经过多轮循环便可以将所有数据排列有序。

3、实现代码

 1 #include <stdio.h>
 2 
 3 // 插入排序：直接插入
 4 void insert_sort(int arr[],int len)
 5 {
 6     // 把下标为i的这个元素插入到前面 前面数组是有序
 7     for(int i=1; i<len; i++)
 8     {
 9         // 记录要插入的值 往后移的过程会覆盖arr[i]的值 提前保存
10         int num = arr[i];
11         // 循环比较
12         int j = 0;
13         for(j=i-1; j>=0; j--)
14         {
15             if(num < arr[j])
16             {
17                 arr[j+1] = arr[j]; // 把数据往后移
18             }
19             else // arr[j] >= num   插入的位置j+1
20             {
21                 break;    
22             }
23         }
24         if(j != i-1)
25         {
26             arr[j+1] = num;    
27         }
28     }
29 }
30 
31 void travel(int arr[],int len)
32 {
33     for(int i=0;i<len;i++)
34     {
35         printf("%d ",arr[i]);    
36     }    
37     printf("
");
38 }
39 
40 int main()
41 {
42     int arr[] = {53,82,9,233,43,14,55,9,4,67};
43     int len = sizeof(arr)/sizeof(arr[0]);
44 
45     travel(arr,len);
46     insert_sort(arr,len);
47     travel(arr,len);
48 
49 /*    travel(arr,len);
50     binary_insert_sort(arr,len);
51     travel(arr,len);*/
52 
53 /*    travel(arr,len);
54     shell_sort(arr,len);
55     travel(arr,len);*/
56 }

4、测试结果