直接插入需要在有序数据一个个查找,找到插入位置,然后插入, 效率较慢;折半插入是使用二分查找在有序区间查找插入位置,减少查找量。
总的来说,折半插入排序就是折半查找+插入排序。关于直接插入排序可以看这一篇 文章 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| #include <iostream> #include <stdio.h> #include <cstdio> #include <vector> #include <algorithm> #include "dbg.h" using namespace std;
void binaryInsetionSort(int R[], int len) { for (int i = 1; i < len; i++) { int temp = R[i]; int low = 0, high = i - 1; while (low <= high) { int mid = low + (high - low) / 2; if (R[mid] > temp) high = mid - 1; else low = mid + 1; }
for (int j = i - 1; j >= low; j--) R[j + 1] = R[j]; R[low] = temp; } }
int main(int argc, char *argv[]) { int R[] = {1, 3, 2, 18, 3, 28, 23, 38, 7, 8}; cout << "Before sorting: " << endl; dbg(R); int len = sizeof(R) / sizeof(R[0]); cout << "After sorting : " << endl; binaryInsetionSort(R, len); dbg(R); return 0; }
|
运行结果
时间复杂度: O(n^2)