思路:

插入排序法的思路与我们打扑克牌时排列手牌的方法很相似。就拿扑克牌举例子，我们要单手拿牌，然后将牌从左至右，由大到小进行排序。此时我们需要将牌一张张抽出来，分别插入到前面已经排好序的手牌中的适当位置。重复这一操作直到插入最后一张牌，整个排序就完成了。

模版:

insertionSort(A, N)//包含N个元素的0起点数组Afor i 从 1 到 N-1         v = A[i]         j = i - 1         while j >= 0 且 A[j] >v             A[j+1] = A[j]             j--         A[j+1] = v_____________________________________insertionSort(A, N)for( i = 1;i < N; i++){     v = A[i];     j = i - 1 ;     while( j >=0&&A[j] > v)     {         A[j + 1] = A[j];         j--;     }     A[j + 1] = v;}

C++模板

#include 
     
      using namespace std;void insertionSort(int a[],int n){    int i,j,sum;    for(i=1;i
      
       =0&&a[j]>sum)        {            a[j+1]=a[j];            j--;        }        a[j+1]=sum;    }}int main(){    int n,i;    cin>>n;    int a[n];    for(i=0;i
       
        >a[i];    insertionSort(a,n);    for(i=0;i
       
      
     

 

有关插入排序法的时间复杂度:

　　在插入排序法中，我们只将比v(取出的值)大的元素向后平移，不相邻的元素不会直接交换位置，因此整个排序算法十分稳定。

　　然后我们考虑一下插入排序法的时间复杂度。这里需要估算每个 i 循环中A[ j ]元素向后移动的次数。最坏的情况下，每个 i 循环要执行 i 次移动，总共需要 1 + 2 +···+ N - 1=(N² - N)/2次移动，即算法复杂度为O(N²)。

　　在计算复杂度的过程中，可以大致估计一下运算次数，然后只留下对代数式影响最大的项，忽略常数项。比如$\frac{N^2}{2}$-$\frac{N}{2}$，这里的N相对于N²而言就小得足以忽略，然后再忽略掉常数倍$\frac{1}{2}$，得出复杂度与N²成正比。当然，前提是假设这里的N足够大。

　　插入排序法是一种很有趣的算法，输入数据的顺序能大幅度影响它的复杂度。我们前面说它的时间复杂度为O(N²)，也仅是指输入数据为降序排列的情况。如果输入数据为升序排列，那么A[ j ]从头至尾都不需要移动，程序只需要经过N次比较便可执行完毕。可见，插入排序法的优势就在于能快速处理相对有序的数据。

 例题:

　　请编写一个程序，用插入排序法将包含N个元素的数列A按升序排列。程序中包含上述伪代码所表示的算法。为检验算法的执行过程，请输出各计算步骤的数组(完成输入后的数组，以及每次 i 自增后的数组)。

输入 :在第一行输入定义数组长度的整数 N 。在第2行输入 N 个整数，以空格隔开。

输出 :输出总共有 N 行。插入排序法每个计算步骤的中间结果各占用 1 行。数列的各元素之间空 1 个空格。请注意，行尾元素后的空格等多余的空格和换行会被认定为 Presentation Error。

限制 :1≤ N ≤100

　　 0≤A的元素≤1000

输入示例

 

65 2 4 6 1 3

 

输出示例

5 2 4 6 1 32 5 4 6 1 32 4 5 6 1 32 4 5 6 1 31 2 4 5 6 31 2 3 4 5 6

 

C语言

#include 
     
      void trace(int A[],int N){    int i;    for(i=0;i
      
       0)            printf(" ");        printf("%d",A[i]);    }    printf("\n");}void insertionSort(int A[],int N){    int j,i,v;    for(i=1;i
       
        =0&&A[j]>v)        {            A[j+1]=A[j];            j--;        }        A[j+1]=v;        trace(A,N);    }}int main(){    int N,i,j;    int A[100];    scanf("%d",&N);    for(i=0;i
       
      
     

 

 

 例题网址: