数据结构-插入排序-折半插入排序

插入排序：

①直接插入排序。

②折半插入排序。←this

③2-路插入排序。←this

④表插入排序。

⑤希尔排序。

折半插入排序

描述过程：查找的操作可以利用“折半查找”（二分）来实现，在进行插入排序。

伪代码：

输入：n个元素的数组A[1~n] 。

输出：按非降序排列的数组A[1~n]

for i ←2 to n x ←A[i] low ←0,high ←i-1 while(low<=high) m ←(low+high)/2 if(x<A[m]) high=m-1; else low=m+1; end while for j ←i-1 to high+1 A[j+1] ←A[j] end for A[j+1] ←x end for

最好：已按非降序排序，比较次数为：n-1

最坏：元素已按降序排序，比较次数为：n*logn

时间复杂度：O(n2)时间复杂度：O(n2)折半查找只是减少了比较次数，但是元素的移动次数不变

#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int N=10; void BInsertSort(int *a,int st,int ed){ for(int i=st+1;i<ed;i++){ int x=a[i]; int low=st,high=i-1; while(low<=high){ int m=(low+high)/2; if(x<a[m]) high=m-1; else low=m+1; } for(int j=i-1;j>=high+1;--j) a[j+1]=a[j]; a[high+1]=x; } } int main() { int a[N]={5,6,3,2,1,8,9,7,4,10}; BInsertSort(a,0,N); for(int i=0;i<N;i++){ printf("%d ",a[i]); } return 0; }

-------------------------------------------------分隔线-------------------------------------------------

2-路插入排序是在折半插入排序的基础上改进，其目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。

描述过程：另外再开一个数组，

最坏：关键字最小或者最大记录时，失去优越性

时间复杂度：O(n2)移动记录次数约为n平方/2

具体就不写了。