文章目录
article
排序简介
AI文章摘要
qwen-turbo-latest
加载中...
排序简介
排序算法用于重新整理一个序列，使之按照特定的要求进行排列。
基于比较的排序算法
基于比较的算法依赖数据元素间权重比较，排序算法的库默认基于权重的升序排序实现，权重越大的元素被排在后面。
设元素$x$,$y$为被比较元素，$f(x)$为权重计算函数，比较函数定义如下$cmp(x,y)$：
$ cmp(x,y)= \begin{cases} 1 & f(x) > f(y) \\ -1 & f(x) < f(y) \\ 0 & f(x) = f(y) \end{cases} $
以自然数$x$、$y$排序为例：
直觉上我们觉得自然数的数值越大它的权重越大，即$x>y$时$cmp(x,y)=1$，排序算法表现为自然数的升序排序。
若我们定义自然数的数值越小它的权重越大，即$x<y$时$cmp(x,y)=1$，排序算法表现为自然数降序排序。
直觉上我们觉得自然数的数值越大它的权重越大，即$x>y$时$cmp(x,y)=1$，排序算法表现为自然数的升序排序。
若我们定义自然数的数值越小它的权重越大，即$x<y$时$cmp(x,y)=1$，排序算法表现为自然数降序排序。
基于比较的排序
- 计数排序
- 基数排序
- 桶排序
- TimSort
- 梳排序