数据结构与算法分析学习笔记。第七章 排序
数据结构与算法分析
7 排序
7.0 预备知识
7.0.1 基本概念
通常约定我们讨论的排序是指整数数组的排序。
Ø 内部排序:元素个数较少(小于几百万),在主存中完成。
Ø 外部排序:元素个数较多(大于几百万),无法在主存中完成而必须要在磁盘上完成的排序。
Ø 稳定:如果a原本在b的前面,而a=b,排序后a仍然在b的前面。
Ø 不稳定:如果a原本在b的前面,而a=吧,排序后a可能会出现在b的后面。
Ø 时间复杂度: 操作次数表示。反映数据规模n和操作次数之间的规律。
Ø 空间复杂度:所需存储空间的度量。反映数据规模n和占用空间之间的规律。
7.0.2 算法分类
通常分为两类:比较类和非比较类
Ø 比较类排序:通过比较来确定元素位置,时间负责度无法突O(nlogn),因此成为非线性时间比较类排序。
Ø 非比较类排序:不通过比较来确定元素位置,可以以线性时间运行,因此成为线性时间非比较类排序。
7.0.3 算法复杂度
7.1 冒泡排序(Bubble Sort)
1 | /** |
7.2 快速排序
1 | /** |
7.3 简单插入排序
1 | /** |
7.4 希尔排序
1 | /** |
7.5 简单选择排序
1 | /** |
7.6 堆排序
堆是一棵顺序存储的完全二叉树。
完全二叉树中所有非终端节点的值均不大于(或不小于)其左右孩子节点的值。
1 | /** |
7.7 归并排序
1 | /** |
7.8 计数排序
1 | /** |
7.9 桶排序
1 | /** |
7.10 基数排序
1 | /** |
本文作者:
Jeff.R
本文链接: https://stefanxiepj.github.io/archives/faa54514.html
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!
本文链接: https://stefanxiepj.github.io/archives/faa54514.html
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!
![知识共享许可协议](https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png)