归并排序和快速排序。这两种排序算法适合大规模的数据排序，比上一节讲的那三种排序算法要更常用。归并排序和快速排序都用到了分治思想，非常巧妙。我们可以借鉴这个思想，来解决非排序的问题，比如：如何在 O(n) 的时间复杂度内查找一个无序数组中的第 K 大元素？ 这就要用到我们今天要讲的内容。

一、归并排序（Merge Sort）

概念

归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。
从我刚才的描述，你有没有感觉到，分治思想跟我们前面讲的递归思想很像。是的，分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧，这两者并不冲突。
写递归代码的技巧就是，分析得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。所以，要想写出归并排序的代码，我们先写出归并排序的递推公式。

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

**伪代码**

// 归并排序算法, A是数组，n表示数组大小
merge_sort(A, n) {
  merge_sort_c(A, 0, n-1)
}

// 递归调用函数
merge_sort_c(A, p, r) {
  // 递归终止条件
  if p >= r  then return
  // 取p到r之间的中间位置q
  q = (p+r) / 2
  // 分治递归
  merge_sort_c(A, p, q)
  merge_sort_c(A, q+1, r)
  // 将A[p...q]和A[q+1...r]合并为A[p...r]
  merge(A[p...r], A[p...q], A[q+1...r])
}

**自己写的归并排序：（有误）**

public class Test {
    public static void main(String[] args) {
        int[] arr = new int[]{5,8,6,2,7,3,10,4,1,9};
        meger_sort(arr, 0, arr.length-1);
//        sort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void meger_sort(int[] target, int left, int right) {
        int mid = (left + right) / 2;
        if(left >= right) {
            return; // 结束条件
        }
        meger_sort(target, left, mid);         // 左部分递归分治
        meger_sort(target, mid+1, right);  // 右部分递归分治
        sort(target, left, right);             // 求和
    }

    // 插入排序
    public static void sort(int[] target, int left, int right) {
        for (int i = left+1; i <= right; i++) {
            int value = target[i];
            int j = i;
            while(j > 0) {
                if(target[j-1] > value) {
                    target[j] = target[j-1];
                } else {
                    break;
                }
                j--;
            }
            target[j] = value;
        }
        System.out.println(left + "=" + right + " " + Arrays.toString(target));
    }
}

代码结果：

0=1 [5, 8, 6, 2, 7, 3, 10, 4, 1, 9]
0=2 [5, 6, 8, 2, 7, 3, 10, 4, 1, 9]
3=4 [5, 6, 8, 2, 7, 3, 10, 4, 1, 9]
0=4 [2, 5, 6, 7, 8, 3, 10, 4, 1, 9]
5=6 [2, 5, 6, 7, 8, 3, 10, 4, 1, 9]
5=7 [2, 5, 6, 7, 8, 3, 4, 10, 1, 9]
8=9 [2, 5, 6, 7, 8, 3, 4, 10, 1, 9]
5=9 [1, 2, 5, 6, 7, 8, 3, 4, 9, 10]
0=9 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

代码问题：既然是使用归并排序，那么你使用插入排序已经可以解决问题了，那么还要在写个归并排序干嘛？它归并排序本来是通过开辟额外的数组空间来保存每次分治的结果，那使用插入排序是不是错了呢？？？
老师的思路：

merge()函数的代码：

merge(A[p...r], A[p...q], A[q+1...r]) {
  var i := p，j := q+1，k := 0 // 初始化变量i, j, k
  var tmp := new array[0...r-p] // 申请一个大小跟A[p...r]一样的临时数组
  while i<=q AND j<=r do {
    if A[i] <= A[j] {
      tmp[k++] = A[i++] // i++等于i:=i+1
    } else {
      tmp[k++] = A[j++]
    }
  }

  // 判断哪个子数组中有剩余的数据
  var start := i，end := q
  if j<=r then start := j, end:=r

  // 将剩余的数据拷贝到临时数组tmp
  while start <= end do {
    tmp[k++] = A[start++]
  }

  // 将tmp中的数组拷贝回A[p...r]
  for i:=0 to r-p do {
    A[p+i] = tmp[i]
  }
}

你还记得第 7 讲讲过的利用哨兵简化编程的处理技巧吗？merge() 合并函数如果借助哨兵，代码就会简洁很多，这个问题留给你思考。
哨兵方法:
1. 先将要合并的两个放到tmpLeft和tmpRight数组,其中每个数组都多出一个位置放哨兵
2. tmpLeft[leftSize] = int.MaxValue; tmpRight[rightSize] = int.MaxValue;
3.比较两个tmp数组,哪个小就放到原数组,使用哨兵不用再判断是否有剩下的有序数组

for (k=left,i=0,j=0; k<=right; k++){ 
    if(tmpLeft[i] < tmpRight[j]){ 
        arr[k] = tmpLeft[i]; i++; 
    }else{
        arr[k] = tmpRight[j]; j++; 
    } 
}

最终实现代码：

    public static void main(String[] args) {
        int[] arr = new int[]{5,8,6,2,7,3,10,4,1,9};
        meger_sort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void meger_sort(int[] target, int left, int right) {
        int mid = (left + right) / 2;
        if(left >= right) {
            return; // 结束条件
        }
        meger_sort(target, left, mid);         // 左部分递归分治
        meger_sort(target, mid+1, right);  // 右部分递归分治
        tempSort(target, left, mid, right);
    }

    public static void tempSort(int[] target, int left, int mid, int right) {
        int[] temp = new int[right - left+1];
        int index = 0;
        int lef = left;
        int riL = mid+1;
        for (;lef <= mid && riL <= right; ) { // 将两个数组其中一个清空
            if(target[lef] <= target[riL]) {
                temp[index++] = target[lef++];
            } else {
                temp[index++] = target[riL++];
            }
        }

        while(riL <= right) {
            temp[index++] = target[riL++];
        }

        while(lef <= mid) {
            temp[index++] = target[lef++];
        }

        // 合并
        for (int i = 0; left <= right; ) {
            target[left++] = temp[i++];
        }

结果：

[5, 8, 6, 2, 7, 3, 10, 4, 1, 9]
[5, 6, 8, 2, 7, 3, 10, 4, 1, 9]
[5, 6, 8, 2, 7, 3, 10, 4, 1, 9]
[2, 5, 6, 7, 8, 3, 10, 4, 1, 9]
[2, 5, 6, 7, 8, 3, 10, 4, 1, 9]
[2, 5, 6, 7, 8, 3, 4, 10, 1, 9]
[2, 5, 6, 7, 8, 3, 4, 10, 1, 9]
[2, 5, 6, 7, 8, 1, 3, 4, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

归并排序的性能分析

第一，归并排序是稳定的排序算法吗？

归并排序稳不稳定关键要看 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*T(n/2) + n
     = 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^kT(n/2^k)+kn。当 T(n/2^k)=T(1) 时，也就是 n/2^k=1，我们得到 k=log2n 。我们将 k 值代入上面的公式，得到 T(n)=Cn+nlog2n 。如果我们用大 O 标记法来表示的话，T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。
从我们的原理分析和伪代码可以看出，归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。

第三，归并排序的空间复杂度是多少？

实际上，递归代码的空间复杂度并不能像时间复杂度那样累加。刚刚我们忘记了最重要的一点，那就是，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

二、快速排序（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，就说明所有的数据都有序了。
如果我们用递推公式来将上面的过程写出来的话，就是这样：

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

终止条件：
p >= r

伪代码：

// 快速排序，A是数组，n表示数组的大小
quick_sort(A, n) {
  quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数，p,r为下标
quick_sort_c(A, p, r) {
  if p >= r then return

  q = partition(A, p, r) // 获取分区点
  quick_sort_c(A, p, q-1)
  quick_sort_c(A, q+1, 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

这里的处理有点类似选择排序。我们通过游标 i 把 A[p…r-1]分成两部分。A[p…i-1]的元素都是小于 pivot 的，我们暂且叫它“已处理区间”，A[i…r-1]是“未处理区间”。我们每次都从未处理的区间 A[i…r-1]中取一个元素 A[j]，与 pivot 对比，如果小于 pivot，则将其加入到已处理区间的尾部，也就是 A[i]的位置。
数组的插入操作还记得吗？在数组某个位置插入元素，需要搬移数据，非常耗时。当时我们也讲了一种处理技巧，就是交换，在 O(1) 的时间复杂度内完成插入操作。这里我们也借助这个思想，只需要将 A[i]与 A[j]交换，就可以在 O(1) 时间复杂度内将 A[j]放到下标为 i 的位置。

因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列 6，8，7，6，3，5，9，4，在经过第一次分区操作之后，两个 6 的相对先后顺序就会改变。所以，快速排序并不是一个稳定的排序算法。
代码：

public class Test {
    public static void main(String[] args) {
        int[] arr = new int[]{5,8,6,2,7,3,10,4,1,9};
//        meger_sort(arr, 0, arr.length-1);
//        sort(arr, 0, arr.length-1);
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));

    }

    // 快速排序
    public static void quickSort(int[] target, int l, int r) {
        if(l >= r) return;
        int p = getPartition(target, l, r);
        quickSort(target, l, p-1);  // 这里有种情况，分区值不用处理
        quickSort(target, p+1, r);
    }

    // 自己思路，这样子写的
    public static int getPartition(int[] target, int l, int r) {
        System.out.println(l + " " + r);
        // 将每次的第一个作为分区点
        int index = l; // r 或者 l 都可以
        while(l < r) {
            while(target[l] < target[index]) {
                l++;
            }
            // 交换
            int temp = target[l];
            target[l] = target[index];
            target[index] = temp;
            index = l;

            while(target[r] > target[index]) {
                 r--;
            }
            // 交换
            temp = target[r];
            target[r] = target[index];
            target[index] = temp;
            index = r;
        }

        return index;
    }

    // 菜鸟教程找分区值
     private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

菜鸟教程快速排序图：

快速排序的性能分析

快排的时间复杂度也是 O(nlogn)。

如果数组中的数据原来已经是有序的了，比如 1，3，5，6，8。如果我们每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的。我们需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约 n/2 个元素，这种情况下，快排的时间复杂度就从 O(nlogn) 退化成了 O(n2)。
一个是分区极其均衡，一个是分区极其不均衡。

三、区别

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

四、解答开篇

快排核心思想就是分治和分区，我们可以利用分区的思想，来解答开篇的问题：O(n) 时间复杂度内求无序数组中的第 K 大元素。比如，4， 2， 5， 12， 3 这样一组数据，第 3 大元素就是 4。
我们选择数组区间 A[0…n-1]的最后一个元素 A[n-1]作为 pivot，对数组 A[0…n-1]原地分区，这样数组就分成了三部分，A[0…p-1]、A[p]、A[p+1…n-1]。
如果 p+1=K，那 A[p]就是要求解的元素；如果 K>p+1, 说明第 K 大元素出现在 A[p+1…n-1]区间，我们再按照上面的思路递归地在 A[p+1…n-1]这个区间内查找。同理，如果 K