[toc]
归并排序和快速排序都用到了分治思想，非常巧妙。这两种排序算法适合大规模的数据排序。
归并排序（Merge Sort）
如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧，这两者并不冲突。
public static int[] sort(int[] a,int low,int high){
int mid = (low+high)/2;
if(low<high){
sort(a,low,mid);
sort(a,mid+1,high);
//左右归并
merge(a,low,mid,high);
}
return a;
}
public static void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high-low+1];
int i= low;
int j = mid+1;
int k=0;
// 把较小的数先移到新数组中
while(i<=mid && j<=high){
if(a[i]<a[j]){
temp[k++] = a[i++];
}else{
temp[k++] = a[j++];
}
}
// 把左边剩余的数移入数组
while(i<=mid){
temp[k++] = a[i++];
}
// 把右边边剩余的数移入数组
while(j<=high){
temp[k++] = a[j++];
}
// 把新数组中的数覆盖nums数组
for(int x=0;x<temp.length;x++){
a[x+low] = temp[x];
}
}
第一，归并排序是稳定的排序算法吗？
归并排序稳不稳定关键要看 merge() 函数，也就是两个有序子数组合并成一个有序数组的那部分代码。在合并的过程中，如果 A[p…q] 和 A[q+1…r] 之间有值相同的元素，那我们可以像伪代码中那样，先把 A[p…q] 中的元素放入 tmp 数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。
第二，归并排序的时间复杂度是多少？
递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。
假设对 n 个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)。我们知道，merge() 函数合并两个有序子数组的时间复杂度是 O(n)。所以，套用前面的公式，归并排序的时间复杂度的计算公式就是：
- T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。
- T(n) = 2*T(n/2) + n； n>1
得到 T(n) = 2^k^T(n/2^k^)+k\n。当 T(n/2^k^)=T(1) 时，也就是 n/2^k^=1，我们得到 k=log~2~n 。我们将 k 值代入上面的公式，得到 T(n)=C*n+n*log~2~n 。如果我们用大 O 标记法来表示的话，T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。
==归并排序的执行效率与要排序的原始数组的有序程度无关==，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。
第三，归并排序的空间复杂度是多少？
==归并排序不是原地排序算法==。这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。空间复杂度是 O(n)
快速排序（Quicksort）
快速排序（Quicksort）是对冒泡排序的一种改进。
如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
根据分治、递归的处理思想，可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。
如果希望快排是原地排序算法，那它的空间复杂度得是 O(1)，那 partition() 分区函数就不能占用太多额外的内存空间，就需要在 A[p…r] 的原地完成分区操作。
partition(A, p, r) {
pivot := A[r]
i := p
for j := p to r-1 do {
if A[j] < pivot {
swap A[i] with A[j]
i := i+1
}
}
swap A[i] with A[r]
return i
因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列 6，8，7，6，3，5，9，4，在经过第一次分区操作之后，两个 6 的相对先后顺序就会改变。所以，快速排序并不是一个稳定的排序算法。
import java.util.Arrays;
public class QuickSort {
//三数取中法。取出不大不小的那个位置
public static int getPivotPos(int[] a,int low,int high) {
int mid=(low+high)/2;
int pos=low;
if(a[mid]<a[low]) {
int temp=a[low];
a[low]=a[mid];
a[mid]=temp;
}
if(a[high]<a[low]) {
int temp=a[high];
a[high]=a[low];
a[low]=temp;
}
if(a[high]<a[mid]) {
int temp=a[high];
a[high]=a[mid];
a[mid]=temp;
}
pos=mid;
return pos;
}
//划分，取出枢纽位置
public static int partition(int[] a,int low,int high) {
int pivotpos=getPivotPos(a,low,high);
int pivot=a[pivotpos];
int temp=pivot;
a[pivotpos]=a[low];
a[low]=temp;
while(low<high) {
while(low<high&&a[high]>=pivot) high--;
a[low]=a[high];
while(low<high&&a[low]<=pivot) low++;
a[high]=a[low];
}
a[low]=pivot;
return low;
}
//快排
public static void quickSort(int[] a,int low,int high) {
if(low<high) {
int pivotpos=partition(a,low,high);
quickSort(a,low,pivotpos-1);
quickSort(a,pivotpos+1,high);
}
}
//重载快排
public static void quickSort(int[] a) {
if(a.length==0)
return;
int low=0;
int high=a.length-1;
quickSort(a,low,high);
}
public static void main(String[] args) {
int[] a= {12,32,24,99,54,76,48};
quickSort(a);
System.out.println(Arrays.toString(a));
}
}
快排是一种原地、不稳定的排序算法。快排的时间复杂度也是 O(nlogn)。举一个比较极端的例子。如果数组中的数据原来已经是有序的了，比如 1，3，5，6，8。如果每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的。需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区平均要扫描大约 n/2 个元素，这种情况下，快排的时间复杂度就从 O(nlogn) 退化成了 O(n2)。在大部分情况下的时间复杂度都可以做到 O(nlogn)，只有在极端情况下，才会退化到 O(n2)。
区别
归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。