本文共 1632 字，大约阅读时间需要 5 分钟。

1.归并排序

归并排序将整体数组不断分成更小的数组，最终结果是所有数组中只含有一个元素，然后两两不断合并。时间复杂度为O(nlogn) 比如现在有数组{1,15,16,24,3,8,7,23} 第一次划分，{1,15,16,24},{3,8,7,23} 第二次划分，{1,15},{16,24},{3,8},{7,23} 第三次划分，{1}，{15}，{16}，{24}，{3}，{8}，{7}，{23} 开始两两合并排序 第一次合并, {1,15},{16,24},{3,8},{7,23} 第二次合并,{1,15,16,24},{3,7,8,23} 第三次合并,{1,3,7,8,15,16,23,24} 归并排序中有着递归的思想，不断将数组划分成更小的数组，在这种递归的思想中不妨想一下划分的最终状态——数组中只含有一个元素，然后反过来向上推演。 归并排序关键函数如下：

void Combine(int left,int middle,int right){   	int i=left;	int j=middle;	int k=left;	while(i<=middle&&j<=right){   		//将分成的左右两部分合并比较大小 		if(arr[i]<=arr[j]){   			temp[k++]=arr[i++];		//将arr[i]与arr[j]中较小者存入到temp数组中 		}		else{   			temp[k++]=arr[j++];		}	}	while(i<=middle){   				//左边部分没有比较完，右边部分比较结束 		temp[k++]=arr[i++];			//将左边部分直接全部存入temp数组中 	}	while(j<=right){   				//右边部分没有比较完，坐边部分比较结束		temp[k++]=arr[j++];			//将左右部分直接全部存入temp数组中 	}	for(k=left;k<=right;k++){   		//将temp数组中数据存入原数组 		arr[k]=temp[k];	}	return;}void MergeSort(int left,int right){   	if(left

2.快速排序

快速排序首先需要选取一个pivot，每一次快速排序可以确定一个数的最终位置 比如现在有数组{15,16,24,1,3,8,7,23} 第一次快速排序：{7,8,3,1,15,24,16,23} 第二次快速排序：{1,3,7,8,15,23,16,24} 第三次快速排序：{1,3,7,8,15,16,23,24} 快速排序同样也是将一个大问题分解为更小的问题，时间复杂度为O(nlogn)

void QuickSort(int arr[],int left,int right){   	if(left
   
    =pivot) j--;	//从右边开始不断将右指针左移，寻找到第一个小于pivot的数 			if(i
   

快速排序练习题：寻找数组中第k小的数

寻找数组中第k小的数不用将整个数组进行排序，在快速排序算法的基础上，在每一次快排结束后进行一次判断即可

int QuickSort(int arr[],int left,int right,int k){   	if(left
   
    =pivot) j--;	//从右边开始不断将右指针左移，寻找到第一个小于pivot的数 			if(i
    
     k){   			QuickSort(arr,left,i,k);		//如果当前i的位置大于k，将i左半部分快速排序 		}		else{   			QuickSort(arr,i+1,right,k);		//如果当前i的位置小于k，将i右半部分快速排序 		}						}	return arr[k];}