归并，快速排序

归并排序
实现思想：
归并的含义很明显就是将两个或者两个以上的有序表组合成一个新的有序表。
归并排序中一般所用到的是2-路归并排序，即将含有n个元素的序列看成是n个有序的子序列，
每个子序列的长度为1，而后两两合并，得到n/2个长度为2或1的有序子序列，再进行两两合并。。。
直到最后由两个有序的子序列合并成为一个长度为n的有序序列。
2-路归并的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。
2-路归并的代码：

/*
蒋有绪的arr[start...mid]和有序的arr[mid+1...end]
合并为有序的arr[start...end]
*/
void merge(int *arr,int start,int mid,int end)
{
	int i=start;
	int j=mid+1;
	int k=0;
	//brr为辅助数组
	int *brr=(int *)malloc((end-start+1)*sizeof(int));
	//比较两个有序序列中的元素，将较小的元素插入到brr
	
	while(i<=mid&&j<=end)
	{
		if(arr[i]<=arr[j])
			brr[k++]=arr[i++];
		else
			brr[k++]=arr[j++];
	}
	
	//将arr 序列中剩余的元素复制到brr 
	while(i<=mid)
		brr[k+]=arr[i++];
	while(j<=end)
		brr[k++]=arr[j++];
		
	//将brr 复制到arr,使arr[start..end]有序
	
	for(i=0;i<k;i++)
		arr[i+start]=brr[i];
		
	//释放brr所占空间
		free(brr);
		brr=0;
		
}

/* 
对arr[start...end]内的元素进行归并排序 
归并排序后的顺序为从小到大 
*/  

void sort(int *arr,int start,int end)
{
	if(start<end)
	{
		int mid=(start+end)/2;
		sort(arr,start,mid);
		sort(arr,mid+1,end);
		merge(arr,start,mid,end);
	}
}

void merge_sort(int *arr,int len)
{
	sort(arr,0,len-1);
}

为了避免递归使用malloc和free，用这种经典的实现方式

void merge(int *arr,int *brr,int start,int mid,int end)
{
	int i=start;
	int j=mid+1;
	int k=0;
	
	//比较两个有序序列中的元素，将较小的元素插入到brr中
	while(i<=mid&&j<=end)
	{
		if(arr[i]<=arr[j])
			brr[k++]=arr[i++];
		else	
			brr[k++]=arr[j++];
	}
	
	while(i<=mid)
		brr[k++]=arr[i++];
	while(j<=end)
		brr[k++]=arr[j++];
	
	for(i=0;i<k;i++)
		arr[i+start]=brr[i];
		
}

void sort(int *arr,int *brr,int start,int end)
{
	if(start<end)
	{
		int mid=(start+end)/2;
		sort(arr,brr,start,mid);
		sort(arr,brr,mid+1,end);
		merge(arr,brr,start,mid,end);
	}

}

void merge_sort(int *arr,int len)
{
	int *brr=(int *)malloc(len*sizeof(int));
	sort(arr,brr,0,len-1);
	
	free(brr);
	brr=0;
}

归并排序的最好最坏和平均时间复杂度都是O（n*logn），但是需要额外的长度为n的辅助数组

快速排序：
实现思想

快速排序的基本思想如下：

1、从待排序列中任选一个元素作为枢轴；

2、将序列中比枢轴大的元素全部放在枢轴的右边，比枢轴小的元素全部放在其左边；

3、以枢轴为分界线，对其两边的两个子序列重复执行步骤1和2中的操作，直到最后每个子序列中只有一个元素。

void quick_sort(int *arr,int low,int high)
{
	int pos;
	if(low<high)
	{
		pos=findPos(arr,low,high);
		quick_sort(arr,low,pos-1);
		quick_sort(arr,pos+1,high);
	}
}
/* 
该函数返回分割点数值所在的位置,a为待排序数组的首地址， 
low刚开始表示排序范围内的第一个元素的位置，逐渐向右移动， 
high刚开始表示排序范围内的最后一个位置，逐渐向左移动 
*/  
int findPos(int *arr,int low,int high)
{
	int val=arr[low];
	while(low<high)
	{
		while(low<high&&arr[high]>=val)
			high--;
		arr[low]=arr[high];
		
		while(low<high&&arr[low]<=val)
			low++;
		arr[high]=arr[low];
		 
		 
		//最终low=high  
		arr[low]=val;
		return low;
	}

}

通常，快速排序被认为在所有同数量级（平均时间复杂度均为O(n*logn)）的排序方法中，平均性能最好
所以通常枢轴元素的选择一般基于“三者取中”的原则，即比较首元素、末元素、中间元素的值，取三者中中间大小的那个。