一、\(STL\)版本的插入二分排序
#include <bits/stdc++.h>
using namespace std;
const int N = 6;
int a[N] = {3, 2, 1, 4, 5, 7};
void BinInsertSort(int a[], int n) {
for (int i = 1; i < n; i++) { // 把下标0的没处理,做为基础数据,其它的一个个做二分插入排序
int x = a[i]; // 辅助变量x用来保存待排序的元素,因为后面有整体移动的过程,不单独记下来,后面就被改了
// 这个代码其实很巧妙的,一个数组分两半用,一半是待插入的,另一个是插入完的,牛啊!
int pos = lower_bound(a, a + i, x) - a; // 在a数组中,范围[0,a+i)这个前闭后开的区间内查找第一个大于等于x的位置p
for (int j = i - 1; j >= pos; j--) a[j + 1] = a[j]; // 移动元素,腾出空间,将pos位置倒出来
a[pos] = x; // 将待排序的元素插入
}
}
int main() {
// 插入排序+二分
BinInsertSort(a, N);
for (int i = 0; i < N; i++) printf("%d ", a[i]);
return 0;
}
二、手写二分版本的插入二分排序
#include <bits/stdc++.h>
using namespace std;
const int N = 6;
int a[N] = {3, 2, 1, 4, 4, 7};
void BinInsertSort(int a[], int n) {
for (int i = 1; i < n; i++) { // 把下标0的没处理,做为基础数据,其它的一个个做二分插入排序
int x = a[i]; // 辅助变量x用来保存待排序的元素,因为后面有整体移动的过程,不单独记下来,后面就被改了
// 这个代码其实很巧妙的,一个数组分两半用,一半是待插入的,另一个是插入完的,牛啊!
// 手写二分lower_bound模板,左闭右开
int l = 0, r = i; //[0~i-1] <=> [0,i)
while (l < r) {
int mid = (l + r) >> 1;
if (a[mid] >= x)
r = mid;
else
l = mid + 1;
}
// 此处写l,r都是一样的
for (int j = i - 1; j >= r; j--) a[j + 1] = a[j]; // 移动元素,腾出空间,将pos位置倒出来
a[r] = x; // 将待排序的元素插入
}
}
int main() {
// 插入排序+二分
BinInsertSort(a, N);
for (int i = 0; i < N; i++) printf("%d ", a[i]);
return 0;
}
标签:二分,int,插入排序,pos,插入,排序
From: https://www.cnblogs.com/littlehb/p/17137028.html