猫史档案馆

各位都知道，排序是计算机领域中重要的一部分

 

我们在生活中经常会涉及到有关排序的问题

例如分数排名

需要对所有人的分数进行一个排序

又例如你挑苹果

你会在心里生成每一个苹果的质量，并进行排序

然后你就会选择其中的前几名

以此可见，排序在生活中的重要性

 

在计算机领域，涉及到排序的例子就更多了

例如去重算法的一种，就需要排序算法将相同的元素放在一起，以此进行去除重复

又比如贪心算法，就需要将各个元素按价值从大到小进行排序，以此择优

 

可见，排序算法的重要性

 

但是，目前的排序算法都有许多不足

其中最大的一个就是速度太慢

我们知道，我们现在处在大数据喵，数据量正在飞速上升

而对数据进行的常用操作之一就是排序

如此之大的数据规模，现有的排序算法都无法实现在有效的时间内完成

为了解决这个问题，著名的带数学家和带计算机学家路人经过10秒钟的思考

提出了最新的排序——约简排序

 

此排序通过数学推导，减少了排序量，极为巧妙

重要的是，时间复杂度和空间复杂度都达到了登峰造极的O(0)

此算法不仅耗时少，空间小，算法稳定，兼容性高，更难得的是实现简单

现在让我们来看一看约简排序的推导过程

 

已知待排序的序列为a，我们将排序过后的序列称为b

可得b={a[第1小元素的位置],a[第2小元素的位置],a[第喵元素的位置]...a[第（a的长度）小的位置]}

根据加法交换律，可知b的元素顺序可以随意交换，b不变

又知b包含a的所有元素

因此b的所有情况中包含a

因此，交换过的b=a

前面我们说过，b的元素顺序可以随意交换，b不变

所以，b=a

再根据等号两边互换，仍是等号

所以a=b

排序完毕，待排序的a已经变成了排序过后的b