数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 中的二分插入排序
二分插入排序是一种特殊形式的插入排序，它使用二分搜索算法查找数组中插入元素的正确位置。
插入排序是一种通过查找数组中元素的正确位置，然后将其插入其正确位置的排序技术。
二分搜索是一种通过查找数组的中间值查找元素的搜索技术。
由于二分搜索的复杂度是 O(log n)，因此搜索算法的时间复杂度也将降低到 O(log n)。
二分插入排序的实现。这个程序是一个简单的插入排序程序，但使用了二分搜索，而不是标准的搜索技术。
示例
#include <iostream>
using namespace std;
int binarySearch(int arr[], int item, int low, int high) {
if (high <= low)
return (item > arr[low])? (low + 1): low;
int mid = (low + high)/2;
if(item == arr[mid])
return mid+1;
if(item > arr[mid])
return binarySearch(arr, item, mid+1, high);
return binarySearch(arr, item, low, mid-1);
}
void BinaryInsertionSort(int arr[], int n) {
int i, loc, j, k, selected;
for (i = 1; i < n; ++i) {
j = i - 1;
selected = arr[i];
loc = binarySearch(arr, selected, 0, j);
while (j >= loc) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = selected;
}
}
int main() {
int arr[] = {12, 56, 1, 67, 45, 8, 82, 16, 63, 23};
int n = sizeof(arr)/sizeof(arr[0]), i;
BinaryInsertionSort(arr, n);
cout<<"Sorted array is : \n";
for (i = 0; i < n; i++)
cout<<arr[i]<<"\t";
return 0;
}输出
Sorted array is : 1 8 12 16 23 45 56 63 67 82
更新日期：2019-11-22
4K+ 浏览
广告