#include <stdio.h>
#include <stdlib.h>void PrintHeap(const char* strMsg,int array[],int nLength);
void InsertionSort1(int *items, int count) 
void InsertionSort2(int a[],int size);
void PrintArray(const char* strMsg,int array[],int nLength);int main(int argc, char *argv[])
{
  int data[13]={8,5,4,6,13,7,1,9,12,11,3,10,2};
  InsertionSort1(data,13);
  PrintArray("Insertion Sort:",data,13);
  
  system("PAUSE");    
  return 0;
}/*
插入排序思路：
    将数组分成两个区域：已排序区域和未排序区域。首先假设数组的第一个元素处于已排序区域，
    第一个元素之后的所有元素都处于未排序区域。
    排序时用到两层循环，第一层循环用于从未排序区域中取出待排序元素，并逐步缩小未排序区域，
    第二层循环用于从已排序区域中寻找插入位置（即不断地从已排序区域中寻找比待排序元素大的元素，
    然后将较大的已排序区的元素后移，后移的最终结果是已排序区元素的最后一个元素占据
    待排序元素原来的位置，而已排序区中间空出一个位置），最后将待排序元素插入元素后移后留下的空位。 
    注：待排序元素所在位置与已排序元素的最后一个元素是相邻的，因此进行移位循环时第一次后移时将已排序元素的最后一个元素直接移至待排序元素的位置即可。元素比较和元素移位共用一个循环，即边比较边移位。
*/
void InsertionSort1(int *items, int count)              
{                                                  
    int x, y;                             
    int c;                                        
                                                   
    for ( x=1; x<count; ++x )                      
    {                                              
        c = items[x];                              
        for ( y=x-1; (y>=0) && (c<items[y]); y-- ) 
            items[y+1] = items[y];                 
                                                   
        items[y+1] = c;                            
    }                                              
}void InsertionSort2(int a[],int size)
{
     int i,j,v;
     //initially,the first item is considered to be sorted
     //i divides a into a sorted region,x<i,and unsorted one,x>=i
     for(i=1;i<size;i++)
     {
        //select the item at the beginning of the as yet unsorted section
        v=a[i];
        //work backwards through the array,finding where v should go
        j=i;
        //if this element is greater than v,move it up one
        while(a[j-1]>v)
        {
           a[j]=a[j-1];
           j--;
           if(j<=0) break;
        }
        //stopped when a[j-1]<=v,put v at position
        a[j]=v;
     } 
}void PrintArray(const char* strMsg,int array[],int nLength)
{
     int i;
     printf("%s",strMsg);
     for(i=0;i<nLength;i++)
     {
        printf("%d ",array[i]);
     }
     printf("\n");
}