三种插入排序

 1 #include<iostream>
 2 using namespace std;
 3 //直接插入排序
 4 void InsertSort(int a[], int n)
 5 {
 6     int i, j, key;
 7     for (i = 1; i < n; i++)
 8     {
 9         key = a[i];
10         j = i-1;
11         while (j >= 0 && a[j]>key)
12         {
13             a[j + 1] = a[j];
14             j--;
15         }
16         a[j + 1] = key;
17 
18     }
19 }
20 //希尔插入排序
21 void shellsort(int a[], int n)
22 {
23     int k, i, gap;
24 
25     for (gap = n / 2; gap > 0; gap /= 2) //步长
26     {
27         for (k = 0; k < gap; k++)        //直接插入排序
28         {
29             for (i = k + gap; i < n; i += gap)
30                 //if (a[j] < a[j - gap])
31             {
32                 int key = a[i];
33                 int j = i - gap;
34                 while (j >= 0 && a[j] > key)
35                 {
36                     a[j + gap] = a[j];
37                     j -= gap;
38                 }
39                 a[j + gap] = key;
40             }
41         }
42     }
43 }
44 //二分插入
45 void binsert(int a[], int n)
46 {
47     int key, left, right;
48     for (int i = 1; i < n; i++)
49     {
50         left = 0;
51         right = i - 1;
52         key = a[i];
53         while (left <= right)
54         {
55             int middle = (left + right) / 2;//最好写成 right+(right-left)/2;
56             if (a[middle]>key)
57                 right = middle - 1;
58             else
59                 left = middle + 1;
60         }
61         for (int j = i - 1; j >= left; j--)
62         {
63             a[j + 1] = a[j];
64         }
65         a[left] = key;
66 
67     }
68 }
69 
70 int main()
71 {
72     int a[10];
73     for (int i = 0; i < 10; i++)
74         cin >> a[i];
75     for (auto t : a)
76         cout << t << " ";
77     cout << endl;
78     InsertSort(a, 10);// 直接插入排序
79     for (auto t : a)
80         cout << t << " ";
81     cout << endl;
82     shellsort(a, 10); //希尔排序
83     for (auto t : a)
84         cout << t << " ";
85     cout << endl;
86     binsert(a, 10);  // 二分插入
87     for (auto t : a)
88         cout << t << " ";
89     cout << endl;
90     system("pause");
91     return 0;
92 }