您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识

排序算法中的“稳定”和“不稳定”，有没有一个结论性的因素导致该算法稳定或不稳定？

算法,稳定,就像排序算法中的“稳定”和“不稳定”，有没有一个结论性的因素导致该算法稳定或不稳定？

发布时间：2020-12-06加入收藏来源：互联网点击：

排序算法中的“稳定”和“不稳定”，有没有一个结论性的因素导致该算法稳定或不稳定？

回答于 2019-09-11 08:43:50

回答于 2019-09-11 08:43:50

稳定与否原本取决于测试用例。

举个例子来说，你觉得你打字很快，那么首先是因为你打的是中文，然后再就是你打的是有显著内容含义的口语化句子。如果打古文，速度就降下来一些，打没含义的一大堆生僻字，就更慢，再来试试用韩文键盘打韩文，你的速度甚至比韩国人还慢。

算法也一样，一些算法基于原来的序列是大致分布好的（尽管用例随机，但大致上是有某些分布的概率性规律，就像你打中文口语化句子里有很多词原本在输入法里就是一个词，你不需要一个个选字）来运作效率就很高，另一些用例分布不是那么适应这种算法的，运作效率就显著变低（就像让你打韩文）。这种情况我们就称之为不稳定。

反观稳定的例子，就像你和韩国人打英文文章，大家英文水平都差不多，也都不是母语，或者说假设你和韩国人原本都没学过英文，就只是照键盘打出来，那无论原文如何，打字速度都差不多，这就是稳定的例子。

再深究一步，什么决定了稳定与否，那就是设计的算法是否对测试用例挑食，或者说对于算法，你能不能找得出极端的例子使这个算法排好第一个数之后，要花费很长时间才能排好第二个数。