1664_基于列表的插入排序（选做题，为时间充裕的同学而准备）

可以采用邓老师的指针式列表存储数据，亦可以采用以下“静态列表”存储方式。

列表 List 的数据类型如下：

#define MAX_SIZE 100000

/// 节点基础数据类型
typedef struct Node {
    int  id;  /// 员工编号
    char  name[20];  /// 员工名字
    int  succ;  /// 本节点的下一个元素所在位置的下标
    int  pred;  /// 本节点的上一个元素所在位置的下标
} mytype;

typedef struct {
    mytype data[ MAX_SIZE ];  /// 列表元素存放的数组
    bool used[ MAX_SIZE ];   /// 单元是否被占用的标记
    int head, tail;  /// 首元素的下标位置，尾元素的下标位置
    int _size;  /// 列表元素的实际个数
} mylist;

需要用到的函数原型如下：

void init( mylist &L )  /// 初始化列表L

int inputList( mylist &L )   /// 读入列表

int search ( mylist &L, int r, mytype e )  /// 对列表L，从列表头开始的r个元素中，找到不比e大的最后(最大)一个元素

void removeNode( mylist &L, int tmax )  /// 摘除 列表L 中 下标为 tmax 的元素 ，但并不释放单元    

int insertionSort( mylist &L, int beginPos, int n ) /// 对列表进行选择排序

void traverse( mylist &L ) /// 遍历列表L ，输出每个节点

当然，没采用插入排序法的AC代码，是要判cheat且封号的。

第一行是一个正整数n，表示列表共有n个节点。( 0 < n < 100000 ）

接下来n行，每行是一个非负整数 id 和 一个字符串 str ，按顺序表示列表的每一个节点，节点的员工编号是id (不一定唯一)、姓名是str 。员工姓名字符串不含空格，0 < |str| < 20

按员工id号非降序执行选择排序，排序后，输出n行：先输出员工id，再输出员工名字。

5
1 Tom
4 Jack
3 Alice
1 Bob
2 Apple

1 Tom
1 Bob
2 Apple
3 Alice
4 Jack