第一章 绪论
2 Topics
第二章 线性结构
7 Topics | 4 Quizzes
第四章 树(tree)
18 Topics | 7 Quizzes
第五章 图(gragh)
15 Topics | 6 Quizzes
第六章 查找
9 Topics | 2 Quizzes
第七章 排序(sort)
12 Topics | 4 Quizzes
第八章 简单算法
7 Topics
第九章 基础算法
18 Topics | 2 Quizzes
第十章 动态规划
19 Topics | 1 Quiz
第十一章 数学
14 Topics | 2 Quizzes
第七章 排序(sort)
1. 排序的功能：将一组数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。(升序或降序)
十种常见排序算法可以分为两大类：
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
排序算法复杂度及稳定性
| 类型 | 算法 | 时间复杂(平均) | 时间复杂度最坏(最坏) | 时间复杂度(最优) | 空间复杂度 | 稳定性 | 备注 |
| 插入排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 | ||
| 比 | 冒泡排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 | |
| 较 | 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 | |
| 类 | 希尔排序 | O(n1.3) | O(n2) | O(n) | O(1) | 不稳定 | |
| 快速排序 | O(nlogn) | O(n2) | O(nlogn) | O(logn) | 不稳定 | ||
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | ||
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | ||
| 非 | 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 稳定 | |
| 比 | 桶排序 | O(n+n2/k+k) | O(n2) | O(n) | O(n+k) | 稳定 | 桶内排序按插入 |
| 较 | 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 |
Lesson Content
0% Complete
0/12 Steps