排序算法是学习算法时十分重要的部分,尤其是在大量数据处理方面扮演十分重要的角色。这次我们学习使用最广泛,最流行的排序算法——快速排序算法。


0. 快速排序

快速排序与归并排序一样是一种分治的排序算法,它将一个数组分成两个子数组,将两部分独立起来。与归并排序不同的是,而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。

快速排序会对数组进行切分,随机选定一个元素,将小于该元素的元素放在左边,大于该元素的元素放在右边。左右两边形成两个子数组,继续递归排序,直到数组排序完成。

1. 快速排序算法

1.1 切分数组辅助方法

快速排序最重要的部分就是如何高效的切分数组,所以我们先介绍切分方法的实现。

private static int partition(Comparable[] a, int left, int right) 
{
int p = left,q = right + 1; // 左右扫描指针
Comparable v = a[left]; // 切分元素
while (true)
{
while (less(a[++p], v)) if (p == right) break;
while (less(v, a[--q])) if (q == left) break;
if (p >= q) break;
exch(a, p, q);
}
exch(a, left, q); // 将v = a[q]放入正确的位置
return q; // 返回切分元素索引
}

1.2 快速排序实现

public class Quick 
{
public static void sort(Comparable[] a)
{
StdRandom.shuffle(a); // 消除对输入的依赖
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int left, int right)
{
if (right <= left) return;
int q = partition(a, left, right);// 切分
sort(a, left, q-1); // 将左半部分a[left .. q-1]排序
sort(a, q+1, right); // 将右半部分a[q+1 .. right]排序
}
}

1.3 快速排序分析

快速排序切分方法的内循环只会用一个递增的索引将数组元素和一个定值比较,这种简洁性是快速排序的一个优点。快速排序另一个速度优势在于它的比较次数很少。

将长度为 N 的无重复数组排序,快速排序平均需要大约 2NlnN 次比较(以及 1/6 的交换)。快速排序最多需要约 (N^2)/2 次比较,但随机打乱数组能够预防这种情况。

总结:

对于大小为 N 的数组,快速排序要比归并排序要更快一些。快速排序的比较次数比归并排序多39%,但是移动元素的次数要更少。


参考文献:算法(第四版) —— 人民邮电出版社

评论