示例代码

示例代码为C语言，输入参数中，需要 排序的数组为array[],起始索引为first，终止索引为last。示例代码的函数采用in-place排序，调用完成后，array[]中从 first到last处于升序排列。

void insertion_sort(char array[], unsigned int first, unsigned int last)
 {
  int i,j;
  int temp;
  for (i = first+1; i<=last;i++)
  {
   temp = array[i];
   j=i-1;
 
   //与已排序的数逐一比较，大于temp时，该数移后
   while((j>=first) && (array[j] > temp))
   {
    array[j+1] = array[j]; 
    j--;
   }
 
   array[j+1] = temp; 
  }
 }

这个更好:

void InsertSort(char array[],unsigned int n)
 {
    int i,j;
    int temp;
    for(i=1;i<n;i++)
    {
      temp = array[i];//store the original sorted array in temp
      for(j=i ; j>0 && temp < array[j-1] ; j--)//compare the new array with temp
      {
          array[j]=array[j-1];//all larger elements are moved one pot to the right
      }
     array[j]=temp;
    }
 }

这个是c++语言版 本的插入排序。为了支持list使用了std::advance()。

#include 
 
template<typename biIter>
void insertion_sort(biIter begin, biIter end)
  {
    typedef typename std::iterator_traits<biIter>::value_type value_type;
    biIter bond = begin;
    std::advance(bond, 1);
    for(; bond!=end; std::advance(bond, 1)) {
      value_type key = *bond;
      biIter ins = bond;
      biIter pre = ins;
      std::advance(pre, -1);
      while(ins!=begin && *pre>key) {
        *ins = *pre;
        std::advance(ins, -1);
        std::advance(pre, -1);
      }
      *ins = key;
    }
  }

以下是PASCAL语言，程序使用链表做插入排序，目的：将读入的英文名字按字典序排列

TYPE
link=^node;
node=record
      data:string;
      next:link;
     end;
VAR
 
p,q,head,n:link;
t,m:integer;
f1,f2:text;
i:string;
BEGIN
 
assign(f1,'lianbiao-name-in.txt');
reset(f1);
assign(f2,'lianbiao-name-out.txt');
rewrite(f2);
head:=nil;
read(f1,t);
readln(f1);
read(f1,i);
new(p);
p^.data:=i;
p^.next:=nil;
head:=p;
readln(f1);
read(f1,i);
FOR m:=2 TO t DO
 BEGIN
  p:=head;
  new(n);
  n^.data:=i;
  while (i>p^.data) and (p^.next<>nil) do
   begin
    q:=p;
    p:=p^.next;
   end;
  if idata then begin
                        n^.next:=head;
                        head:=n;
                       end
                  else if (i>p^.data) and (p^.next=nil) then begin
                                                              p^.next:=n;
                                                              n^.next:=nil;
                                                             end
                                                        else begin
                                                              q^.next:=n;
                                                              n^.next:=p;
                                                             end;
  readln(f1);
  read(f1,i);
 end;
p:=head;
while p<>nil do
 begin
  write(f2,p^.data,' ');
  p:=p^.next;
 end;
CLOSE(f1);
CLOSE(f2);
END.