期末的信息技术考砸了，原来是一道插入排序法的顺序实现忘记了，被扣掉了30分。

究其原因是插入排序法的数组实现太烂，QB是垃圾（没有指针）~~~~~~~~~~~~~~~~~~~

个人认为插入排序法用顺序实现不是很好的办法，因为插入的过程中要移动一大堆连续的数据，显然用数组实现（一个一个移动）是很费时的。若用链表则可以省下很多时间，源码如下（pascal）：

一、单向链表实现：

program lian;
type
  pt=^node;
  node=record                        {记录体，有两个域：值和后继指针}
     value:integer;
     next:pt;
    end;
var
  x:integer;
  p,q,h,k,y,z:pt;
procedure create(var head:pt);             {建表}
  begin
    new(head);
    writeln('Create');
    p:=head;
    readln(x);
    while x<>0 do
    begin
      new(q);
      q^.value:=x;
      p^.next:=q;
      p:=q;
      readln(x);
    end;
    p^.next:=nil;
  end;
procedure print(head:pt);               {打印链表}
  begin
    writeln('print');
    p:=head;
    while p^.next<>nil do
    begin
      writeln(p^.next^.value);
      p:=p^.next;
    end;
    readln;
  end;
begin
  create(h);
  k:=h^.next^.next;  {k为抓起的牌，初始化k为第二个数}
  y:=h^.next;        {因为单向链表的缺陷，所以需要记录k的前趋y}
  while k<>nil do    {排序主循环体}
  begin
    p:=h^.next;      {p为要比较的数}
    z:=h;            {z为p的前趋}
    while k^.value>p^.value do   {移动前定位}
    begin
      z:=z^.next;                 {若p<k，p取后一位的值，继续定位}
      p:=p^.next;
    end;
    if p<>k then                  {若属要移动}
    begin
      y^.next:=k^.next;           {把k从原位挤出}
      z^.next:=k;                 {这两句把k插入到p的前面}
      k^.next:=p;
      k:=y^.next;                 {k取后一位，继续循环}
    end
    else                          {若不用移动}
    begin
      k:=k^.next;                 {k取后一位，继续循环}
      y:=y^.next;
    end;
  end;
  print(h);
end.

二、双向链表实现：

program lian2;
type
  pt=^node;
  node=record               {记录体，有三个域：前趋、值和后继}
        ahead:pt;
        value:integer;
        next:pt;
    end;
var
  x:integer;
  p,q,he,la,v,k:pt;
procedure create(var head,last:pt);{建表，以head为头last为尾}
  begin
    new(head);
    writeln('Create');
    p:=head;
    read(x);
    while x<>0 do
    begin
      new(q);
      q^.value:=x;
      p^.next:=q;
      q^.ahead:=p;
      p:=q;
      read(x);
    end;
    new(last);
    p^.next:=last;
    last^.ahead:=p;
  end;
procedure print(head,last:pt;flag:boolean);{打印链表flag决定顺打和逆打}
  begin
    writeln('print');
    if flag then                  {顺打，从头到尾}
    begin
      p:=head;
      while p^.next<>last do
      begin
        writeln(p^.next^.value);
        p:=p^.next;
      end;
    end
    else                          {逆打，从尾到头}
    begin
      p:=last;
      while p^.ahead<>head do
      begin
        writeln(p^.ahead^.value);
        p:=p^.ahead;
      end;
    end;
  end;

begin             {main}
  create(he,la);
  k:=he^.next^.next;             {k为抓起的牌，初始为第二个值}
  while k<>la do                 {排序主循环}
  begin
    p:=he^.next;                 {p为比较的牌，每次循环初始为第一个值}
    v:=k^.next;                  {由于k可能会移动，记下k的位置}
    while k^.value>p^.value do   {移动前定位}
      p:=p^.next;                {若p<k，p取后一位的值，继续定位}
    if p<>k then                 {若要移动}
    begin
      k^.ahead^.next:=k^.next;   {这两句把k从原位挤出}
      k^.next^.ahead:=k^.ahead;
      p^.ahead^.next:=k;         {这四句把k插入到新位置}
      k^.ahead:=p^.ahead;
      p^.ahead:=k;
      k^.next:=p;
    end;
    k:=v;                        {k取后一位的值，继续循环}
  end;
  print(he,la,true);
  {打印链表，这里是顺打，升序；你可以用false来逆打，降序}
end.