二分插入排序算法c++
时间: 2024-08-01 12:01:18 浏览: 43
二分插入排序是一种基于比较的排序算法,它利用了数组已经部分有序的特点。在C++中,它的基本思想是:
1. 首先,假设数组的第一个元素是已排序的。
2. 然后,从第二个元素开始,对于每个未排序的元素,算法会在已排序的部分找到其正确的位置(通常是中间位置),通过不断将比当前元素大的元素向右移动来完成插入。
3. 插入过程中,每次查找中间位置的过程都是通过二分搜索的方式进行的,这大大减少了查找次数,提高了效率。
4. 当找到正确位置后,将该元素插入到这个位置,并继续处理下一个未排序的元素,直到所有元素都被排序。
以下是简单的C++二分插入排序示例代码:
```cpp
#include <vector>
using namespace std;
void binaryInsertionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int low = 0, high = i - 1;
// 使用二分查找
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] > key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
// 将key插入到低索引处
for (int j = i; j > low; --j) {
arr[j] = arr[j - 1];
}
arr[low] = key;
}
}
// 示例
int main() {
vector<int> arr = {9, 5, 7, 1, 6};
binaryInsertionSort(arr);
for (int num : arr) {
cout << num << " ";
}
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)