数据结构之插入排序：直接插入排序

直接插入排序的定义&＃xff1a;

直接插入排序的原理&＃xff1a;

直接插入排序的代码实现&＃xff1a;

void InsertSort(int a[],int n){int i,j;for(i&＃61;2;i<n;i&＃43;&＃43;){ //依次将A[2]~A[n]插入到前面已排序队列a[0] &＃61; a[i]; //哨兵 for(j&＃61;i-1;a[0] < a[j];j--) //从后往前查找待插入位置a[j&＃43;1] &＃61; a[j]; //后移a[j&＃43;1] &＃61; a[0]; //复制到插入位置}
}


ps&＃xff1a;
哨兵&＃xff1a;不用判断是否比较到了最后一个元素&＃xff1b;保存插入的值。
a[0] 是哨兵&＃xff0c;不存放输入的数据

例&＃xff1a;

直接插入排序的性能&＃xff1a;

空间复杂度&＃xff1a; O(1)
时间复杂度&＃xff1a; O(n^2)

主要来自于对比关键字、移动元素&＃xff0c;若有n个元素&＃xff0c;则需要n-1趟处理
最好&＃xff1a;原本有序&＃61;>O(n)
最坏&＃xff1a;原本逆序&＃61;>O(n^2)
平均&＃xff1a;O(n)

排序算法稳定
顺序和链式都适用