排序简介
这篇文章介绍了排序算法的基本概念，特别是基于比较的排序算法。文章指出，基于比较的算法依赖于元素间的权重比较，通过定义cmp函数来确定元素间的顺序。文章详细解释了升序和降序排序的cmp函数设计，以及如何通过对cmp取负数来切换排序顺序。文章还提到了排序算法在实际应用中的例子，如搜索引擎广告排序。最后，文章列举了常见的基于比较的排序算法，如选择排序、冒泡排序等。
排序简介
排序算法用于重新整理一个序列，使之按照特定的要求进行排列。
基于比较的排序算法
基于比较的算法依赖数据元素间权重比较，排序算法的库默认基于权重的升序排序实现，权重小的元素被排在前面(优先级更高)。
设元素$x$,$y$为被比较元素，$w(x)$为权重计算函数，如下对比较函数$cmp(x,y)$进行了定义
$ cmp(x,y)= \begin{cases} 1 & w(x) > w(y) \\ -1 & w(x) < w(y) \\ 0 & w(x) = w(y) \end{cases} $
以排序算法实现作者的角度来看，可以通过$cmp(x,y)=1$判断$y$的权重更小，或者通过$cmp(x,y)=-1$判断$x$的权重更小，本项目实现的排序算法是基于前一种方式进行的判断。下面以自然数为例解释如何设计比较函数。
👉升序排序：$x<y$时，$x$排在$y$的前面。
表明当$x<y$时，$x$的权重小于$y$， 则$x>y$时，$x$的权重大于$y$
$ cmp(x,y)= \begin{cases} 1 & x > y \\ -1 & x < y \\ 0 & x = y \end{cases} $
👉降序排序：$x>y$时，$x$排在$y$的前面。
表明当$x>y$时，$x$的权重小于$y$ ，则$x<y$时，$x$的权重大于$y$
$ cmp(x,y)= \begin{cases} 1 & x < y \\ -1 & x > y \\ 0 & x = y \end{cases} $。
通过观察可以发现，对$cmp$取负数能够在升序和降序间进行切换，所以我们只需要实现其中任意一种$cmp$函数即可。比较对象可以扩展到自然界任意对象，一般通过加权平均或其他算法计算出对象的权重数值进行比较。一个现实的例子是搜索引擎广告，一般排在前面的广告受多种因素的制约(如广告费、点击率或紧急程度等)，我们可以对一个广告的各种属性做加权平均作为权重(或其他更复杂的算法，这其实就是搜索引擎的核心技术)，实现升序$cmp$函数，然后通过取负数获取降序$cmp$函数。
初始排序算法默认元素的类型实现了比较方法，调用元素类型的比较方法进行比较，对于自然数则是根据数值的大小进行比较。
基于比较的排序
- 计数排序
- 基数排序
- 桶排序
- TimSort
- 梳排序