C++ 折半插入排序

 1 //折半插入排序 : 时间复杂度为n^2
 2 void binary_insert_sort(std::vector<size_t> &arr)
 3 {
 4   for (size_t idx = 0; idx < arr.size(); ++idx)
 5   {
 6     size_t curr_val    = arr[idx];      //当前索引值
 7     size_t curr_pos    = idx;           //当前索引初始位置
 8     size_t compare_pos = curr_pos / 2;  //比较索引初始位置
 9     bool   needInsert  = false;         //是否需要插入当前值
10 
11     while (true)
12     {
13       //同一位置不比较
14       if (curr_pos == compare_pos) break;
15 
16       if (curr_val < arr[compare_pos])
17       {
18         //将当前位移动至比较位, 下一个比较位为当前位折半
19         curr_pos    = compare_pos;
20         compare_pos = curr_pos / 2;
21         needInsert  = true;
22       }
23       else
24       {
25         //当前比较位为当前位的前一位则退出
26         if (compare_pos == (curr_pos - 1)) break;
27 
28         //下一个比较位为当前位到当前比较位之间折半
29         compare_pos = (compare_pos + curr_pos) / 2;
30       }
31     }
32 
33     if (needInsert)
34     {
35       //将当前值插入到当前索引位
36       arr.erase(arr.begin() + idx);
37       arr.insert(arr.begin() + curr_pos, curr_val);
38     }
39   }
40 }