折半插入排序

直接插入需要在有序数据一个个查找,找到插入位置,然后插入, 效率较慢;折半插入是使用二分查找在有序区间查找插入位置,减少查找量。

总的来说,折半插入排序就是折半查找+插入排序。关于直接插入排序可以看这一篇 文章

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)
{
// 假设初始有序序列为R[0]
for (int i = 1; i < len; i++)
{
int temp = R[i];
int low = 0, high = i - 1; // 设置折半查找范围
while (low <= high) // 开始在有序序列中进行折半查找,
//low为最终查找到的插入位置
{
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;
}

运行结果
binary_insertion_sort

时间复杂度: O(n^2)