直接插入排序:
将一个元素通过和当前已经排序好的数组的最大元素进行比较,并在待插入数组较小的情况下通过设置哨兵,整体移动,插入正确位置的步骤,从此得到一个新的排序好的数组的过程。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| #include <stdio.h>
#define MAXSIZE 100
typedef struct { int r[MAXSIZE+1]; int length; }SortList;
void InsertSort(SortList *L) { int i,j; for(i=2;i<=L->length;i++) { if (L->r[i]<L->r[i-1]) { L->r[0]=L->r[i]; for(j=i-1;L->r[j]>L->r[0];j--) L->r[j+1]=L->r[j]; L->r[j+1]=L->r[0]; } } }
|
直接插入排序时间复杂度分析:
最好的情况下,即每次需要插入的元素都是最大的,这样只需要比较n-1次,没有移动记录,所以时间复杂度为O(n)。
最坏的情况下,即待排序的是逆序的,此时需要比较的次数为:2+3+4+…+n=(n+2)(n-1)/2,而移动的次数为:(n+4)(n-1)/2。总得时间复杂度为O(n^2)。
直接插入排序算法比冒泡和简单排序算法的性能要好一点。