哨兵排序算法

代码展示 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 20
//直接排序
typedef struct
{int r[MAXSIZE + 1];int length;
} SqList;
int InsertSort(SqList* 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];//设置哨兵L->r[i] = L->r[i - 1];//交换位置for (j = i - 2; L->r[0] < L->r[j]; j--){L->r[j + 1] = L->r[j];}L->r[j + 1] = L->r[0];}printf("第%d躺排序结果:", i-1);for (int k = 1; k <= L->length; k++){/* if (k == L->length)printf("%d", L->r[k]);else*/printf("%d ", L->r[k]);}printf("\n");}return 1;
}
// 时间复杂度：O(n^2)  n为元素个数
int main()
{SqList L;int n;while (scanf("%d", &n) != -1){L.length = n;for (int i = 1; i <= L.length; i++){scanf("%d", &L.r[i]);}L.r[0] = -1;//数组下标为0的位置初始值为-1，设置为哨兵InsertSort(&L);}return 0;
}

运行结果与画图理解分析

第一行：输入数据的个数

第二行：从数组下标为1开始输入数据

数组下标为0的位置初始值为-1，设置为哨兵