随手实现, 直接上代码, 如有错误疏漏欢迎指正
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 }