插入排序源码：

1 #include 
      
        2 #include 
       
         3  4 using namespace std; 5  6 void insert_sort(int a[]) 7 { 8     for(int j=1;j<10;j++) 9     {10         int key=a[j];11         int i=j-1;12         while(i>=0 && a[i]>key)13         {14             a[i+1]=a[i];15             i--;16         }17         a[i+1]=key;18     }19 }20 21 int main()22 {23     int a[10];24     int i;25     for(i=0;i<10;i++)26         scanf("%d",&a[i]);27     insert_sort(a);28     for(i=0;i<10;i++)29         printf("%3d",a[i]);30     puts("");31     return 0;32 }
       
      

逆序输出：

1 #include 
      
        2 #include 
       
         3  4 using namespace std; 5  6 void insert_sort(int a[]) 7 { 8     for(int j=1;j<10;j++) 9     {10         int key=a[j];11         int i=j-1;12         while(i>=0 && a[i]
       
      

分治法：合并排序

对于两堆以排好序的，最底层的运行逻辑：

1 #include 
      
        2 #include 
       
         3 #define inf 1e9 4 using namespace std; 5  6 void merge_sort(int a[],int p,int q,int r) 7 { 8     int n1=q-p+1; 9     int n2=r-q;10     int i,j;11     int L[n1+1],R[n2+1];12     for(i=0;i
       
      

 一般性源码：

1 #include 
      
        2 #include 
       
         3  4 #define inf 1e9 5  6 using namespace std; 7  8 void merge_sort(int a[],int p,int q,int r) 9 {10     int n1=q-p+1;11     int n2=r-q;12     int L[n1+1],R[n2+1];13     int i,j;14     15     for(i=0;i
        
         =r)39         return;40     int q=(p+r)/2;41     Merge_sort(a,p,q);42     Merge_sort(a,q+1,r);43     merge_sort(a,p,q,r);44 }45 46 int main()47 {48     int a[10];49     int i;50     for(i=0;i<10;i++)51         scanf("%d",&a[i]);52     Merge_sort(a,0,9);53     for(i=0;i<10;i++)54         printf("%3d",a[i]);55     puts("");56     return 0;57 }
        
       
      

不设置哨兵

1 #include 
      
        2 #include 
       
         3  4  5 using namespace std; 6  7 void merge_sort(int a[],int p,int q,int r) 8 { 9     int n1=q-p+1;10     int n2=r-q;11     int L[n1+1],R[n2+1];12     int i,j;13     14     for(i=0;i
        
         =r)52         return;53     int q=(p+r)/2;54     Merge_sort(a,p,q);55     Merge_sort(a,q+1,r);56     merge_sort(a,p,q,r);57 }58 59 int main()60 {61     int a[10];62     int i;63     for(i=0;i<10;i++)64         scanf("%d",&a[i]);65     Merge_sort(a,0,9);66     for(i=0;i<10;i++)67         printf("%3d",a[i]);68     puts("");69     return 0;70 }
        
       
      

利用归并排序求逆序数

1 #include 
      
        2 #include 
       
         3 #define inf 1e9 4  5 using namespace std; 6 int cnt; 7  8 void merge_sort(int a[],int p,int q,int r) 9 {10     int n1=q-p+1;11     int n2=r-q;12     int L[n1+1],R[n2+1];13     int i,j;14     15     for(i=0;i
        
         =r)41         return;42     int q=(p+r)/2;43     Merge_sort(a,p,q);44     Merge_sort(a,q+1,r);45     merge_sort(a,p,q,r);46 }47 48 int main()49 {50     int a[8];51     int i;52     for(i=0;i<5;i++)53         scanf("%d",&a[i]);54     cnt=0;55     Merge_sort(a,0,4);56     for(i=0;i<5;i++)57         printf("%3d",a[i]);58     puts("");59     printf("%d\n",cnt);60     return 0;61 }