八大排序算法
排序是个老生常谈的问题。好奇OC下各种排序功能的优劣，于是自己写了代码测试了下。
每次排序前生成新数组
数组求平均值：
NSArray *testArray = [NSArray arrayWithObjects:@"2.0", @"2.3", @"3.0", @"4.0", nil];
NSNumber *sum = [testArray valueForKeyPath:@"@sum.floatValue"];
NSNumber *avg = [testArray valueForKeyPath:@"@avg.floatValue"];
生成待排序数组 ：
-(void)getArray
{
_arrOrder=[NSMutableArray arrayWithCapacity:0];
NSInteger intTimes=0;
while (intTimes<5000)
{
[_arrOrder addObject:[NSNumber numberWithInteger:arc4random()%10000]];
//[_arrOrder addObject:[NSString stringWithFormat:@"%zd",arc4random()%10000]];
//若存字符串比存NSNumber排序耗时
intTimes++;
}
}
方法一：- (void)sortUsingComparator:(NSComparator NS_NOESCAPE)cmptr ;
[_arrOrder sortUsingComparator:^NSComparisonResult(id _Nonnull obj1, id _Nonnull obj2) {
if ([obj1 integerValue] < [obj2 integerValue])
{
return NSOrderedAscending;
}
else
{
return NSOrderedDescending;
}
}];
// 500个：0.000381,0.000360,0.000361,0.000309,0.000418,0.000398,0.000315,0.000466,0.000331,0.000318,平均值：0.000366
// 5000个：0.004227,0.003010,0.003172,0.003028,0.003118,0.003216,0.003757,0.003337,0.003364,0.003582,平均值：0.003381
// 50000个：0.042021,0.040707,0.047435,0.040408,0.041275,0.041389,0.040199,0.040472,0.040630,0.040379,平均值：0.041492
方法二：sortedArrayUsingSelector和sortedArrayUsingSelector排序
- (NSArray<ObjectType> *)sortedArrayUsingSelector:(SEL)comparator
[_arrOrder sortedArrayUsingSelector:@selector(compare:)];
//500个：0.000220,0.000299,0.000318,0.000259,0.000319,0.000263,0.000300,0.000353,0.000270,0.000497,平均值：0.000310
//5000个：0.002739,0.002559,0.002626,0.003347,0.002749,0.002546,0.002663,0.002718,0.002821,0.002630,平均值：0.002740
//50000个：0.033305,0.031930,0.031060,0.033721,0.036414,0.030785,0.033314,0.033470,0.032452,0.033425,平均值：0.032988
- (void)sortUsingSelector:(SEL)comparator
[_arrOrder sortUsingSelector:@selector(compare:)];
//500个：0.000304,0.000280,0.000559,0.000327,0.000413,0.000218,0.000382,0.000359,0.000276,0.000327,平均值：0.000345
//5000个：0.002569,0.003390,0.002718,0.002697,0.002800,0.002576,0.002800,0.002787,0.002583,0.002709,平均值：0.002763
//50000个：0.031858,0.032488,0.032914,0.032613,0.034166,0.032757,0.036731,0.032459,0.032640,0.032658,平均值：0.033128
sortUsingSelector是对可变数组直接排序，
sortedArrayUsingSelector则是将排序结果生成一个新的数组
方法三：- (void)sortWithOptions:(NSSortOptions)opts usingComparator:(NSComparator NS_NOESCAPE)cmptr排序 ，
NSSortOptions:NSSortConcurrent并发排序
[_arrOrder sortWithOptions:NSSortConcurrent usingComparator:^NSComparisonResult(id _Nonnull obj1, id _Nonnull obj2) {
if ([obj1 integerValue] < [obj2 integerValue])
{
return NSOrderedAscending;
}
else
{
return NSOrderedDescending;
}
}];
//500个：0.000278,0.000319,0.000290,0.000329,0.000401,0.000375,0.000313,0.000323,0.000342,0.000243,平均值：0.000321
//5000个：0.001739,0.002152,0.001907,0.002064,0.001664,0.001965,0.003030,0.002398,0.002034,0.001738,平均值：0.002069
//50000个：0.021747,0.021706,0.020331,0.021087,0.021828,0.021737,0.021627,0.022958,0.021629,0.023324,平均值：0.021797
NSSortOptions:NSSortStable 稳定排序
[_arrOrder sortWithOptions:NSSortStable usingComparator:^NSComparisonResult(id _Nonnull obj1, id _Nonnull obj2) {
if ([obj1 integerValue] < [obj2 integerValue])
{
return NSOrderedAscending;
}
else
{
return NSOrderedDescending;
}
}];
//500个：0.000264,0.000433,0.000365,0.000323,0.000425,0.000405,0.000402,0.000414,0.000311,0.000378,平均值：0.000372
//5000个：0.003025,0.003093,0.003118,0.003714,0.003136,0.004174,0.003129,0.003161,0.003151,0.004309,平均值：0.003401
//50000个：0.040789,0.040345,0.040546,0.042689,0.041075,0.040520,0.040579,0.041072,0.040587,0.040511,平均值：0.040871
数组排序中NSSortOptions两个参数详解（NSSortConcurrent、NSSortStable）
对于同一个数组第一次排序时系统会缓存排序的结果再次调用排序方法会调用缓存结果。
[_arrOrder sortUsingSelector:@selector(compare:)];
//5000个排序结果：第一次排序用时0.002985，后面四次排序：0.000744,0.000635,0.000692,0.000647
可以第一次排序用时教较长，再次排序则非常短；
方法四：冒泡排序
//冒泡排序
-(void)sortBubble
{
NSInteger count = [_arrOrder count];
for (int i = 0; i < count; i++)
{
for (int j = 0; j < count - i - 1; j++)
{
if([[_arrOrder objectAtIndex:j] integerValue] > [[_arrOrder objectAtIndex:j + 1] integerValue] )
{
[_arrOrder exchangeObjectAtIndex:j withObjectAtIndex:(j + 1)];
}
}
}
//500个：0.007532,0.007893,0.007341,0.009539,0.008324,0.007242,0.007290,0.007436,0.008467,0.007305,平均值：0.007837
//5000个：0.715326,0.711669,0.720526,0.715806,0.712150,0.714332,0.727436,0.712774,0.707690,0.714996,平均值：0.715271
//50000个：70.192044,72.187806,平均值：71.189925
}
方法五：插入排序
//插入排序
-(void)sortInsert
{
NSInteger count = [_arrOrder count];
for (NSInteger i = 1; i < count; i++)
{
NSInteger temp=[_arrOrder[i] intValue];
NSInteger j=i;
while (j > 0 && temp<[_arrOrder[j-1] intValue])
{
[_arrOrder exchangeObjectAtIndex:j withObjectAtIndex:j-1];
j--;
}
}
//500个：0.002372,0.002347,0.002602,0.002576,0.002208,0.002581,0.002558,0.002177,0.002283,0.002263,平均值：0.002397
//5000个：0.225729,0.201501,0.198318,0.223954,0.199238,0.198796,0.200308,0.197790,0.202265,0.206066,平均值：0.205397
//50000个：19.712748,20.270076,平均值：19.991412
}
//插入排序-希尔排序
-(void)sortShellInsert
{
NSInteger gap = _arrOrder.count / 2;
while (1 <= gap)
{
for (NSInteger i = gap; i < _arrOrder.count; i++)
{
NSInteger j = 0;
NSInteger temp = [_arrOrder[i] integerValue];
for (j = i - gap; j >= 0 && temp < [_arrOrder[j] integerValue]; j = j - gap)
{
[_arrOrder exchangeObjectAtIndex:j + gap withObjectAtIndex:j];
}
}
gap = gap / 2; // 减小增量
}
//500个：0.000541,0.000480,0.000757,0.000616,0.000526,0.000641,0.000553,0.000599,0.000505,0.000975,平均值：0.000619
//5000个：0.008002,0.005971,0.005979,0.006034,0.007360,0.005961,0.006008,0.006305,0.006331,0.006952,平均值：0.006490
//50000个：0.092619,0.091339,0.107534,0.096827,0.096549,0.088841,0.092913,0.092641,0.093957,0.094274,平均值：0.094749
}
方法六:选择排序
//选择排序
-(void)sortSelect
{
for (NSInteger i=0; i<_arrOrder.count-1; i++)
{
NSInteger intMin=i;
for (NSInteger j=i+1; j<_arrOrder.count; j++)
{
intMin=[_arrOrder[intMin] integerValue]>[_arrOrder[j] integerValue]?j:intMin;
}
if (intMin!=i)
{
[_arrOrder exchangeObjectAtIndex:i withObjectAtIndex:intMin];
}
}
//500个：0.007415,0.007749,0.008564,0.009378,0.007826,0.009144,0.007637,0.008565,0.007747,0.009345,平均值：0.008337
//5000个：0.752760,0.748053,0.769431,0.774992,0.795343,0.748039,0.747646,0.750589,0.787549,0.757852,平均值：0.763225
//50000个：77.661581,76.398291,平均值：77.029936
}
//选择排序-二元选择排序
-(void)sortSelectTwo
{
for (NSInteger i=0; i<_arrOrder.count/2; i++)
{
NSInteger intMin=i;
NSInteger intMax=i;
for (NSInteger j=i+1; j<_arrOrder.count-i; j++)
{
if ([_arrOrder[intMin] integerValue]>[_arrOrder[j] integerValue])
{
intMin=j;
continue;
}
if ([_arrOrder[intMax] integerValue]<[_arrOrder[j] integerValue])
{
intMax=j;
}
}
if (intMin!=i)
{
[_arrOrder exchangeObjectAtIndex:i withObjectAtIndex:intMin];
if (intMax==i)
{
intMax=intMin;
}
}
if (intMax!=i)
{
[_arrOrder exchangeObjectAtIndex:_arrOrder.count-i-1 withObjectAtIndex:intMax];
}
else
{
[_arrOrder exchangeObjectAtIndex:intMax withObjectAtIndex:_arrOrder.count-i-1];
}
}
//500个：.007438,0.007496,0.007218,0.007421,0.007520,0.008727,0.007429,0.009546,0.007673,0.007514,平均值：0.007798
//5000个：0.748539,0.763340,0.735187,0.736641,0.729803,0.747142,0.729810,0.751240,0.747948,0.745442,平均值：0.743509
//50000个：79.616967,81.923435,平均值：80.770201
}
方法七：快速排序
//快速排序
-(void)sort:(NSMutableArray *)arr left:(NSUInteger)left right:(NSUInteger)right
{
if(left>=right)
{
return;
}
NSUInteger i=left ,j=right;
NSInteger x=[arr[i] integerValue];
while (i<j)
{
while(i < j && [arr[j] integerValue] >= x) // 从右向左找第一个小于x的数
{
j--;
}
if(i < j)
{
[arr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
while(i < j && [arr[i] integerValue] < x) // 从左向右找第一个大于等于x的数
{
i++;
}
if(i < j)
{
[arr exchangeObjectAtIndex:j withObjectAtIndex:i];
}
}
[self sort:arr left:left right:j ];
[self sort:arr left:i+1 right:right ];
//500个：0.000451,0.000576,0.000595,0.000554,0.000434,0.000446,0.000456,0.000580,0.000519,0.000477,平均值：0.000509
//5000个：0.004278,0.005009,0.004109,0.004348,0.005379,0.004299,0.004206,0.004302,0.004918,0.004048,平均值：0.004490
//50000个：0.053343,0.052303,0.056789,0.053971,0.052194,0.056028,0.056682,0.053735,0.051138,0.053816,平均值：0.054000
}
测试环境：Mac mini Intel Core i5 2.6 GHz Xcode8 iOS7模拟器
| 方法 | 500个平均用时(秒) | 5000个平均用时(秒) | 50000个平均用时(秒) |
|---|---|---|---|
| sortUsingComparator | 0.000366 | 0.003381 | 0.041492 |
| sortedArrayUsingSelector | 0.000310 | 0.002740 | 0.032988 |
| sortUsingSelector | 0.000345 | 0.002763 | 0.033128 |
| sortWithOptions:NSSortConcurrent | 0.000321 | 0.002069 | 0.021797 |
| sortWithOptions:NSSortStable | 0.000372 | 0.003401 | 0.040871 |
| 冒泡排序 | 0.007837 | 0.715271 | 71.189925 |
| 插入排序 | 0.002397 | 0.205397 | 19.991412 |
| 插入排序-希尔排序 | 0.000619 | 0.006490 | 0.094749 |
| 选择排序 | 0.008337 | 0.763225 | 77.029936 |
| 选择排序-二元选择排序 | 0.007798 | 0.743509 | 80.770201 |
| 快速排序 | 0.000509 | 0.004490 | 0.054000 |
