插入排序

插入排序，这是一个对少量元素进行排序的有效算法。

看代码先：

1. #include <iostream>
2. #define Max 100
3.  
4. using namespace std;
5.  
6. void Insertion_Sort(int a[],int n)
7. {
8.      for(int j=1;j<n;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 n,a[Max]={0};
24.     cin>>n;
25.     for(int i=0;i<n;i++)
26.         cin>>a[i];
27.     Insertion_Sort(a,n);
28.     for(int i=0;i<n;i++)
29.         cout<<a[i]<<' ';
30.     cout<<endl;
31.     system("Pause");
32.     return 0;
33. }

代码分析：

此程序实现对n个整型数据的排序，主要部分为6~19行的Insertion_Sort()函数。在函数中外循环变量j从数组a中的第二个元素（a[1]）开始一次向后直到数组最后一个元素(a[n-1])，用变量key记录当前外循环变量j所在元素的值，定义变量i存放j前面一个数的下标，在内循环中，从a[i]开始(刚开始i=j-1)向前依次和key（即外循环j所在位置元素）进行比较，如果a[i]>key，那么就把a[i]移到a[i+1]位置去，然后i向前移动，只要满足内循环条件则重复操作！否则i后面的那个数据存放key值，内循环结束。

操作图解：

对{5,2,4,6,1,3}这列数字进行排序的步骤如下：

初始状态。

第一步，由于5>2所以交换 (j=1, i=0, a[i]=5, key=2)

            由于i<0小循环结束 (j=1, i=-1, key=1)

            a[0]=key.

第二步，由于5>4所以交换 (j=2, i=1, a[i]=5, key=4)

            由于2<4小循环结束 (j=2, i=0, a[i]=2, key=4)

            a[1]=key.

第三步，由于6>5所以不交换 (j=3, i=2, a[i]=5, key=6)

            a[3]=key.

第四步，由于6>1所以6向后移 (j=4, i=3, a[3]=6, key=1)

            由于5>1所以5向后移 (j=4, i=2, a[2]=5, key=1)

            由于4>1所以4向后移 (j=4, i=1, a[1]=4, key=1)

            由于2>1所以2向后移 (j=4, i=0, a[0]=2, key=1)

            由于i<0小循环结束 (j=4, i=-1, key=1)

            a[0]=key.

第五步，由于6>3所以6向后移 (j=5, i=4, a[i]=6, key=3)

            由于5>3所以5向后移 (j=5, i=3, a[3]=5, key=3)

            由于4>3所以4向后移 (j=5, i=2, a[2]=4, key=3)

            由于2<3小循环结束 (j=5, i=1, key=3)

            a[2]=key.