iOS 中的选择、冒泡、插入排序

1.插入排序

分析：插入排序是将一个元素插入到已排序好的有序表中，从而得到一个新的记录数增加1的新的有序表，执行过程一次选出第i个元素插入到前i－1个有序元素的合适位置

代码执行过程：

排序过程

调试结果：

执行结果

时间复杂度问题：

        如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。

2.冒泡排序

分析：每趟排序过程中需要通过比较找到为排序元素中最大的元素，所以我们需要一个外部循环，从数组其实开始，一次比较相邻的两个元素并把较大的放在右边，保证排序的顺序从小到大。

代码执行过程：

代码执行过程

调试结果与上边类似。

时间复杂度问题：

3.插入排序

分析：每趟从排序的元素中找到最小的一次放到左边，执行完一趟刚好排出正确的顺序

排序过程

调试结果与上边类似。

时间复杂度：

选择排序的时间复杂度不像前面几种排序方法那样，前面几种排序方法的时间复杂度不是一眼就能看出来的，而是要通过推导计算才能得到的。一般会涉及到递归和完全二叉树，所以推导也不是那么容易。但是选择排序就不一样了，你可以很直观的看出选择排序的时间复杂度：就是两个循环消耗的时间；

比较时间：T = （n-1)）+ （n -2）+（n - 3）.... + 1;  ===>>  T =  [n*(n-1) ] / 2；

交换时间：最好的情况全部元素已经有序，则 交换次数为0；最差的情况，全部元素逆序，就要交换 n-1 次；

所以最优的时间复杂度  和最差的时间复杂度  和平均时间复杂度  都为 ：O(n^2)