[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的这个元素插入到前面 前面数组是有序 7for(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+120 {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 {33for(int i=0;i<len;i++)34{35 printf("%d ",arr[i]); 36} 37printf("\n");38 }39 40 int main()41 {42int arr[] = {53,82,9,233,43,14,55,9,4,67};43int len = sizeof(arr)/sizeof(arr[0]);44 45travel(arr,len);46insert_sort(arr,len);47travel(arr,len);48 49 /* travel(arr,len);50binary_insert_sort(arr,len);51travel(arr,len);*/52 53 /* travel(arr,len);54shell_sort(arr,len);55travel(arr,len);*/56 }

4、测试结果