快速排序

前言

掌握了基础的排序算法,就可以在进阶高级的算法的路上渐行渐远了。今天试着学习一下高端一点的排序算法,快速排序。快速排序的期望时间复杂度较前面低端的要好一点为O(nlgn)。

快速排序

快速排序的思想运用了二分的思路,找一个基准点,将大于基准点的放右边,小于基准点的放左边。每一次循环完,以基准线分割两边,分别寻找基准点重复循环操作。在网上看了许多不同的实现方式,今天在这里介绍一下学院派的实现方式。
我们知道二分实际上是个递归的过程,快速排序就是对基准点两边进行递归,那么核心的是如何进行基准点的选取和基准点一边的递归实现。
我们先来一份伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
quickSort(a,l,r)
if l < r
q = partition(a,l,r)
quickSort(a,l,q-1)
quickSort(a,q+1,l)
partition(a,l,r)
key = a[r]
i = l-1
j = l
while(j < r)
if a[j]<=key
i++
exchange a[i] with a[j]
j++
exchange a[i+1] with a[r]
return i+1;

这里初始的基准点为数组尾元素,分析一下核心的排序函数partition,我们可以得出这样的规律:

1
2
3
j从数组第一个元素开始递增,i从空开始递增,每当数组元素a[j]中小于a[r]时,i++并a[i]与a[j]交互。这样使得:
1.当 i<k<j时,a[k]>a[r]
2.当 l<=k<=i时,a[k]<=a[r]

从中我们可以发现,经过一轮循环后,将数组分割成大于基准点和小于基准点两部分,而基准点的位置则在i+1处,所以循环结束后,将a[r]与a[i+1]交换,实现整个数组的分割。

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
int[] quickSort(int[] num, int left, int right) {
if (left < right) {
int baseIndex = partiton(num, left, right);
quickSort(num, left, baseIndex - 1);
quickSort(num, baseIndex + 1, right);
}
return num;
}

private int partiton(int[] num, int left, int right) {
int baseIndex = right;
int i = left - 1;
int j = left;
int key = num[baseIndex];
while (j < right) {
if (num[j] <= key) {
i++;
exchange(num, i, j);
}
j++;
}
exchange(num, i + 1, baseIndex);
return i + 1;
}

private void exchange(int[] num, int i, int j) {
int temp = num[j];
num[j] = num[i];
num[i] = temp;
}

时间复杂度分析

在最理想的情况下,partition得到的两个子数组的规模都不超过n/2,而partition的复杂度为r-l+1 =O(n),所以我们得出快排的时间复杂度计算公式:
T(n) = 2T(n/2) + O(n)
求解得T(n) = O(nlgn)

坚持原创技术分享,您的支持将鼓励我继续创作!