【重温基础算法】内部排序之快速排序法

内部排序之快速排序法

对冒泡排序的一种优化

主要思想

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

通过一趟排序将待排记录分割成独立的两个部分，一部分的关键字比另一部分的关键字小，则可以分别对两部分记录继续进行排序。

1. 选取任务选取的一个记录，作为枢轴或（支点）（pivot）
2. 重新排列记录，所有关键字比pivot值小的摆放在pivot前面，所有关键字比pivot值大的摆在pivot的后面（相同的数可以到任一边）。在这个分区退出之后，该pivot就处于数列的中间位置。这个称为分区（partition）操作；
3. 重复执行步骤2。把小于pivot关键字的子数列和大于pivot关键字的子数列排序。

过程演示

JAVA代码

package sort;

public class QuickSort {

    private static int count = 1;

    public static void main(String[] args) {
        int[] o = {49, 38, 45, 27, 46, 13, 27, 8};
        System.out.print("排序前: ");
        for (int t : o) {
            System.out.print(t);
            System.out.print(" ");
        }
        System.out.println();

        // 算法部分
        int left = 0;
        int right = o.length - 1;

        quickSort(o, left, right);

        System.out.print("排序后: ");
        for (int t : o) {
            System.out.print(t);
            System.out.print(" ");
        }
        System.out.println();

    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        } else {
            count++;
        }
    }

    private static int partition(int[] arr, int left, int right) {
        // left位置的记录就是pivot,index代表比pivot小的下标
        int index = left + 1;
        System.out.print("第" + count + "趟pivot=" + arr[index - 1] + ",排序后: ");

        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[left]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, left, index - 1);
        for (int t : arr) {
            System.out.print(t);
            System.out.print(" ");
        }
        System.out.println();
        count++;
        return index - 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

执行结果

排序前: 49 38 45 27 46 13 27 8 
第1趟pivot=49,排序后: 8 38 45 27 46 13 27 49 
第2趟pivot=8,排序后: 8 38 45 27 46 13 27 49 
第4趟pivot=38,排序后: 8 27 27 13 38 45 46 49 
第5趟pivot=27,排序后: 8 13 27 27 38 45 46 49 
第8趟pivot=45,排序后: 8 13 27 27 38 45 46 49 
排序后: 8 13 27 27 38 45 46 49 
1
2
3
4
5
6
7

算法分析

时间复杂度分析

经过上述一趟快速排序，我们只确定了一个元素的最终位置，我们最终需要经过$n$趟快速排序才能将一个含有$n$个数据元素的序列排好序，下面我们来分析其时间复杂度.

设 $n$ 为待排序数组中的元素个数， $T(n)$为算法需要的时间复杂度则
$$T(n)=\{\begin{array}{ll}D& n\le 1\\ D(n)+T(I_1)+T(I_2)& n>1\end{array}$$
其中 $D(n)=n-1$ ,是一趟快排需要的比较次数，一趟快排结束后将数组分成两部分$I_1$ 和$I_2$。

最好时间复杂度

最好的情况是，每一次划分都正好将数组分成长度相等的两半
$$T(n)=\{\begin{array}{ll}D(1)& n\le 1\\ D(n)+T(\frac{n}{2})+T(\frac{n}{2})& n>1\end{array}$$

$$\begin{array}{rl}\therefore T(n)& =D(n)+2T(\frac{n}{2})\\ & =D(n)+2D(\frac{n}{2})+2T(\frac{n}{4})\\ & .\\ & .\\ & .\\ & =D(n)+2D(\frac{n}{2})+4D(\frac{n}{4})+...+2^{k}D(\frac{n}{2^k})\\ & =n-1+2(\frac{n}{2}-1)+4(\frac{n}{4}-1)+...+2^k(\frac{n}{2^k}-1)\\ & =(n-1)+(n-2)+(n-4)+...+(n-2^k)\\ & ⟹\sum _{k=1}^{n}n-2^k=kn-2^k+1\\ & \because k=lo{g}_2^n\\ & \therefore 原式=nlo{g}_2^n-2n+1⟹\boxed{O(nlo{g}_2^n)}\end{array}$$

最坏时间复杂度

最坏情况下，每一次划分都将数组分成了$0$和$n-1$两部分
$$T(n)=\{\begin{array}{ll}D& n\le 1\\ D(n)+T(n-1)+T(0)& n>1\end{array}$$

$$\begin{array}{rl}\therefore T(n)& =D(n)+2T(n-1)\\ & =D(n)+D(n-1)+T(n-2)\\ & .\\ & .\\ & .\\ & =D(n)+D(n-1)+D(n-2)+...+D(1)\\ & =(n-1)+(n-2)+(n-3)+...+0\\ & ⟹\sum _{k=0}^{n}k=\frac{n(n-1)}{2}\\ 原式& =\frac{n(n-1)}{2}⟹\boxed{O(n^2)}\end{array}$$

平均时间复杂度

任意一种划分情况出现的概率都相等
$$All=\{\begin{array}{ll}{I}_1=0& I_2=n-1\\ I_1=1& I_2=n-2\\ .& \\ .& \\ .& \\ I_1=n-1& I_2=0\end{array}$$

$$\begin{array}{rl}\therefore T_{avg}(n)& =D(n)+\frac{1}{n}\ast \sum _{i=0}^{n-1}{T}_{avg}(i)+T_{avg}(n-i)\\ & =D(n)+\frac{2}{n}\ast \sum _{i=0}^{n-1}{T}_{avg}(i)\\ T_{avg}(n-1)& =D(n-1)+\frac{2}{n-1}\ast \sum _{i=0}^{n-2}{T}_{avg}(i)\\ n{T}_{avg}(n)-(n-1)T_{avg}(n-1)& =nD(n)+2\sum _{i=0}^{n-1}{T}_{avg}(i)-(n-1)D(n-1)-2\ast \sum _{i=0}^{n-2}{T}_{avg}(i)\\ & =nD(n)-(n-1)D(n-1)+2T_{avg}(n-1)\\ & =n(n-1)-(n-1)(n-2)+2T_{avg}(n-1)\\ & =2(n-1)+2T_{avg}(n-1)\\ 移项得& \\ n{T}_{avg}(n)& =2(n+1)+2T_{avg}(n-1)+(n-1)2T_{avg}(n-1)\\ & =2(n+1)+(n+1)2T_{avg}(n-1)\\ 等式两边同时除以n(n+1)得& \\ \frac{T_{avg}(n)}{n+1}& =\frac{T_{avg}(n-1)}{n}+\frac{2(n-1)}{n(n+1)}\\ 令B(n)=\frac{T_{avg}(n)}{n+1}得& \\ B(n)& =B(n-1)+\frac{2(n-1)}{n(n+1)}\\ & =\boxed{B(n-2)+\frac{2(n-2)}{n(n-1)}}+\frac{2(n-1)}{n(n+1)}\\ .& \\ .& \\ .& \\ & =B(1)+\sum _{i=1}^n\frac{2(i-1)}{i(i+1)}\\ & =B(1)+\sum _{i=1}^n\frac{2(i+1)-4}{i(i+1)}\\ & =\sum _{i=1}^n[\frac{2}{i}-\frac{4}{i(i+1)}]\\ \because \sum _{i=1}^n\frac{4}{i(i+1)}& =4\sum _{i=1}^n[\frac{i+1-i}{i(i+1)}]\\ & =4\sum _{i=1}^n[\frac{1}{i}-\frac{1}{i(i+1)}]\\ & =4[1-\frac{1}{n+1}]=\boxed{4\frac{n}{n+1}}\\ \because \sum _{i=1}^n\frac{1}{i}& \approx 0.577216+ln(n)\\ \therefore B(n)& =2\ast 0.577216+2\ast ln(n)+4\frac{n}{n+1}\\ 代回B(n)=\frac{T_{avg}(n)}{n+1}& \\ T_{avg}(n)& =2(n+1)ln(n)-4n+2\ast 0.577216(n+1)⟹\boxed{O(nlo{g}_2^n)}\end{array}$$

空间复杂度

快速排序的空间复杂度取决于分划基准的选择，每次都选在中间，$O(lo{g}_2^n)$若基本有序，退化为冒泡，栈的深度$O(n)$。

$O(lo{g}_2^n)$就是递归的深度，递归的时候使用的栈空间稍微优化一点的快排，比如取首尾中三个数据，取其中间的值作为划分标准，不会出现退化到冒泡的可能。

计算参考：https://zhuanlan.zhihu.com/p/341201904