iOS/OC：插入排序与选择排序的比较

• 选择排序（Selection sort）是最基本的O(n^2)的排序算法，通过依次比较数组中前一个元素跟后一个元素的大小，来找到并记录最小的那个元素的下标，再与第一个元素交换。以此类推，找到第二小的元素的下标，再与第二个元素交换，直到全部遍历完成。

• 插入排序也是一个时间复杂度平均为O(n^2)的算法。

  
  1.png
  

  排序时首先第一个元素不动，因为我们认为它已经在正确的位置了。

2.png

接下来将第二位与第一位进行比较，如果比第一位小，则将二者交换。

3.png 4.png

此时前两位完成。
然后继续将第三位与前一位比较，如果比前一位小，交换二者。

5.png
6.png

再将第二位与前一位比较，比前一位大则结束，进行下一个元素排序，直到全部完成。

7.png

插入排序相比选择排序不同的是，第二层循环可以提前结束，即与前一位比较时，比前一位大，就说明此时元素已经在正确的位置了，直接进行下一个循环。由于可以提前结束内循环，所以在再好的情况下，插入排序的时间复杂度可以达到O(n)的级别。

• 我们代码测试一下。
  首先我们定义可以一个生成随机数数组的方法。

NSMutableArray* createDifferentArr (int count) {
NSMutableArray *arr = [[NSMutableArray alloc] init];
NSInteger random;
for (;;) {
    random = arc4random_uniform(count);
    [arr addObject:[NSNumber numberWithInteger:random]];
      if(arr.count == count){
        return arr;
      }
    }
}

将两个数组分别使用选择排序和插入排序进行排序，并计算耗时。

 NSMutableArray * sortArray1 = createDifferentArr(10000);
 NSMutableArray * sortArray2 = [sortArray1 mutableCopy];
 NSInteger count = sortArray1.count;
 //插入排序
 double startTime1 = CFAbsoluteTimeGetCurrent();
 for (int i = 1; i<count; i++) {
    for (int j = i; j>0; j--) {
      if (sortArray1[j] < sortArray1[j-1]) {
        [sortArray1 exchangeObjectAtIndex:j withObjectAtIndex:j-1];
      }else{
        //提前结束，跳出循环
        break;
      }
    }
  }
 double endTime1 = CFAbsoluteTimeGetCurrent();
 NSLog(@"插入排序用时:%f s",endTime1 - startTime1);

 //选择排序
 double startTime2 = CFAbsoluteTimeGetCurrent();
 for (int i = 0; i< count; i++) {
   int minIndex = i;
   for (int j = i + 1; j < count; j++) {
     if (sortArray2[j] < sortArray2[minIndex]) {
       minIndex = j;
     }
   }
    [sortArray2 exchangeObjectAtIndex:i withObjectAtIndex:minIndex];
 }
    double endTime2 = CFAbsoluteTimeGetCurrent();
    NSLog(@"选择排序用时:%f s",endTime2 - startTime2);

一万数量级打印的结果为：

2017-07-10 18:31:53.407 插入排序用时:1.262208 s
2017-07-10 18:31:55.229 选择排序用时:1.821002 s

2017-07-10 19:13:19.017 插入排序用时:1.281390 s
2017-07-10 19:13:20.891 选择排序用时:1.872755 s

此时相差将近0.6秒。
而在两万的量级时，打印结果为：

2017-07-10 19:20:17.962 插入排序用时:5.300281 s
2017-07-10 19:20:25.706 选择排序用时:7.742351 s

2017-07-10 19:20:49.626 插入排序用时:5.283061 s
2017-07-10 19:20:57.549 选择排序用时:7.921418 s

此时相差了两秒多。

---

• 而如果要排序的数组是近乎有序的数组时，差别将更加明显。
  我们修改下上面的生成随机数组的函数。将随机数范围修改到0~1
  random = arc4random_uniform(2);

此时在两万数量级下，打印结果为：

2017-07-10 20:38:45.100 插入排序用时:2.603737 s
2017-07-10 20:38:52.367 选择排序用时:7.265069 s

2017-07-10 20:39:29.732 插入排序用时:2.630652 s
2017-07-10 20:39:37.727 选择排序用时:7.993733 s