美文网首页程序员iOS精选
iOS 开发中常用的排序算法

iOS 开发中常用的排序算法

作者: senpaiLi | 来源:发表于2018-11-29 15:33 被阅读9次

我们有许多的排序算法可以选择,冒泡、选择、快速、插入、希尔、归并、基数等,我今天来简单介绍一下不同算法的优缺点。

先普及一个概念:
算法稳定性:相同元素的前后顺序在任何情况都不会发生改变,这种排序成为稳定排序算法。反之成为不稳定排序算法

冒泡排序

原理:重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从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;
}

快速排序也是一种不稳定排序算法。

插入排序

实现思路:

  1. 从第一个元素开始,认为该元素已经是排好序的。
  2. 取下一个元素,在已经排好序的元素序列中从后向前扫描。
  3. 如果已经排好序的序列中元素大于新元素,则将该元素往右移动一个位置。
  4. 重复步骤3,直到已排好序的元素小于或等于新元素。
  5. 在当前位置插入新元素。
  6. 重复步骤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];

相关文章

  • iOS算法总结

    总结了下在iOS开发常用到的算法,不管是在面试中还是日常开发中,都会用到 1、冒泡排序冒泡算法是重复地走访过要排序...

  • 个人面试-计算机网络基本知识

    算法有几种 有多少种排序算法 iOS 开发中常用的排序(冒泡、选择、快速、插入、希尔、归并、基数)算法 什么是tc...

  • iOS开发-常用排序算法

    前言 常见的几种排序,针对不同数据,数据量,找到最合适的算法,是衡量一个程序员的基本标准,因此掏出小本子,又复习(...

  • iOS开发·必会的算法操作:字符串数组排序+模型对象数组排序

    iOS开发·必会的算法操作:字符串数组排序+模型对象数组排序

  • iOS 排序

    iOS开发中很少需要自己写排序的算法,因为苹果已经为我们封装好了。 简单的数值排序 复杂类型排序

  • iOS算法总结-堆排序

    iOS算法总结-堆排序 iOS算法总结-堆排序

  • iOS算法总结-冒泡排序

    iOS算法总结-冒泡排序 iOS算法总结-冒泡排序

  • iOS 排序(冒泡和选择)

    ♥️冒泡排序 ♥️选择排序 在iOS开发过程中,或者面试过程中,避免不了需要一些算法去解决问题,尤其是iOS面试中...

  • 排序算法

    文章序 排序算法作为算法的入门,也是在日常开发中十分常用的,故在此整理出十大排序算法,方便自己和需要的朋友查阅 先...

  • iOS 开发中常用的排序算法

    我们有许多的排序算法可以选择,冒泡、选择、快速、插入、希尔、归并、基数等,我今天来简单介绍一下不同算法的优缺点。 ...

网友评论

    本文标题:iOS 开发中常用的排序算法

    本文链接:https://www.haomeiwen.com/subject/juixcqtx.html