【模板小程序】二分法插入排序

 1 #include <iostream>
 2 #include <vector>
 3 #include <string>
 4 using namespace std;
 5 
 6 void printArray(string str,vector<int>& array){
 7     cout<<str;
 8     for(int val:array){
 9         cout<<val<<" ";
10     }
11     cout<<endl;
12 }
13 
14 void binaryInsertionSort(vector<int>& array) {
15     printArray("原数组：", array);
16     int time=0;
17     for (int i = 1; i < (int)array.size(); ++i) {
18         int temp = array[i];
19         int right = i - 1;
20         int left = 0;
21         int mid;
22         // 定位
23         while (left <= right) {
24             //mid = (left + right) / 2;
25             mid = left+(right-left)/2;
26             if (array[mid] > temp) {
27                 right = mid - 1;
28             } else if (array[mid] < temp) {
29                 left = mid + 1;
30             }
31         }
32         // 移动数组
33         for (int j = i; j > left; j--) {
34             array[j] = array[j - 1];
35         }
36         // 在找到的位置插入
37         array[left] = temp;
38         printArray("第" + to_string(++time) + "次循环排序结果: ", array);
39     }
40 }
41 
42 int main()
43 {
44     vector<int> v={21,8,2,18,0,9,27,12,5,24};
45     binaryInsertionSort(v);
46     return 0;
47 }