BInsertSort

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 #define MAXSIZE 200000
 5 typedef int KeyType;
 6 typedef struct {
 7     KeyType key;
 8 }RedType;
 9 typedef struct {
10     RedType r[MAXSIZE + 1];
11     int length;
12 }SqList;
13 int Random(int start,int end){
14     int dis = end - start;
15     return rand() % dis + start;
16 }
17 void BInsertSort(SqList &L) {
18     double start_time,finish_time,cord_time;
19     start_time = clock();
20     int i,j,low,high,m;
21     for (i = 2; i <= L.length; ++i) {
22         L.r[0] = L.r[i];
23         low = 1; 
24         high = i - 1;
25         while (low <= high) {
26             m = (low + high) /2;
27             if (L.r[0].key < L.r[m].key)
28                 high = m - 1;
29             else 
30                 low = m + 1;
31         }
32         for (j = i - 1; j >= high + 1; --j) {
33             L.r[j + 1] = L.r[j];
34         }
35         L.r[high + 1] = L.r[0];
36     }
37     finish_time = clock();
38     cord_time = (double)(finish_time - start_time) ;
39     printf("BInsertSort time=%f msn",cord_time);
40 }
41 void InPut(SqList &L) {
42     int i;
43     srand((unsigned)time(NULL));
44     cin >> L.length;
45     for (i = 1; i <= L.length; ++i) {
46         // cin >> L.r[i].key;
47         L.r[i].key = Random(1,1000000);
48     }
49 }
50 void OutPut(SqList &L) {
51     int i;
52     for (i = 1; i <= L.length; ++i) {
53         cout << L.r[i].key << " ";
54     }
55 }
56 int main() {
57     SqList L;
58     // L.r = new RedType [MAXSIZE+1];
59     InPut(L);
60     BInsertSort(L);
61     OutPut(L);
62     return 0;
63 }