iOS 开发中常用的排序算法
我们有许多的排序算法可以选择，冒泡、选择、快速、插入、希尔、归并、基数等，我今天来简单介绍一下不同算法的优缺点。
先普及一个概念：
算法稳定性：相同元素的前后顺序在任何情况都不会发生改变，这种排序成为稳定排序算法。反之成为不稳定排序算法。
冒泡排序
原理：重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
for(inti =0; i
时间复杂度：O(n^2)
算法稳定性：相同元素的前后顺序不会发生改变，所以冒泡排序是一种稳定排序算法。
选择排序
原理：它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
C语言实现选择排序
voidselect_sort(int*a,intn){registerinti,j,min,t;for(i=0;ia[j]) min=j;//交换if(min!=i) { t=a[min]; a[min]=a[i]; a[i]=t; } }}
时间复杂度：选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间
但是它是一种不稳定算法，相同元素的前后顺序有可能发生改变。
快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
一趟快速排序的算法是：
设置两个变量i、j，排序开始的时候：i=0，j=N-1；
以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
此时，一个数组分成两个小数组，一组所有的值都大于key，另一组都小于key。
然后进行递归操作，直到数组不能再分解为止（只有一个数据），才能得到正确结果。
代码实现：(递归的思想)
- (void)quickAscendingOrderSort:(NSMutableArray*)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right{if(left < right) {NSIntegertemp = [selfgetMiddleIndex:arr leftIndex:left rightIndex:right]; [selfquickAscendingOrderSort:arr leftIndex:left rightIndex:temp -1]; [selfquickAscendingOrderSort:arr leftIndex:temp +1rightIndex:right]; }}- (NSInteger)getMiddleIndex:(NSMutableArray*)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right{NSIntegertempValue = [arr[left] integerValue];while(left < right) {while(left < right && tempValue <= [arr[right] integerValue]) { right --; }if(left < right) { arr[left] = arr[right]; }while(left < right && [arr[left] integerValue] <= tempValue) { left ++; }if(left < right) { arr[right] = arr[left]; } } arr[left] = [NSNumbernumberWithInteger:tempValue];returnleft;}
快速排序也是一种不稳定排序算法。
插入排序
实现思路：
从第一个元素开始，认为该元素已经是排好序的。
取下一个元素，在已经排好序的元素序列中从后向前扫描。
如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
重复步骤3，直到已排好序的元素小于或等于新元素。
在当前位置插入新元素。
重复步骤2。
#pragma mark - 插入升序排序- (void)insertionAscendingOrderSort:(NSMutableArray*)ascendingArr{for(NSIntegeri =1; i < ascendingArr.count; i ++) {NSIntegertemp = [ascendingArr[i] integerValue];for(NSIntegerj = i -1; j >=0&& temp < [ascendingArr[j] integerValue]; j --) { ascendingArr[j +1] = ascendingArr[j]; ascendingArr[j] = [NSNumbernumberWithInteger:temp]; } }NSLog(@"插入升序排序结果：%@",ascendingArr);}
平均时间复杂度：O(n^2)
上面说了很多，都是我们用不到的，算法排序，可以拿过来了解一下算法实现。
下面提供几种常用的iOS排序方法：
NSComparator排序
升序：（降序只需要改变判断规则）
[arr sortUsingComparator:^NSComparisonResult(id_Nonnull obj1,id_Nonnull obj2) {NSIntegervalue1 = [obj1 integerValue];NSIntegervalue2 = [obj2 integerValue];if(value1 < value2) {returnNSOrderedAscending; }else{returnNSOrderedDescending; } }];NSLog(@"%@",arr);
好处：我们可以自己去写逻辑，控制输出我们想要的升序规则。
一般用在排序规则比较少见的情况。
NSDescriptor排序
sort descriptor可以很方便的对数组进行多个key的排序。比如要对数组的对象先做ID排序，然后在对content进行排序的话，可以写成：
NSSortDescriptor*firstDescriptor = [[NSSortDescriptoralloc] initWithKey:@"ID"ascending:YES];NSSortDescriptor*secondDescriptor = [[NSSortDescriptoralloc] initWithKey:@"content"ascending:YES];NSArray*sortArray = [NSArrayarrayWithObjects:firstDescriptor,secondDescriptor,nil];NSArray*sortedArray = [unSortedArray sortedArrayUsingDescriptors:sortArray];
作者：senpaiLi
链接：https://www.jianshu.com/p/97cdc7135773
