Quicksort

最近公司打算招一个新的程序,之前我们的策略一直是只面试并没有笔试题。我想了下笔试题最好不要过于偏重于哪一门语言或者哪一方面的知识,那么最好的就是大学学习的基本知识,包括算法和数据结构等,我也打算让面试者在面试过程中实际写一些代码。因为,通过聊天来判断一个人能力是否合格太虚了。基于此原因,我自己事先去复习了一下快速排序(Quicksort)的知识,并且实现了好几个快速排序的算法,这里会简单介绍 3 个重要的快速排序算法。

1 简介

Robert Sedgewick(《算法》的作者,书写的非常好,当然人肯定是大牛) 称快速排序是 20 世纪最重要的 10 个算法之一,快速排序几乎被用于任何重要的系统排序(system sorts)中,被许多语言标准库作为默认排序算法实现,比如 C 语言中 qsort 就是典型的例子。

快速排序最早由 Tony Hoare 于 1959 年发现的,后期经过了不断的发展、论证得到了许多别的优化方案。在恰当实现的情况下,其性能是归并排序(Mergesort)和堆排序(Heapsort)的 2~3 倍。

快速排序是一种比较排序算法,能够对任何支持 less then 关系的数据进行排序,它不是一种稳定排序(stable sort),意味着相等的元素的相对位置可能会发生改变。对于额外的内存需求很少,这种特定也叫就地排序(in-place sort)。计算机科学家对快速排序做了相当多的研究,在数学上的分析得到平均比较次数是 O(n log n) ,最坏的情况是 O(n^2) 次比较。

阅读全文 “Quicksort”