现在有一个问题，对于所有的输入来说，前面得到的结果是否都成立呢？第二种排序法在少量字符串的时候性能也许是最好的。但是，输入数据有很多地方可能变化：
·输入数据可能有1 000 000个字符串。算法如何处理如此大规模的数据？
·输入数据可能会是部分有序状态，也就是说，几乎所有的元素所在的位置离最终位置并不是很远。
·输入数据可能包含重复的值。
·无论输入数据的规模n是多少，输入数据都可以从一个小得多的数据集扩展而来，不过会有相当多的重复值。
虽然从图2-2上来看，第四种排序法在排序n个乱序字符串的时候是最慢的，但是处理已经排序的数据却是最快的。但是，随着n的增长，第四种排序法的领先优势消失得非常快，我们从图2-3上可以看到，在对16个乱序的字符串进行排序时，第四种排序法就已经失去领头羊的位置了。
图 2-3 处理完全或者几乎有序的数据时，排序算法的性能表现尽管如此，假设一个包含n个字符串的输入，并且这个输入已经是几乎有序，其中n/4个字符串（占总字符串的25%）被交换到仅仅是离最终位置4个元素。最终结果如图2-4所示，我们看到第四种排序法性能表现远远好于其他的排序算法。
图 2-4 处理几乎有序数据时，第四种排序法胜出我们得到这样一个结论，对于许多问题来说，并不存在单一的最优算法。选择一个算法需要对问题有着充分的理解，并知道这个问题将要处理数据规模的概率分布情况，还有算法的实际行为也必须要考虑到。
在这里我们提供一些指导，算法通常会分成三种情况进行分析：
最坏情况
定义一类输入，在这类输入下，算法表现出了最坏的运行性能。算法设计人员需要明白，这类输入的共同性质阻止了算法高效地运行，而不只是针对特定的输入。
平均情况
平均情况是表示算法在随机给定的数据上期望的执行情况。通俗地说，一些输入可能会在某些特殊情况下耗费程序大量的时间，但是大部分的输入并不会这样。这个衡量标准描述了用户对算法性能的期望。
最好情况
定义一类输入，算法在这类输入下表现出了最好的运行性能。对于这类输入来说，算法只进行很少的计算。不过在实际情况下，最好情况很少出现。
通过分析三种情况，大致了解了算法的性能，那么接下来你需要为将要面临的问题选择一个算法。
最坏情况
大多数问题都可能会处理一些比n大的数据。任意给定一个n，算法或者程序在处理所有规模为n的数据，其性能可能会动态地发生变化。给定一个程序和n，这个程序的最坏运行时间就是处理所有规模为n的数据所需要的最长运行时间。
我们也看到，最坏情况是对整个世界的一个悲观的分析。但是我们还是非常关注最坏情况，因为：
追根刨底的欲望
这通常是对一个算法复杂度的最早的分析。
实际运行时的限制
如果你需要设计一个系统，协助外科医生进行体外循环心脏手术，那么长时间的运行（即使这种情况是不经常发生）当然不可能接受。
更正式地说，如果Sn是数据集合si中规模为n的子集，t表示算法在每一份数据上的运行时间，那么最坏情况下，对于所有si∈Sn，算法在Sn上的运行时间是t(si)的最大值。我们将在Sn下的最长时间记做Twc(n)，Twc(n)的增长率表示算法在最坏情况下的复杂度。
一般来说，没有足够的资源来计算每一份数据si，然后检查算法在哪份数据上表现最坏。于是，给定算法的描述，算法分析人员总是想方设法地精心准备可能会导致最坏情况的输入数据。