[数据结构与算法]归并排序，快速排序，希尔排序主要代码对比

/*o(nlogn) time efficiency*/

//归并排序 o(nlogn) o(n) stable

//归并排序 o(nlogn) o(n) stable
void MA(int a[],int be,int mid,int en)//数组的a[0] 不保存元素 
{
	int b = be,ob = mid + 1,k = 0,c[101] = {0};//c数组为临时数组
	
	//当且当 b,ob在范围内 
	while(b <= mid && ob <= en)
	{
		if(a[b] <= a[ob])
		{
			c[k ++] = a[b ++];
		}
		else
		{
			c[k ++] = a[ob ++]
		}
	}
	//如果b已经录完 
	if(b > mid)
	{
		//再看ob是否录完 
		while(ob <= en)
		{
			c[k ++] = a[ob ++];
		}
	}
	//b没有录完（由while条件 则ob一定录完） 
	else
	{
		while(b <= mid)
		{
			c[k ++] = a[b ++];
		}
	}
	//将临时数组 赋值给 原数组 
	for(int i = b,k = 0;i <= en;i ++)
	{
		a[i] = c[k ++];
	}
	return;
}

void MS(int a[],int b,int e)//数组的a[0] 不保存元素 
{
	if(b >= e)
	{
		return;
	}
	
	int mid = (b + e) / 2;
	MS(a,b,mid);
	MS(a,mid + 1,e);
	MA(a,b,mid,e);
	return;
}

//快速排序 o(nlogn) o(logn) instable

//快速排序 o(nlogn) o(logn) instable
void Quick(int a[],int t,int w)
{
	if(t < w)
	{
		int i = t,j = w,x = a[i];
		while(j > i)//寻找值插入点（第一个值为 首位元素值） 
		{
			//先从右边 开始 
			while(j > i && a[j] > x)
			{
				j --;
			} 
			if(j > i)//如果存在a[j] < x
			{
				//swap
				a[i] = a[j];i ++;
			}
			
			//再从左边 开始 
			while(j > i && a[i] < x)
			{
				i ++;
			} 
			if(j > i)//如果存在a[i] > x
			{
				//swap
				a[j] = a[i];j --;
			}
		}
		//此时 i == j 
		x = a[j];//值放入正确插入点 
				
		//k中间点元素位置确定，处理两边 
		Quick(a,t,k - 1);
		Quick(a,k + 1,w);
	}
	
	return;
}

//希尔排序 o(nlogn) o(1) stable

//希尔排序 o(nlogn) o(1) stable
void shell(int a[],int n)//数组的a[0] 不保存元素 
{
	int d = n / 2;//初始增量 
	while(d >= 1)
	{
		for(int i = d + 1;i < n;i ++)//起始点往后
		{
			int j = i - d,x = a[i];
			while(j > 0 && a[j] > x)//以该增量 往前遍历 对比 
			{
				a[j + d] = a[j];
				j = j - d;
			}
		}
		a[j + d] = x;//找到起始点 插入位置 
		d = d / 2;//缩小增量 
	}
	return;
}