快速排序(Quicksort)是一种描述序列中,元素有序性的方式……但是,等等,什么是「序列」,什么是「有序」呢?
在高中的时候,我们都接触过一个叫「集合」(Set)的概念,直观上说,集合就是一堆不重复的任意概念被放到了一块,因此集合是没有序的:只要装的东西一样,那就是同一个集合。所以只可以判断一个东西在某个集合里或者不在某个集合里,却不能说在某个集合里的两个东西谁比谁排得更前。比如说,一个装有 {a,→,1,Δ,∅} 的集合,我们可以说 a 在这个集合里,b 不在这个集合里,却不能说 → 比 Δ 前,因为 {a,→,1,Δ,∅} 和 {a,1,Δ,∅,→} 是同一个集合。
所以,稍微修改一下集合,让里面的每个东西都具有自己独一无二的位置,那就是一个「序列」(Tuple)了。因为现在每个序列中的东西都有独一无二的位置,序列里就允许出现看起来相同的东西了:因为至少它们的位置一定是不同的。比如序列 [a,→,1,Δ,∅],其中 a 在 0 号位置,Δ 在 3 号位置。把任意两个元素调换之后的序列,都是新的序列。