[数据结构与算法]数据结构——折半插入排序

折半插入排序，是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。

算法改进原理

回忆一下直接插入排序最理想的情况：
序列的顺序和目标顺序一致
此时只需要将全部元素遍历一遍即可，时间复杂度为O(n)。也就意味着，使用直接插入排序时，待排序序列顺序越靠近目标顺序时效率越高。
折半插入排序原理便是每次都划分成子序列先进行预排序，到后面整个序列整体进行排序时，序列已接近有序，就能够降低时间复杂度了。

排序过程

将目标序列一分为二，再讲子序列再次一分为二，直到子序列不可以再被划分为止。然后，将子序列排序，合成，再将得到的新子序列再排序再合成，直至到最后回归到整个目标序列进行排序。在进行兄弟序列进行排序合成的过程中，操作和有序顺序表合并一模一样。

核心排序代码（递归版）

void Merge(int a[],int t[],int start,int mid,int end){
	int i = start, j = mid + 1, k = start;
	while(i<=mid&&j<=end){//i是前半段坐标，j是后半段坐标 
		if(a[i]<=a[j]){// 前半段和后半段元素按大小依次入t序列 
			t[k++] = a[i++];//小数先入序列 
		}else{
			t[k++] = a[j++];
		}
	}
	while(i<=mid){//前半段如有剩余 
		t[k++] = a[i++]; 
	}
	while(j<=end){//前半段如有剩余 
		t[k++] = a[j++];
	}
} 

void halfSort(int a[],int start,int end){
	if(start>=end){//序列分治至只有1个元素 
		return ;
	}
	int mid = (start+end)/2;
	int t[len];
	halfSort(a,start,mid);//当前序列的前半段 
	halfSort(a,mid+1,end);//当前序列的后半段 
	Merge(a,t,start,mid,end);
	for(int i=start;i<=end;i++){
		a[i] = t[i];//将本次排列好的子串放回a序列 
	}
} 

示例1

初始化数组:
8 4 9 1 2 4 2
本轮划区间:
8 4 9 1 2 4 2
本轮划区间:
8 4 9 1
本轮划区间:
8 4（1）
本区间排序后:
4 8
本轮划区间:
9 1（2）
本区间排序后:
1 9
本区间排序后:（将前面（1）（2）子序列进行排序合并）
1 4 8 9（4）
本轮划区间:
2 4 2
本轮划区间:
2 4（3）
本区间排序后:
2 4
本区间排序后:（将前面（3）子序列和子序列[2]进行排序合并，因为元素[2]只有一个，便直接开始回溯和兄弟序列排序合并了）
2 2 4（5）
本区间排序后:（将前面（4）（5）子序列进行排序合并）
1 2 2 4 4 8 9
排序完成:
1 2 2 4 4 8 9

示例2

初始化数组:
0 3 6 1 2 0 8 5
本轮划区间:
0 3 6 1 2 0 8 5
本轮划区间:
0 3 6 1
本轮划区间:
0 3（1）
本区间排序后:
0 3
本轮划区间:
6 1（2）
本区间排序后:
1 6
本区间排序后:
0 1 3 6（3）（将（1）（2）排序合并）
本轮划区间:
2 0 8 5
本轮划区间:
2 0（4）
本区间排序后:
0 2
本轮划区间:
8 5（5）
本区间排序后:
5 8
本区间排序后:
0 2 5 8（6）（将（4）（5）排序合并）
本区间排序后:
0 0 1 2 3 5 6 8（将（3）（6）排序合并）
排序完成:
0 0 1 2 3 5 6 8

源代码

#include<iostream>
#include<stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
int len=8;//数组长度
#define max 10;

void Swap(int *a,int *b){
	int t  = *a;
	*a = *b;
	*b = t;
} 

void initial(int a[]){
	srand((unsigned)time(NULL));
	for(int i=0;i<len;i++){//随机生成10个数
		a[i] = rand()%max;
	}
	
}

void showArray(int a[],int start,int end){
	for(int i=start;i<=end;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
}

void Merge(int a[],int t[],int start,int mid,int end){
	int i = start, j = mid + 1, k = start;
	while(i<=mid&&j<=end){//i是前半段坐标，j是后半段坐标 
		if(a[i]<=a[j]){// 前半段和后半段元素按大小依次入t序列 
			t[k++] = a[i++];//小数先入序列 
		}else{
			t[k++] = a[j++];
		}
	}
	while(i<=mid){//前半段如有剩余 
		t[k++] = a[i++]; 
	}
	while(j<=end){//前半段如有剩余 
		t[k++] = a[j++];
	}
	cout<<"本区间排序后:\n";
	showArray(t,start,end);
} 

void halfSort(int a[],int start,int end){
	if(start>=end){//序列分治至只有1个元素 
		return ;
	}
	int mid = (start+end)/2;
	int t[len];
	cout<<"本轮划区间:\n";
	showArray(a,start,end);
	halfSort(a,start,mid);//当前序列的前半段 
	halfSort(a,mid+1,end);//当前序列的后半段 
	Merge(a,t,start,mid,end);
	for(int i=start;i<=end;i++){
		a[i] = t[i];//将本次排列好的子串放回a序列 
	}
} 

int main(){
	int a[len];
	initial(a);
//	int a[] = {8,4,9,1,2,4,2} ;
	cout<<"初始化数组:\n";
	showArray(a,0,len-1);
	halfSort(a,0,len-1); 
	cout<<"排序完成:\n";
	showArray(a,0,len-1);
	return 0;
} 

敬请批评指正！