- Notifications
You must be signed in to change notification settings - Fork3
📊 Animation and analysis of classical sorting algorithms.（动画详解十大经典排序算法）
NotificationsYou must be signed in to change notification settings
fiteen/Sorting-Algorithm
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
由于待排序的元素数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两类：一类是内部排序，指的是待排序列存放在计算机随机存储器中进行的排序过程；另一类是外部排序，指的是待排序的元素的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
我们可以将常见的内部排序算法可以分成两类：
比较类排序：通过比较来决定元素间的相对次序，时间复杂度为 O(nlogn)～O(n²)。属于比较类的有：
| 排序算法 | 时间复杂度 | 最差情况 | 最好情况 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | In-place | ✔ |
| 快速排序 | O(nlogn) | O(n²) | O(nlogn) | O(logn) | In-place | ✘ |
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | In-place | ✔ |
| 希尔排序 | O(nlog²n) | O(n²) | O(n) | O(1) | In-place | ✘ |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | In-place | ✘ |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | In-place | ✘ |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | Out-place | ✔ |
非比较类排序：不通过比较来决定元素间的相对次序，其时间复杂度可以突破 O(nlogn)，以线性时间运行。属于非比较类的有：
| 排序算法 | 时间复杂度 | 最差情况 | 最好情况 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 桶排序 | O(n+nlog(n/r)) | O(n²) | O(n) | O(n+r) | Out-place | ✔ |
| 计数排序 | O(n+r) | O(n+r) | O(n+r) | O(n+r) | Out-place | ✔ |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | Out-place | ✔ |
名词解释：
时间复杂度：描述一个算法执行时间与数据规模的增长关系
空间复杂度：描述一个算法占用空间与数据规模的增长关系
n：待排序列的个数
r：“桶”的个数（上面的三种非比较类排序都是基于“桶”的思想实现的）
d：待排序列的最高位数
In-place：原地算法，指的是占用常用内存，不占用额外内存。空间复杂度为 O(1) 的都可以认为是原地算法
Out-place：非原地算法，占用额外内存
稳定性：假设待排序列中两元素相等，排序前后这两个相等元素的相对位置不变，则认为是稳定的。
看完整文章可以直接戳这里
About
📊 Animation and analysis of classical sorting algorithms.（动画详解十大经典排序算法）
Topics
Resources
Uh oh!
There was an error while loading.Please reload this page.
Stars
Watchers
Forks
Releases
No releases published
Packages0
No packages published