简要步骤

直接插入排序正如名字所示，它的工作过程就是：对于一个待插数据，将其与前面的数据依次比较，直至找到正确的插入位置。

初始序列：{ 4, 6, 3, 0, 2, 5, 1 }

和简单选择排序相比，直接插入排序当找到正确的位置时，扫描就停止了；而简单选择排序即使在正确的位置放上了正确的数，它也会继续扫描完，因为它不知道后面有没有数比这个数好。例如序列{1, 2, 4, 5, 3}:

直接插入排序的平均时间复杂度虽然也为O( N^2 )，但是它避免了一些无用的比较工作，所以在性能上是优于冒泡和简单选择排序的。

性能分析

时间复杂度：当数据正序时，因为不需要移动数据，所以效率最高，时间复杂度为O( N )；当数据反序时，因为每次插入都需要移动数据，所以效率最差，时间复杂度为O( N^2 );

空间复杂度：在插入过程中，需要一个额外临时辅助空间用来保存待插入的值，所以空间复杂度为O( 1 )。

优化

因为在插入数据时，被插序列是有序的，所以我们可以引入折半法来寻找插入点。折半插入法可以有效减少比较次数，但是并不能减少移动次数，所以折半插入和直接插入排序的平均时间复杂度相同，都是O( N^2 )。

代码

#include <stdio.h> /* * 直接插入排序 */ void InsertSort(int arr[], int length) { int temp; int i,j; for (i = 1; i < length; i++) { temp = arr[i]; for (j = i - 1; j >= 0 && arr[j] > temp; j--) arr[j + 1] = arr[j]; arr[j + 1] = temp; } } /* * 折半插入排序 */ void BiInsertSort(int arr[], int length) { int temp; int low,high,mid; int i,j; for (i = 1; i < length; i++) { temp = arr[i]; low = 1; high = i - 1; while(low <= high) { mid = (low + high)/2; if(arr[mid] < arr[i]) low = mid + 1; else high = mid - 1; } for (j = i - 1; j >= 0 && arr[j] > temp; j--) arr[j + 1] = arr[j]; arr[j + 1] = temp; } } int main() { int arr[] = {4,6,3,0,2,5,1}; int length = sizeof(arr)/sizeof(arr[0]); printf("排序前:"); for(int i=0; i<length; i++) { printf(" %d",arr[i]); } BiInsertSort(arr, length); printf("\n排序后:"); for(int i=0; i<length; i++) { printf(" %d",arr[i]); } return 0; }