直接插入排序

算法思想

用i将L[0..n]分成L[0..i-1]和L[i..n]，L[0..i-1]为有序表，然后将L[i..n]中的所有元素以此的插入到前一表中，可以使用改进的哨兵的方式

代码

//直接插入排序,使用哨兵的形式进行，减少了一次比较
void sort(int array[], int n){
    int i,j;
    for(i = 2; i < n; i++){
        array[0] = array[i];  //array[0]不存储数据
        for(j = i-1;array[0] < array[j]; j--) //不断在有序表中查找对应的位置，其结束条件是当需要插入的值出现在表中或者出现大于
            array[j+1] = array[j];            //要查找的数据那么就将数据插入到结束的前一个位置
            
        array[j] = array[0];
    }
}