归并排序和快速排序算法的实现（C语言）

Merge Sort是建立在归并操作上的一种有效的排序算法,该算法是采用递归分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并, 使用中牺牲空间换取时间的算法

典型的分而治之的思想： 

递归边界为只有一个元素默认排好序的时候

第一步：将序列分成左右两部分mid=(start+end)/2
第二步.排序左序列，排序右序列（通过递归实现）
第三步.合并两个有序的序列

#include
#include
void merge(int *arr, int start, int mid, int end);
void mergeSort(int *arr, int start, int end) {
	if (start >= end)//分解到只有一项的时候递归结束 
		return;
	int mid = ( start + end ) / 2;
	mergeSort(arr, start, mid);//对左半部分递归排序合并 
	mergeSort(arr, mid + 1, end);//对右半部分递归排序合并 
	merge(arr, start, mid, end);
}

void merge(int *arr, int start, int mid, int end) {
	int result[1001];//建立第三个数组用于合并
	int k = 0;
	int i = start;
	int j = mid + 1;
	while (i <= mid && j <= end) {
		if (arr[i] < arr[j]){ 
			result[k++] = arr[i++];
        }
		else{
			result[k++] = arr[j++];
        }
	}
	if (i == mid + 1) {//左半部分的数组已经到了边界 
		while(j <= end) result[k++] = arr[j++];//result的后半部分全部赋值为arr的右半部分剩余 
	}
	if (j == end + 1) {//右半部分的数组已经到了边界
		while (i <= mid) result[k++] = arr[i++];//result的后半部分全部赋值为arr的左半部分剩余 
	}
	for (j = 0, i = start ; j < k; i++, j++) {
		arr[i] = result[j];
	}
}

void Init(int *arr,int n){
	for(int i=0;i 
时间复杂度：O（nlogn）
 
二、快速排序 
快速排序也是典型的分治策略：
 
第一轮排序过程：
 
1、先用key把第一个元素储存起来；
 
2、j从右往左读取，找小于key的值；
 
3、i从左往右读取，找大于key的值；
 
void QuickSort(int *arr,int low,int high){
		if(low=key) j--;//从右往左读取
			while(i 
快排在最好的时候时间复杂度O(nlogn)最坏的时候O(n^2)
 
平均复杂性是O(nlogn);