我们有许多的排序算法可以选择，冒泡、选择、快速、插入、希尔、归并、基数等，我今天来简单介绍一下不同算法的优缺点。
先普及一个概念：
算法稳定性：相同元素的前后顺序在任何情况都不会发生改变，这种排序成为稳定排序算法。反之成为不稳定排序算法。
冒泡排序
原理：重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
for (int i = 0; i<result.count-1; i++) {
for (int j = 0; j<result.count-1-i; j++) {
NSInteger left = [result[j] integerValue];
NSInteger right = [result[j+1] integerValue];
if (left<right) {
[result exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"%@",result);
时间复杂度：O(n^2)
算法稳定性：相同元素的前后顺序不会发生改变，所以冒泡排序是一种稳定排序算法。
选择排序
原理：它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
C语言实现选择排序
void select_sort(int*a,int n)
{
register int i,j,min,t;
for(i=0;i<n-1;i++)
{
min=i;//查找最小值
for(j=i+1;j<n;j++)
if(a[min]>a[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) {
NSInteger temp = [self getMiddleIndex:arr leftIndex:left rightIndex:right];
[self quickAscendingOrderSort:arr leftIndex:left rightIndex:temp - 1];
[self quickAscendingOrderSort:arr leftIndex:temp + 1 rightIndex:right];
}
}
- (NSInteger)getMiddleIndex:(NSMutableArray *)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right
{
NSInteger tempValue = [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] = [NSNumber numberWithInteger:tempValue];
return left;
}
快速排序也是一种不稳定排序算法。
插入排序
实现思路：
- 从第一个元素开始，认为该元素已经是排好序的。
- 取下一个元素，在已经排好序的元素序列中从后向前扫描。
- 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
- 重复步骤3，直到已排好序的元素小于或等于新元素。
- 在当前位置插入新元素。
- 重复步骤2。
#pragma mark - 插入升序排序
- (void)insertionAscendingOrderSort:(NSMutableArray *)ascendingArr
{
for (NSInteger i = 1; i < ascendingArr.count; i ++) {
NSInteger temp = [ascendingArr[i] integerValue];
for (NSInteger j = i - 1; j >= 0 && temp < [ascendingArr[j] integerValue]; j --) {
ascendingArr[j + 1] = ascendingArr[j];
ascendingArr[j] = [NSNumber numberWithInteger:temp];
}
}
NSLog(@"插入升序排序结果：%@",ascendingArr);
}
平均时间复杂度：O(n^2)
上面说了很多，都是我们用不到的，算法排序，可以拿过来了解一下算法实现。
下面提供几种常用的iOS排序方法：
NSComparator排序
升序：（降序只需要改变判断规则）
[arr sortUsingComparator:^NSComparisonResult(id _Nonnull obj1, id _Nonnull obj2) {
NSInteger value1 = [obj1 integerValue];
NSInteger value2 = [obj2 integerValue];
if (value1 < value2) {
return NSOrderedAscending;
}else{
return NSOrderedDescending;
}
}];
NSLog(@"%@",arr);
好处：我们可以自己去写逻辑，控制输出我们想要的升序规则。
一般用在排序规则比较少见的情况。
NSDescriptor排序
sort descriptor可以很方便的对数组进行多个key的排序。比如要对数组的对象先做ID排序，然后在对content进行排序的话，可以写成：
NSSortDescriptor *firstDescriptor = [[NSSortDescriptor alloc] initWithKey:@"ID" ascending:YES];
NSSortDescriptor *secondDescriptor = [[NSSortDescriptor alloc] initWithKey:@"content" ascending:YES];
NSArray *sortArray = [NSArray arrayWithObjects:firstDescriptor,secondDescriptor,nil];
NSArray *sortedArray = [unSortedArray sortedArrayUsingDescriptors:sortArray];
