資料結構
網路
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+ 瀏覽
廣告