- 選擇排序（Selection sort）是最基本的O(n^2)的排序算法箱锐，通過依次比較數(shù)組中前一個元素跟后一個元素的大小派哲，來找到并記錄最小的那個元素的下標(biāo)，再與第一個元素交換抡秆。以此類推坊夫，找到第二小的元素的下標(biāo)逮壁，再與第二個元素交換村斟，直到全部遍歷完成奶陈。
-
插入排序也是一個時間復(fù)雜度平均為O(n^2)的算法。
1.png
排序時首先第一個元素不動蔚舀，因為我們認(rèn)為它已經(jīng)在正確的位置了饵沧。
接下來將第二位與第一位進行比較，如果比第一位小蝗敢，則將二者交換捷泞。
此時前兩位完成足删。
然后繼續(xù)將第三位與前一位比較寿谴，如果比前一位小，交換二者失受。
再將第二位與前一位比較讶泰，比前一位大則結(jié)束，進行下一個元素排序拂到，直到全部完成痪署。
插入排序相比選擇排序不同的是，第二層循環(huán)可以提前結(jié)束兄旬，即與前一位比較時狼犯，比前一位大，就說明此時元素已經(jīng)在正確的位置了领铐，直接進行下一個循環(huán)悯森。由于可以提前結(jié)束內(nèi)循環(huán)，所以在再好的情況下绪撵，插入排序的時間復(fù)雜度可以達(dá)到O(n)的級別瓢姻。
- 我們代碼測試一下。
首先我們定義可以一個生成隨機數(shù)數(shù)組的方法音诈。
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;
}
}
}
將兩個數(shù)組分別使用選擇排序和插入排序進行排序幻碱，并計算耗時绎狭。
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{
//提前結(jié)束，跳出循環(huán)
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);
一萬數(shù)量級打印的結(jié)果為：
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秒褥傍。
而在兩萬的量級時儡嘶，打印結(jié)果為：
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
此時相差了兩秒多。
- 而如果要排序的數(shù)組是近乎有序的數(shù)組時恍风，差別將更加明顯社付。
我們修改下上面的生成隨機數(shù)組的函數(shù)。將隨機數(shù)范圍修改到0~1
random = arc4random_uniform(2);
此時在兩萬數(shù)量級下邻耕，打印結(jié)果為：
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
