- 选择排序（Selection sort）是最基本的O(n^2)的排序算法，通过依次比较数组中前一个元素跟后一个元素的大小，来找到并记录最小的那个元素的下标，再与第一个元素交换。以此类推，找到第二小的元素的下标，再与第二个元素交换，直到全部遍历完成。
-
插入排序也是一个时间复杂度平均为O(n^2)的算法。
1.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
