可比较的元素

在待排序的数据集合中的元素必须是全序的。也就是说，对于数据集合里的任意两个元素，它们之间的关系只有以下三种表述的一种：p=q、p＜q或者p＞q。通常排序的原始类型包括整数、浮点值和字符。当复合元素（如字符串）需要被排序时，复合结构中的每个对应元素的词典序就用来决定这些复合结构的顺序位置，这样就将复杂的排序降为原始类型的排序了。例如，单词"alphabet"被看做比"alternate"小但是比"alligator"大，这是按照这样的规则来排序的，从左至右对比每一个字母直到一个单词末尾或者这个单词中的字母比其他单词中的同样位置的字母大或者小（如ant比anthem小）。考虑了如下因素之后，排序问题就变得复杂了，例如大小写（"A"是否大于"a"），变音符号（“è”是否小于“ê”）和双元音（“æ”是否小于"a"）。注意，强大的Unicode标准（参考http://www.unicode.org/versions/latest）对字符进行了编码，例如UTF-16利用4个字节来表示每个字符。Unicode协会（www.unicode.org）已经开发了一个排序标准（叫做“校对算法”）来处理不同语言和文化中的各种各样的排序法则（Davis和Whistler,2008）。

对于本章中将要讨论的算法，我们假设存在一个比较函数，叫做cmp，用来比较p、q两个元素，如果p=q，返回0；p＜q返回负数；p＞q返回正数。如果元素是复杂结构的数据，cmp函数也许只是比较这些元素的“键值”。例如，一个有着视频显示的机场候机楼只是按照目的地或者离港时间升序显示离港航班，而航班号却是无序的。