排序算法：折半插入排序
- 格式：pdf
- 大小：54.70 KB
- 文档页数：1
排序算法：折半插⼊排序
算法分析：
（1）时间复杂度
从时间上⽐较，折半查找⽐顺序查找快，所以就平均性能来说，折半插⼊排序优于直接插⼊排序。
折半插⼊排序所需要的关键字⽐较次数与待排序序列的初始排列⽆关，仅依赖于记录的个数。不论初始序列情况如何，在插⼊第i个记录
时，需要经过logi+1(向下取整+1)次⽐较，才能确定它插⼊的位置。所以当记录的初始排列为正序或接近正序时，直接插⼊排序⽐折半插⼊
排序执⾏的关键字⽐较次数要少。
折半插⼊排序的对象移动次数与直接插⼊排序相同，依赖于对象的初始排列。
在平均情况下，折半插⼊排序仅减少了关键字的⽐较次数，⽽记录的移动次数不变。因此，折半插⼊排序的时间复杂度仍然为
O（n^2）。
（2）空间复杂度
折半插⼊排序所需附加存储空间和直接插⼊排序相同，只需要⼀个记录的辅助空间r[0]，所以空间复杂度为O（1）
算法特点：
（1）是稳定排序。
（2）因为要进⾏折半插⼊查找，所以只能⽤于顺序结构，不能⽤于链式结构。
（3）适合初始记录⽆序、n较⼤的情况。
#include
#include
using namespace std;
void BSort(int a[],int n)
{
for (int i = 1; i < n; i++)//数组中的第⼀个元素最为已经排好的序列，所以从数组的第⼆个元素开始排
{
int key = a[i];//带插⼊元素
int low = 0, high = i - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (key < a[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
for (int j = i - 1; j >= high + 1; j--)
{//i-1是已经排好序的序列的数量，high+1是待插⼊的的位置，元素后移腾出high+1这个位置
a[j + 1] = a[j];
}
a[high + 1] = key;
}
}
int main()
{
int a [11] = { 2,6,4,5,54,53,53,5,34,34,32};
BSort(a, 11);
for (int i = 0; i < 11; i++)
{
cout << a[i] << " ";
}
return 0;
}
