iOS-排序算法
2021-04-06 本文已影响0人
Aaron升
传送门
iOS-冒泡排序（Bubble Sort）
iOS-选择排序（Selection sort）
iOS-插入排序（Insertion sort）
常见的排序算法
| 排序算法 | 平均时间复杂度 | 特殊情况 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | 最好：O(n) | O(1) | In-place | 稳定 |
| 选择排序 | O(n²) | - | O(1) | In-place | 不稳定 |
| 插入排序 | O(n²) | 最好：O(n) | O(1) | In-place | 稳定 |
时间复杂度
算法的时间复杂度(Time Complexity)是指算法需要消耗的时间。一般来说，计算机算法是问题规模n的函数f(n)，算法执行时间的增长率与f(n)的增长率正相关，称作渐近时间复杂度，简称时间复杂度。
-
忽略加法常数
函数：f(n)=2n+1
当n不断变大的时候：2n+1基本和2n相同，后面的加法常数 基本没有影响。因此忽略加法常数。 -
忽略相乘常数
函数：f(n)=2n
当n不断变大的时候，其实就是n的趋势结果。因此问题规模n相乘的常数项也可以忽略，不影响算法比较。 -
保留最高次项
函数：f(n)=n²+2n
其实就是n²的趋势结果，相比之下2n影响可以忽略不计。因此只保留最高次项。
时间复杂度的优劣对比 常见的数量级大小：越小表示算法的执行时间频度越短，则越优；
复杂度优劣排序，随数据量增大，执行时间增大的幅度越大的，复杂度越高
随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低
优劣排序：
O(1)<O(log*n)<O(n)<O(n*log*n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)
Big-O Complexity Chart
稳定性分析
如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，即它们的位置保持不变，通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的；如果排序后，数据的相对次序有可能会发生变化，则该算法是不稳定的。
- 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
- 不稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
关于选择排序算法为什么不稳定的问题，在《iOS-选择排序（Selection sort）》中有举例子说明。
参考资料
·
