算法导论 第二章

 1 #include <iostream>
 2 
 3 using namespace std;
 4 void insert_sort(int *datas, int length);
 5 int main()
 6 {
 7    int a[10]={1,2,4,35,6,1,4,7,9,7};
 8    insert_sort(a,10);
 9     return 0;
10 }
11 
12 void insert_sort(int *datas,int length)
13 {
14     int i,j;
15     int key,tmp;
16     //判断参数是否合法
17     if(NULL == datas || 0==length)
18     {
19        cout<<"Check datas or length.\n";
20         //exit(1);
21     }
22     //数组下标是从0开始的，从第二个元素（对应下标1）开始向前插入
23     for(j=1;j<length;j++)
24     {
25         key = datas[j];  //记录当前要插入的元素
26         i = j-1;  //前面已经有序的元素
27       //寻找待插入元素的位置，从小到到排序，如果是从大到小改为datas[i]<key
28         while(i>=0 && datas[i] > key)
29         {
30             datas[i+1] = datas[i];
31             i--;   //向前移动
32         }
33         datas[i+1] = key;  //最终确定待插入元素的位置
34     }
35     for(int i =0;i<10;i++)
36     {
37         cout<<datas[i]<<endl;
38     }
39 }