插入排序(减常数)c++
时间: 2024-06-08 09:04:02 浏览: 9
插入排序是一种简单直观的排序算法,它的基本思想是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。在C++中,为了达到减常数的时间复杂度优化,我们可以使用二分查找来确定新元素的插入位置,这样可以在平均和最好情况下将时间复杂度降低到O(n)。
以下是插入排序的一个优化版本,利用了二分查找来加速查找插入位置的过程:
```cpp
#include <vector>
#include <algorithm> // 引入二分查找
// 函数模板实现插入排序
template<typename T, typename Compare = std::less<T>>
void insertion_sort_optimized(std::vector<T>& arr, Compare compare = Compare()) {
if (arr.empty() || arr.size() == 1) return; // 空数组或只有一个元素无需排序
for (size_t i = 1; i < arr.size(); ++i) {
T key = arr[i];
size_t j = std::upper_bound(arr.begin(), arr.begin() + i, key, compare) - arr.begin(); // 用二分查找法找插入位置
// 将arr[i]放到正确的位置
for (size_t k = i; k > j; --k) {
arr[k] = arr[k - 1]; // 逐步后移元素
}
arr[j] = key; // 插入关键值
}
}
// 示例
int main() {
std::vector<int> vec = {9, 5, 2, 7, 1};
insertion_sort_optimized(vec);
for (const auto& num : vec) {
std::cout << num << " ";
}
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)