快速排序、归并排序
1.快速排序
快速排序每趟选择一个基准元素，用基准元素将序列划分成两部分，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面，这一趟过程称为分区（partition）操作。每一趟分区操作的目的就是把这趟的基准元素摆到最终位置。 递归地对基准元素左边的序列和右边的序列分别调用分区操作，则当序列的大小是零或者一时整个序列排序完成，采用的是“分治”的策略。
快速排序-图片来自维基百科
思路总结：
（1）先从序列中取出一个数作为基准数。
（2）分区过程：将比基准数大的数全部放到它的右边，小于或等于它的数全部放到它的左边。
（3）对左右序列重复步骤（2），直到各序列数只有一个或零个
为了便于大家理解“分区”操作，将快排写成两个函数，大家也可以合成一个函数写，参考代码如下：
//分区操作
public int partition(int a[],int left,int right){
int l = left,r = right,key = a[left];
if(left<right){
while(l<r){//结束条件为左指针与右指针汇合
while(l<r&&key<=a[r]){//从右向左遍历数组，找到第一个小于key的值
r--;
}
if(l<r){//右边小于key的值与key的位置互换
a[l++] = a[r];
}
//左右方向互换
while(l<r&&key>a[l]){//从左向右遍历，找到第一个大于key的值
l++;
}
if(l<r){//左边大于key的值与key互换
a[r--] = a[l];
}
}
a[l] = key;//key放到数组最终位置
}
return l;
}
上面的分区操作的代码可以简单概括为“挖坑填数”，即每次partiton将序列最左边的数选为基准元素key，将key挖出，从右向左开始遍历，让序列中的数与基准元素key值进行比较，若右边有比基准值小的数，则将该数“挖”出来，“填”入坑中，被挖的数成为新的坑，每“挖、填”一次数，改变一次序列的遍历方向，直到序列遍历完成为止，将key（基准元素）填入最终结束的位置，也就确定了基准元素最终在序列中的位置。
//递归调用
public void quickSort(int a[],int left,int right){
if(left<right){
int t = partition(a, left, right);
quickSort(a, left, t-1);//左边的数组快排
quickSort(a, t+1, right);//右边的数组快排
}
}
排序过程如下所示：
初始状态： a[0] a[1] a[2] a[3] a[4] a[5]
初始值： ５ ６ ４ ３ １ ２
第一趟排序过程：key = 5 a[0]为初始坑所在位置（用[ ]标识坑的位置）
［５］ ６ ４ ３ １ ２ (右->左，l=0,r=5，a[r]小于key)
２ ６ ４ ３ １ ［２］ (交换，a[5]值填坑，a[5]变新坑)
２ ６ ４ ３ １ ［２］ (左->右，l=1,r=5，a[l]大于key)
２ ［６］ ４ ３ １ ６ (交换，a[1]值填坑，a[1]变新坑)
２ ［６］ ４ ３ １ ６ (右->左，l=1,r=4，a[r]小于key)
２ １ ４ ３ ［１］ ６ (交换，a[4]值填坑，a[4]变新坑)
２ １ ４ ３ ［１］ ６ (左->右，l=2,r=4)
２ １ ４ ３ ［１］ ６ (左->右，l=3,r=4)
２ １ ４ ３ ［５］ ６ (l=r=4,key填a[l])
２ １ ４ ３ ５ ６ (找到５的最终位置)
第二趟： １ ２ ４ ３ 5 6 （找到２的最终位置）
第三趟： １ ２ ３ ４ 5 6 （找到４的最终位置）
２.归并排序
归并排序先递归分解序列，一分为二进行分组，直到分解到分组只有一个元素为止，认为其有序，再将有序分组两两合并，最后使整个序列有序。（归并可以简单理解为：递归分解+两两合并）
Paste_Image.png
将两个有序序列合并的思路：
（1）比较两个序列中第一个数，取出较小者，对应取数序列取数位置后移一位，即下一个数变为第一个数。
（2）重复步骤（3），如果有序列值全部取完，那直接将另一个序列的数据依次取出即可
（3）取出的数依次存入一个新的序列，这个新的序列即为这两个有序序列合并而成的新的有序序列
分解的实现比较简单，通过改变传入数组下标，直接递归调用即可，为了便于大家理解归并排序中递归与合并的概念，将归并写成两个函数，参考代码如下：
//递归分解操作
public void mergeSort(int a[],int begin,int end){//传入的begin、end均为待排序数组的下标值
if(begin<end){
int mid = (begin+end)/2;
mergeSort(a, begin, mid);
mergeSort(a, mid+1, end);
merge(a, begin, end);
}
}
对于数组进行分解，例如若某个数组长度为8，下标为0~7，则mid = (0+7)/2=3，可将数组分成两个子数组：下标为[03]的数组和下标为[47]的数组。而对于下标[03]的数组，其mid=(0+3)/2=1，又可将其分为下标为[01]的数组和下标为[2~3]的数组。依此类推，直到分解成的数组只有一个元素为止，认为其有序。
//合并操作
public void merge(int a[],int begin,int end){
int mid = (begin + end)/2;//将传进来原数组对应下标的子数组根据mid分解
int i = begin, j = mid + 1; //分解成两个数组:[begin~mid]、[mid+1~end]
int k = 0;
int temp[] = new int[end+1];//申请额外空间来暂存排序后的新的有序数组
while (i <= mid && j <= end) //依次比较分解后两个数组内的数，直至其中一个数组到末尾
{
if (a[i] <= a[j]) //将较小值放入临时数组的前面
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= mid) //若数组[begin~mid]中还有数没取完，则将未取完的数全部追加到临时数组后面
temp[k++] = a[i++];
while (j <= end) //若数组[mid+1~end]中还有数没取完，则将未取完的数全部追加到临时数组后面
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[begin+i] = temp[i]; //将合并后有序的临时数组中的数依次赋值到原来待合并的数组，完成该次合并
}
排序过程如下所示：
初始状态：a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
初始值： ６ ５ ３ １ ８ ７ ２ ４
６ ５ ３ １ ８ ７ ２ ４（0~1合并）
５ ６ ３ １ ８ ７ ２ ４（2~3合并）
５ ６ １ ３ ８ ７ ２ ４（0~3合并）
１ ３ ５ ６ ８ ７ ２ ４（4~5合并）
１ ３ ５ ６ ７ ８ ２ ４（6~7合并）
１ ３ ５ ６ ７ ８ ２ ４（4~7合并）
１ ３ ５ ６ ２ ４ ７ ８（0~7合并）
１ ２ ３ ４ ５ ６ ７ ８（排序结果）
