快速排序去重？计算机专家与程序员的不同

姜咏江

      n个数排序算法时间复杂度是多少？一般程序员会脱口而出：O(n!)。这是按照数学家的想法，从小到大，或者从大到小，一一比较得到的算法。如果你是一位计算机专家，不是一般的程序员，就可以用O(n)时间复杂度得出结果。不信？

    我要介绍的方法，不仅可以快速排序，而且可以去掉重复的数。

    计算机专家要你准备一块足够大的干净存储空间（一般的计算机都可以满足）。计算机专家排序的秘诀就是“将数放到这个数所标志的地址单元”！

    实际上，计算机内部并没有一般的实数，只有无符号的二进制整数（更多的请看本人写的《自己设计制作CPU与单片机》第10章），因而你可以将一个数放在这个数标志的存储地点（用指针实现），于是n个数排序算法时间复杂度就从O(n!)转化成O(n)啦。不仅如此，那些重复的数也会剩下唯一的一个了。

    此文为2016中国计算机大会P vs.NP论坛准备。

2016-8-1