定义

直接插入排序（Straight Insertion Sort） 的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1 的有序表。

算法思路

1. 设置哨兵：从下标 i=2 开始，取出该元素作为哨兵。
2. 从哨兵位置开始，哨兵挨个与之前的元素比较，如果比前面元素小，则把该元素后移一位。
3. 当不满足第2个条件时，取出哨兵到当前位置。

算法实现

#include <stdio.h>

#define MAXSIZE 5

typedef struct {
  int array[MAXSIZE + 1]; /* array[0] 作为哨兵 */
  int length;
} SqList;

void StraightInsertionSort(SqList *L) {
  int i, j;
  for (i = 2; i <= L->length; i++) {
    L->array[0] = L->array[i]; /* 设置哨兵 */
    j = i - 1;
    while (L->array[0] < L->array[j]) { /* 与前面元素比较 */
      L->array[j + 1] = L->array[j];    /* 后移 */
      j--;
    }
    L->array[j + 1] = L->array[0]; /* 插入哨兵到正确位置 */
  }
}

int main(void) {
  SqList L;
  int i;
  L.length = 5;
  L.array[1] = 9;
  L.array[2] = 1;
  L.array[3] = 5;
  L.array[4] = 8;
  L.array[5] = 3;

  printf("原始数组：");
  for (i = 1; i <= L.length; i++) {
    printf("%d ", L.array[i]);
  }
  printf("\n");

  StraightInsertionSort(&L);

  printf("排序后的数组：");
  for (i = 1; i <= L.length; i++) {
    printf("%d ", L.array[i]);
  }
  printf("\n");

  return 0;
}

原始数组：9 1 5 8 3 
排序后的数组：1 3 5 8 9 

[Done] exited with code=0 in 0.406 seconds

复杂度

最坏情况（逆序）
每插入一个元素都要和前面所有元素比较并移动：

• 第2个元素比较1次
• 第3个元素比较2次
  …
• 第n个元素比较n-1次

总比较/移动次数为：

1 + 2 + ... + (n-1) = n(n-1)/2

所以时间复杂度为 O(n²)。

最好情况（已排序）
每次只需比较一次，不需要移动：

比较次数 = n-1

时间复杂度为 O(n)。

空间复杂度
只用常数个辅助变量（如哨兵），空间复杂度为 O(1)。