插入排序

插入排序

维基百科，自由的百科全书

插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下： 从第一个元素开始，该元素可以认为已经被排序

取出下一个元素，在已经排序的元素序列中从后向前扫描 如果该元素（已排序）大于新元素，将该元素移到下一位置 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置中 重复步骤2

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。 示例代码

示例代码为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

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(maybe -1?) {

array[j]=array[j-1];//all larger elements are moved one pot to the right }

array[j]=temp; } }

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

#include

template

void insertion_sort(biIter begin, biIter end) {

typedef typename std::iterator_traits::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 i

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.

算法复杂度

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说插入排序算法复杂度为O(n2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。

插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。 本节介绍两种插入排序方法：直接插入排序和希尔排序。

直接插入排序基本思想

1、基本思想

假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。

2、第i-1趟直接插入排序：

通常将一个记录R[i](i=2，3，…，n-1)插入到当前的有序区，使得插入后仍保证该区间里的记录是按关键字有序的操作称第i-1趟直接插入排序。 排序过程的某一中间时刻，R被划分成两个子区间R[1．．i-1]（已排好序的有序区）和R[i．．n]（当前未排序的部分，可称无序区）。

直接插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1．．i-1]中适当的位置上，使R[1．．i]变为新的有序区。因为这种方法每次使有序区增加1个记录，通常称增量法。

插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理，此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这