iOS-排序算法

传送门

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）》中有举例子说明。

参考资料

RUNOOB.COM-1.0 十大经典排序算法

·