常用算法

时间复杂度 VS 空间复杂度

一般最先接触的就是时间复杂度和空间复杂度的学习了，这两个概念以及如何计算，是必须学的，也是必须最先学的，主要有最大复杂度、平均复杂度等，直接通过博客搜索学习即可。

• 时间复杂度：是指执行这个算法所需要的计算工作量；
• 空间复杂度：是指执行这个算法所需要的内存空间；
  1、空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
  2、一个算法在计算机上占用的内存包括：程序代码所占用的空间、输入输出数据所占用的空间、辅助变量所占用的空间这三个方面。程序代码所占用的空间取决于算法本身的长短，输入输出数据所占用的空间取决于要解决的问题，是通过参数表调用函数传递而来，只有辅助变量是算法运行过程中临时占用的存储空间，与空间复杂度相关。
  3、通常来说，只要算法不涉及到动态分配的空间以及递归、栈所需的空间，空间复杂度通常为0(1)。
  4、算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数，与问题的规模没有关系。

1、排序算法
2、哈希表 （iOS底层很多用到了hash表）
3、列表、链表 （iOS底层很多用到了链表结构）
4、栈与队列

排序算法

1、冒泡排序
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序

+(NSMutableArray*)maopaoSort{
    NSMutableArray* orgArr = [NSMutableArray arrayWithArray: @[@(10),@(9),@(8),@(7),@(6),@(5),@(4),@(3),@(2),@(1)]];
    NSUInteger n = orgArr.count;
    for (NSInteger i = n-1; i>=0; i--) {
        //NSLog(@"+++++i:%ld-------------------",i);
        for (NSInteger j = 0; j<i; j++) {    // j<i  这里很重要
            //NSLog(@"-----j:%ld-------------------",j);
            NSInteger j1 = [orgArr[j] intValue];
            NSInteger j2 = [orgArr[j+1] intValue];
            if (j1>j2) {
                orgArr[j] = @(j2);
                orgArr[j+1] = @(j1);
            }
        }
    }
    return orgArr;
}

排序算法总结.png

引用文章：
iOS开发几大算法资料整理
十分钟搞定时间复杂度
最详细的解说—时间和空间复杂度

• 一个数组怎么取前k大的数；
• 排序算法的时间复杂度；
• 手写快速排序 。
• 给定50个已排序数组，每个里面200个数，找出其中最小的200个数（最优化）