归并排序、快速排序

归并排序和快速排序的时间复杂度为O(nlogn)。利用分治思想将大问题分解成小问题解决；利用递归代码实现归并排序。

归并排序¹

先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起。

递推公式:
merge_sort(p…r) = merge(merge_sort(p…q),merge_sort(q+1…r))
终止条件：
p = r 不用再继续分解

merge_sort(p…r)表示给下标从p到r之间的数组排序。将此问题转化为了两个子问题：merge(merge_sort(p…q),merge_sort(q+1…r))，其中下标q等于p和r的中间位置(p+r)/2。当下标从p到q和从q+1到r这两个子数组都排好序之后，再将两个有序的子数组合并在一起，那么下标从p到r之间的数据也就排好序了。
合并函数merge([p…r],[p…q],[q+1…r])，申请一个临时数组temp,大小与数组[p…r]相同。用两个游标i和j，分别指向[p…q]和[q+1…r]的第一个元素。比较这两个元素[i]、[j]的大小，将较小的元素放入到临时数组temp中，并将相应的游标后移一位。

归并排序是一个稳定的排序算法，合并数组时，遇到值相同的元素，现将[p…q]区间的元素放入到临时数组temp中，保证值相同的元素在合并前后的先后顺序不变。

最好、最坏、平均情况时间复杂度都是O(nlogn)。

T(1) = C；   n=1时，只需要常量级的执行时间，所以表示为C。
T(n) = 2*T(n/2) + n； n>1
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

当T(n/2^k)=T(1)时，k=log₂n，T(n)=Cn+nlog₂n

归并排序不是原地排序算法。
归并排序在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过n个数据的大小，空间复杂度是O(n)。

快速排序²

如果要排序数组中下标从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，就说明所有的数据都有序了。

递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1…r)
终止条件：
p = r

快速排序中的分区函数partition()，随机选择一个元素作为分区点pivot，一般情况下可以选择p到r区间的最后一个元素，对数组进行分区，函数返回分区点pivot的下标。

空间复杂度
- 不考虑空间消耗可以申请两个临时数组X和Y，遍历数组，将小于分区点的元素拷贝到临时数组X，大于分区点的元素拷贝到临时数组Y，最后将数组X、Y中的数据顺序拷贝到原数组中。
- 原地分区操作，类似选择排序
  通过游标i将数组[p…r-1]分成两部分，已处理区间[p…i-1]和未处理区间[i…r-1]，每次从未处理区间中取出一个元素[j]和分区点对比，如果小于，则将其加入到已处理区间的尾部[i]的位置。优化：不搬移数据，交换操作，将a[i]与a[j]交换。
涉及交换操作，属于不稳定的排序算法。
时间复杂度
分区极其均衡，每次分区操作都能正好把数组分成大小接近相等的两个小区间，最好时间复杂度为O(nlogn)。
分区极其不均衡，数组正序，需要n次分区操作，每次分区平均要扫描n、2个元素，最坏时间复杂度为O(n²)。
大部分情况下的时间复杂度都可以做到O(nlogn)，只有在极端情况下，才会退化到O(n²)。平均时间复杂度O(nlogn)。

对比

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。
快速排序的处理过程是由上到下的，先分区，然后再处理子问题。

参考&扩展

[1] 归并排序

//归并排序
public void mergeSort(int[] a) {
    mergeSortInter(a,0,a.length-1);
}
public void mergeSortInter(int[] a,int start,int end) {
    //终止条件
    if(start==end) return;

    //中间结点
    int mid = (start+end)/2;

    mergeSortInter(a,start,mid);
    mergeSortInter(a,mid+1,end);

    //合并函数
    merge(a,start,mid,end);
}
public void merge(int[] a,int left,int mid,int right) {
    //临时数组，大小为当前分区的大小
    int[] temp = new int[right - left + 1];

    int m = 0, i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        //取左右区间中元素最小值放入当前位置
        temp[m++] = a[i] <= a[j] ? a[i++] : a[j++];
    }
    //拷贝剩余数据到临时数组
    while (i <= mid)
        temp[m++] = a[i++];
    while (j <= right)
        temp[m++] = a[j++];

    //拷贝临时数据到原数组对应区间
    for (int k=0;k <= right-left;k++)
        a[left+k] = temp[k];
}

[2] 快速排序

//快速排序
public void quickSort(int[] a) {
    quickSortInter(a,0,a.length-1);
}

public void quickSortInter(int[] a,int start,int end) {
    //终止条件  start 可能大于end
    if(start>=end) return;

    //分区函数获取分区点
    int p = partition(a,start,end);

    quickSortInter(a,start,p-1);
    quickSortInter(a,p+1,end);
}

public int partition(int[] a,int start,int end) {
    //取当前分区最后一个元素做分区点
    int pivot = a[end];
    //记录下一个小于分区点元素值的元素应放置的下标
    int i = start;
    for(int j = start; j < end; j++) {
        //当前元素与分区点元素值比较，小于则当前元素与上一个小于分区点元素的后一个元素进行交换
        if(a[j] < pivot) {
            if(i != j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
            i++;
        }
    }

    //分区点元素值与最后一个小于分区点元素的后一个元素进行交换
    int temp = a[i];
    a[i] =a[end];
    a[end] = temp;

    return i;
}

归并排序1

快速排序2

对比

参考&扩展

归并排序¹

快速排序²