数据结构与算法基础（青岛大学-王卓）

#include <stdio.h>

#include <stdlib.h>

#define MAXSIZE 20

typedef int KeyType; // 设置关键字类型

typedef struct{

  KeyType key; // 关键字

}SListType;

typedef struct{

  List item[MAXSIZE+1]; // 哨兵类型

  int length;

}Slist;

// 初始化数据

void initSList(Slist *L,int length){

  L->item[0].key = 0;

  L->length = length;

  for(int i=1;i<=L->length;i++){

    printf("SList[%d]=%d\n",i,L->item[i].key=rand());

  }

}

// 直接插入排序

void insertSort(Slist *L){

  int i=2,j=0;

  for(i=2;i<=L->length;i++){

    // 当前大于等于前一个直接跳出循环

    if(L->item[i].key >= L->item[i-1].key) continue;

    // 把当前值赋值到哨兵位置

    L->item[0].key = L->item[i].key;

    // 当前小于前一个，把当前位置的值替换成前一个值

    for(j=i-1;L->item[j].key>L->item[0].key;j--){

      L->item[j+1].key = L->item[j].key;

    }

    // 终止判断时，已经往前移了一位，所以才要+1

    L->item[j+1].key = L->item[0].key;

  }

}

// 遍历取出数据

void printfSList(Slist* L){

  for(int i=1;i<=L->length;i++){

    printf("orderSlist[%d]=%d\n",i,L->item[i].key);

  }

}

int main(){

  Slist La;

  initSList(&La,10);

  insertSort(&La);

  printfSList(&La);

  system("pause");

  return 0;

}