算法-排序(中)

发表于 | 更新于 | 分类于 | 阅读次数：

前言


上一节讲到冒泡排序、插入排序、选择排序这三种排序算法，他们的时间复杂度都是$O(n^2)$，比较高，适合小规模的排序。今天讲两种时间复杂度为$O(nlogN)$的排序算法，归并排序和快速排序。这两种算法适合大规模的数据排序，比上一节的三种算法更常用。

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


归并排序的原理


我们先来看看归并排序。

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

归并排序使用的就是分治思想。分治，顾名思义就是分而治之。将一个大问题分解为若干个小问题来解决，小问题解决了，大问题也就解决了。

从我们刚才的描述，你有没有感觉到，分治思想跟我们前面讲过的递归想想很想。是的，分治思想一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧，这两者并不冲突。

前面我通过举例让你对归并有了一个感性的认识，又告诉你，归并排序用的是分治思想，可以用递归来实现。我们现在就来看看如何用递归代码实现归并排序。

我们在递归那一节讲的递归代码的编程技巧你还记得吗？递归代码的技巧就是，分析得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。所以，要想写出归并排序的代码，我们先写出归并排序的递推公式。

1
2
3
4
5
递推公式
merge_sort(p...r) = merge(merge_sort(p...q), merge_sort(q+1...r))

终止条件
p>=r 不在继续分解

我来解释一下这个公式，merge_sort(p…r)表示给下标在p到r之间的数组排序，我们将这个问题转化为了两个子问题，merge_sort(p…q)和merge_sort(q+1…r)，其中下标q就是p和r的中间位置，也就是q=(p+r)/2,。当下标p到q和从q+1到r这两个子数组都排好序之后，我们在将两个有序的子数组合并在一起，这样下标p到r之间的数据也就排好序了。

有了递推公式，转化成代码就简单多了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 归并排序
public static void merge_sort(int[] a, int n){
    merge_sort(a, 0, n-1);
}
private static void merge_sort(int[] a, int p, int r){
    // 递归终止条件
    if (p>=r) return;
    // 获取分区点
    int q = p + (r-p)/2;
    // 分治排序左边
    merge_sort(a, p, q);
    // 分治排序右边
    merge_sort(a, q+1, r);
    // 将p-q 和 q+1-r 两个数组合并为一个数组并赋值给a[p,r]
    merge(a, p, q, r);
}

// 合并数组
private static void merge(int[] a, int p, int q, int r){
    int i = p;
    int j = q + 1;
    int k = 0;
    // 合并数组 a[p, q]  a[q+1, r] 到临时数组temp
    // 申请一个临时数组
    int[] temp = new int[r - p + 1];
    // 根据两个数组最短的长度进行比较添加到temp中
    while (i<=q&& j<=r){
        if (a[i]<=a[j]){
            temp[k++] = a[i++];
        }else {
            temp[k++] = a[j++];
        }
    }

    // 看哪个数组还没有完成，将其放到temp后
    if (i<=q){
        while (i<=q){
            temp[k++] = a[i++];
        }
    }else {
        while (j<=r){
            temp[k++] = a[j++];
        }
    }
    System.out.println(Arrays.toString(temp));

    // 将temp中对应的数据放入原数组中
    for (i = 0; i <= r-p; i++) {
        a[p+i] = temp[i];
    }
}

你可能已经发现了，merge(A[p…r], A[p…q], A[q+1…r])这个函数的作用就是，讲已经有序的A[p…q]和A[q+1…r]合并成另一个有序的数组，并且放入A[p…r]。那这个过程具体该怎么做呢？

如图所示，我们申请一个临时数组temp，大小与A[p…r]相同。我们用两个指针i，j分别指向A[p…q]和A[q+1…r]的第一个元素，比较这两个元素A[i]和A[j]，如果A[i]小于A[j]，我们就把A[i]放入temp数组中，并将i后移一位，否则将A[j]放入temp数组中，j后移一位。

继续上述比较过程，知道其中一个子数组中的所有数据都放入临时数组中，再把另外一个数组中的数据依次加入到temp数组的末尾。这个时候，临时数组temp中存储的就是两个子数组合并之后的结果了。最后再把临时数组temp中数据拷贝到原数组里A[p…r]中。


归并排序的性能分析


还记得上节课分析排序算法时的三个问题吗？接下来，我们来看一看归并排序的三个问题。

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

结合我们前面的原理图和归并排序的代码，不难发现，归并排序稳不稳定关键要看merge函数，也就是两个有序数组合并为一个有序数组时的那部分代码。

在合并的过程中，如果A[p…q]和A[q+1…r]之间有值相同的元素，我们可以像上面代码中那样，先把A[p…q]中的元素放入临时数组temp中，这样就保证了值相同的元素，合并前后顺序并不会改变。所以，归并排序是一个稳定的排序算法。

第二、归并排序的时间复杂度是多少？

归并排序涉及递归，时间复杂度的分析稍微有点复杂，我们正好借此机会来学习一下，如果很细递归代码的时间复杂度。

在递归那一节我们讲过，递归适用场景是，一个问题a可以分解为多个子问题b、c，那求解问题a就可以分解为求解子问题b、c。子问题b、c解决之后，我们再把b、c的结果合并成a的结果。

我们定义求解问题a的时间为T(a)，求解问题b、c的时间分别是T(b)、T(c),那我们就可以得到这样的递推公式：$T(a) = T(b) + T(c) + K$。其中K是将两个子问题b、c的结果合并所需的时间。

从上面的分析，我们得出一个重要的结论：不仅递归求解的问题可以写成递推公式，递推代码的时间复杂度也可以写成递推公式。

套用这个公式，我们来分析一下归并排序的时间复杂度。

我们假设对n个元素进行归并排序需要的时间是T(n)，那分解成两个子数组排序的时间都是T(n/2)。我们知道，merge函数合并两个有序子数组的时间复杂度是O(n)。所以套用前面的公式，归并排序的时间复杂度计算公式是：
$$
\begin{cases}
T(1) = C; & n=1 \\[2ex]
T(n) = 2*T(\frac{n}{2}) + n; & n>1
\end{cases}
$$

通过这个公式，如何来求解T(n)呢？还不够直观，我们再来进一步分解一下计算过程

$$
\begin{align*}
T(n) \ &= \ 2*T(\frac{n}{2}) \ + \ n \\[2ex]
&= 2*(2 * T(\frac{n}{4}) + \frac{n}{2}) \ + \ n \qquad = 4*T(\frac{n}{4}) + 2*n \\[2ex]
&= 4*(2* T(\frac{n}{8}) + \frac{n}{4}) \ + \ 2 * n \ \; = 8*T(\frac{n}{8}) + 3*n \\[2ex]
&= 8*(2* T(\frac{n}{16}) + \frac{n}{8}) \ + \ 3 * n \ \; = 16*T(\frac{n}{16}) + 4*n \\[2ex]
&= …… \\[2ex]
&= 2^{k} * T(\frac{n}{2^{k}}) + k * n
\end{align*}
$$

这样一步步推导，我们可以得到$T(n) \ = \ 2^{k} * T(\frac{n}{2^{k}}) + k * n $。当$T(\frac{n}{2^{k}})=T(1)$时，也就是$\frac{n}{2^{k}} = 1$时，我们得到$k = log_{2}n$。我们将k值带入上面的公式得到$T(n) \ = \ Cn + n*log_{2}n$。如果我们用大O表示法来表示的话，$T(n)$就等于$O(n*log_{2}n)$。所以归并排序的时间复杂度是$O(n*log_{2}n)$。

从我们的原理分析和代码可以看出，归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管最好、最坏、平均情况时间复杂度都为$O(n*log_{2}n)$。

第三、归并排序是不是原地排序算法呢？

归并排序的时间复杂度在任何情况下都是$O(n*log_{2}n)$，看起来非常优秀。待会你会发现，即使是快速排序，最坏情况下时间复杂度也是$O(n^2)$，但是归并排序并不像快排那样，应用广泛，这是为什么？因为它有一个指明的弱点，那就是归并排序并不是一个原地排序算法 。

这是因为归并排序的合并函数，在合并两个有数组为一个有序数组时，需要借助额外的临时存储空间。这一点很好理解，那归并排序的空间复杂度到底是多少呢？是O(n),还是$O(n*log_{2}n)$，该如何分析呢？

如果我们继续按照分析递归时间复杂度的方法，通过递推公式来求解，那整个归并排序的空间复杂度就是$O(n*log_{2}n)$。不过类似分析时间复杂度那样来分析空间复杂度，这个思路对吗？

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


快速排序的原理


我们再来看快速排序的原理，我们习惯性的把它简称为“快排”，快排利用的也是分治思想。乍看起来，他有点像归并排序，但其实思路完全不一样，待会再看两者的区别。现在我们先来看看快排的核心思想。

快排的思想是这样的，如果要排序数组中从下标p-r之间的一组数据，我们选择p到r之间的任意一个数作为pivot分区点。

第一次遍历，我们将p到r之间的数据分为两部分。将小于pivot的放到左边，将大于pivot的放到右边。讲过这一步之后，p-r之间的数据就被分成了三部分，前面p到q-1之间的数据都是小于pivot的，中间是pivot，后面q+1到r之间的数据都是大于pivot的。

根据分治、递归的思想，我们可以用递归排序p到q-1之间的数据和下边在q+1到r之间的数据，知道区间缩小为1，就说明所有的数据都有序了。

如果我们用递推公式来将上面的过程写出来的话，就是这样：

1
2
3
4
5
# 递推公式
quick_sort(p...r) = quick_sort(p...q-1)+quick_sort(q+1...r)

# 终止条件
p>=r

我将递推公式转换为递归代码，你可以根据代码将其翻译为你熟悉的任何语言的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
private static void quickSort(int[] arr, int n) {
    if (n < 1) return;
    quickSort(arr, 0 , n-1);
}
private static void quickSort(int[] arr, int left, int right) {
    if (left>=right) return; 
    int mid = partation(arr, left, right);
    quickSort(arr, left, mid-1);
    quickSort(arr, mid+1, right);
}

// 查找中间位置
private static int partation(int[] arr, int left, int right) {
    int base = arr[left];
    int i = left, j = right;

    while(i<j){
        while (i<j && arr[j] >= base) j--;
        while (i<j && arr[i] <= base) i++;

        if (i<j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    arr[left] = arr[i];
    arr[i] = base;
    return i;

}

// 查找中间位置
private static int partation1(int[] a, int left, int right){
    int pivot = a[right];
    int i = left;
    for (int j=left; j<=right-1;j++){
        if (a[j]<pivot){
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
        }
    }
    a[right] = a[i];
    a[i] = pivot;
    return i;
}

归并排序有一个merge合并函数，快排这里也有一个partation分区函数。partation分区函数实际上我们前面已经讲过了，就是随机选择一个元素作为pivot，然后对A[p…r]分区，函数返回pivot的小标。

如果我们不考虑空间消耗的话，partation分区函数可以写的非常简单。我们申请两个临时数组X和Y，遍历A[p…r]，将小于pivot的元素都拷贝到临时数组X中，将大于pivot的元素都拷贝到临时数组Y中，最后再讲数组X和数组Y中的数据顺序拷贝到数组A[p…r]中。

不过如果按这种思路实现的话，partation函数就需要很多额外的内存空间，所以快排也就不是原地排序算法了。如果我们希望快排是原地排序算法，那它的空间复杂度都是O(1)，那partation分区函数就不能占用太多的内存空间，我们就需要在A[p…r]原地完成分区操作。

原地分区函数的实现思路非常巧妙，我下面用伪代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
partation(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的相对位置就会发现变化。所以快速排序并不是一个稳定的排序算法。

到此，快速排序的原理你应该掌握了。现在，我们来看另一个问题：快速排序和归并排序都是用的分治思想，递推公式和递归代码也非常相似，那它们的区别到底在哪里呢？

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


快速排序的性能分析


现在我们来分析一下快速排序的性能。上面在讲解快排原理的时候，已经分析了快速排序的稳定性和空间复杂度。快排是一种原地、不稳定的排序算法，现在我们来分析一下快排的时间复杂度。

快排也是用递归实现的，对于递归代码的时间复杂度，我前面总结的公式，这里也还是适用的。如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那块拍的时间复杂度递推求解公式跟归并是一样的。所以快排的时间复杂度也是$O(n*log_{2}n)$。

$$
\begin{cases} \\
\ T(1) = C; & n=1 \\[2ex]
\ T(n) = 2*T(\frac{n}{2}) + n; & n>1
\end{cases}
$$

但是公式成立的前提是我们每次分区操作，选择的pivot都很合适，正好是将大区间对等一份为二，但这种情况是很难实现的。

我举一个极端的例子，加入数组中的数据原来就已经是有序的了，比如1,3,5,6,8，如果我们每次选择最后一个元素作为pivot，那每次分区得到的两个区间都是不对等的。我们需要进行大约n次分区操作，才能完成快排的整个过程，这种情况下，快排的时间复杂度就从$O(n*log_{2}n)$退化成了$O(n^2)$。

我们刚刚讲了两个极端情况下的时间复杂度，一个是分区极其均衡，一个是分区极其不均衡。他们分别对应到快排的最好时间复杂度和最坏情况时间复杂度。那快排的平均时间复杂度是多少呢？

实际上，递归的时间复杂度的求解除了递推公式之外，还有递归树，在树那一节再讲，这里暂且不说，这里直接给出结论：快排的平均复杂度也是$O(n*log_{2}n)$，只有在极端情况下才会退化为$O(n^2)$。而且我们也有办法将这个概率降到很低，如何来做，我们后面排序优化再讲。


解答开篇


快排的核心思想是分治和分区。我们可以利用快排的思想，来解答开篇的问题：O(n)的时间复杂度内求解无序数组中第K大元素，比如4,2,5,12,3这样一组数据，第三大元素就是4。

我们选择数组区间A[p…r]最后一个元素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< p+1，那我们就在A[0…p-1]区间内查找。

我们再来看看，为什么上述解决问题的时间复杂度是O(n)呢？

第一次分区查找，我们需要对大小为n的数组进行分区操作，遍历n个元素。第二次分区查找，只需要对大小为2/n的数组执行分区操作，需要遍历n/2个元素。以此类推，分区遍历的元素个数分别为n、n/2、n/4、n/8、n/16……直到区间缩小为1.

如果我们把每次分区遍历的元素个数加起来，就是：n+n/2+n/4+n/8+……+1。这是一个等比数列求和。最后的和为2n-1，所以上述解决问题的时间复杂度为O(n)。


内容小结


归并排序和快速排序是两种稍微复杂的排序算法，他们用的都是分治的思想，代码都是通过递归来实现的。过程非常相似。理解归并排序的重点是理解递推公式和merge合并函数。同理，理解快排的重点是理解递推公式和partation分区函数。

归并排序是一种在任何情况下时间复杂度都比较稳定的算法，这也使得它具有了致命的弱点，即归并排序并不是原地排序算法，空间复杂度比较高，是O(n)。正应为此，他也没有快排应用广泛。

快速排序算法虽然最坏情况时间复杂度是O(n^2),但是平均情况下时间复杂度都是$O(n*log_{2}n)$。不仅如此，快速排序时间复杂度退化到O(n^2)的概率也非常小，我们可以通过合理的选择pivot来避免这种情况。

课后思考

1、现在你有10个接口访问日志文件，每个日志文件大小300MB，每个日志文件里的日志都是按照时间戳从小到大排序的。你希望将这10个较小的日志文件，合并为一个日志文件，合并之后的日志仍然按照时间从小到大排序。如果处理上述排序任务的机器内存只有1GB，你有什么好的解决思路，能快速的将10个日志文件合并吗？

多路归并、外排序