iOS 算法之排序、查找、递归
排序
- 冒泡排序(依次循环旁边的比较放到后边去)
/** 最好时间复杂度是O(n) 最坏时间复杂度是O(n^2) 平均时间复杂度:O(n^2) 平均空间复杂度:O(1) */ - (void)foolSortArray:(NSMutableArray *)array { for (int i = 0; i < array.count-1; i++) { for (int j = 0; j < array.count-i-1; j++) { if (array[j] > array[j+1]) { id tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; } } } }
- 选择排序(拿前边的和后边的依次比较放到前边去,就是先排好前边的)
/** 最好时间复杂度是O(n^2) 最坏时间复杂度是O(n^2) 平均时间复杂度:O(n^2) 平均空间复杂度:O(1) */ - (void)selectSortArray:(NSMutableArray *)array { for (int i = 0; i < array.count-1; i++) { for (int j = i+1; j < array.count; j++) { if (array[i] > array[j]) { id tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } } }
- 插入排序
- (void)insertSortArray:(NSMutableArray *)array { for (int i = 1; i < [array count]; i++) { int j = i; NSInteger temp = [[array objectAtIndex:i] integerValue]; while (j > 0 && temp < [[array objectAtIndex:j - 1] integerValue]) { [array replaceObjectAtIndex:j withObject:[array objectAtIndex:(j - 1)]]; j--; } [array replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]]; } }
- 希尔排序
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。`
增量: 插入排序只能与相邻的元素进行比较,而希尔排序则是进行跳跃比较,而增量就是步长。
/** 最优的增量在最坏的情况下却为O(n²⁄³),最坏的情况下时间复杂度仍为O(n²) 需要注意的是,增量序列的最后一个增量值必须等于1才行 另外由于记录是跳跃式的移动,希尔排序并不是一种稳定的排序算法 */ - (void)shellSortArray:(NSMutableArray *)array { int count = (int)array.count; // 初始增量为数组长度的一半,然后每次除以2取整 for (int increment = count/2; increment > 0; increment/=2) { // 初始下标设为第一个增量的位置,然后递增 for (int i = increment; i<count; i++) { // 获取当前位置 int j = i; // 然后将此位置之前的元素,按照增量进行跳跃式比较 while (j-increment>=0 && [array[j] integerValue]<[array[j-increment] integerValue]) { [array exchangeObjectAtIndex:j withObjectAtIndex:j-increment]; j-=increment; } } } }
- 快速排序
/** 最理想情况算法时间复杂度O(nlogn),最坏O(n^2),平均O(nlogn) 平均空间复杂度:O(nlogn) O(nlogn)~O(n^2) */ - (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex { if (leftIndex >= rightIndex) { // 如果数组长度为0或1时返回 return ; } NSInteger i = leftIndex; NSInteger j = rightIndex; NSInteger key = [array[i] integerValue]; // 记录比较基准数 while (i < j) { /**** 首先从右边j开始查找比基准数小的值 ***/ while (i < j && [array[j] integerValue] >= key) { // 如果比基准数大,继续查找 j--; } // 如果比基准数小,则将查找到的小值调换到i的位置 array[i] = array[j]; /**** 当在右边查找到一个比基准数小的值时,就从i开始往后找比基准数大的值 ***/ while (i < j && [array[i] integerValue] <= key) { // 如果比基准数小,继续查找 i++; } // 如果比基准数大,则将查找到的大值调换到j的位置 array[j] = array[i]; } // 将基准数放到正确位置 array[i] = @(key); /**** 递归排序 ***/ // 排序基准数左边的 [self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1]; // 排序基准数右边的 [self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex]; }
- 堆排序
堆
堆(英语:heap)是计算机科学中一类特殊的数据结构的统称
堆总是满足下列性质: 1. 堆中某个节点的值总是不大于或不小于其父节点的值; 2. 堆总是一棵完全二叉树
将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆
完全二叉树
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
/** 时间复杂度为O(nlogn) */ - (void)heapSortArray:(NSMutableArray *)heapList len:(NSInteger)len { // 建立堆,从最底层的父节点开始 for(NSInteger i = (heapList.count/2 -1); i>=0; i--) [self adjustHeap:heapList location:i len:heapList.count]; for(NSInteger i = heapList.count -1; i >= 0; i--){ NSInteger maxEle = ((NSString *)heapList[0]).integerValue; heapList[0] = heapList[i]; heapList[i] = @(maxEle).stringValue; [self adjustHeap:heapList location:0 len:i]; } } - (void)adjustHeap:(NSMutableArray *)heapList location:(NSInteger)p len:(NSInteger)len { NSInteger curParent = ((NSString *)heapList[p]).integerValue; NSInteger child = 2*p + 1; while (child < len) { // left < right if (child+1 < len && ((NSString *)heapList[child]).integerValue < ((NSString *)heapList[child+1]).integerValue) { child ++; } if (curParent < ((NSString *)heapList[child]).integerValue) { heapList[p] = heapList[child]; p = child; child = 2*p + 1; } else break; } heapList[p] = @(curParent).stringValue; }
- 归并排序
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
/** 时间复杂度为O(nlogn) (1)“分解”——将序列每次折半划分 (2)“合并”——将划分后的序列段两两合并后排序 */ - (NSArray *)mergeSortArray:(NSMutableArray *)array { // 排序数组 NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1]; // 第一趟排序是的子数组个数为ascendingArr.count for (NSNumber *num in array) { NSMutableArray *subArray = [NSMutableArray array]; [subArray addObject:num]; [tempArray addObject:subArray]; } /** 分解操作 每一次归并操作 当数组个数为偶数时tempArray.count/2; 当数组个数为奇数时tempArray.count/2+1; 当tempArray.count == 1时,归并排序完成 */ while (tempArray.count != 1) { NSInteger i = 0; // 当数组个数为偶数时 进行合并操作, 当数组个数为奇数时,最后一位轮空 while (i < tempArray.count - 1) { // 将i 与i+1 进行合并操作 将合并结果放入i位置上 将i+1位置上的元素删除 tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]]; [tempArray removeObjectAtIndex:i + 1]; // i++ 继续下一循环的合并操作 i++; } } return tempArray.copy; } // 合并 - (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 { // 合并序列数组 NSMutableArray *resultArray = [NSMutableArray array]; // firstIndex是第一段序列的下标 secondIndex是第二段序列的下标 NSInteger firstIndex = 0, secondIndex = 0; // 扫描第一段和第二段序列,直到有一个扫描结束 while (firstIndex < array1.count && secondIndex < array2.count) { // 判断第一段和第二段取出的数哪个更小,将其存入合并序列,并继续向下扫描 if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) { [resultArray addObject:array1[firstIndex]]; firstIndex++; } else { [resultArray addObject:array2[secondIndex]]; secondIndex++; } } // 若第一段序列还没扫描完,将其全部复制到合并序列 while (firstIndex < array1.count) { [resultArray addObject:array1[firstIndex]]; firstIndex++; } // 若第二段序列还没扫描完,将其全部复制到合并序列 while (secondIndex < array2.count) { [resultArray addObject:array2[secondIndex]]; secondIndex++; } // 返回合并序列数组 return resultArray.copy; }
二分查找
/** 二分查找法只适用于已经排好序的查找 */ - (NSInteger)dichotomySearch:(NSArray *)array target:(id)key { NSInteger left = 0; NSInteger right = [array count] - 1; NSInteger middle = [array count] / 2; while (right >= left) { middle = (right + left) / 2; if (array[middle] == key) { return middle; } if (array[middle] > key) { right = middle - 1; }else if (array[middle] < key) { left = middle + 1; } } return -1; }
递归
- 斐波那契数列问题
- (NSInteger)recursion0:(NSInteger) n { if (n <= 1) return n; return [self recursion0:n-1] + [self recursion0:n-2]; }
- 阶乘
- (NSInteger)recursion1: (NSInteger)n { if (n == 0) { //递归边界 return 1; } return n*[self recursion1:(n-1)];//递归公式 }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
iOS应用签名(上)
关于iOS应用签名我想一起探讨一下它的原理.首先我们需要了解一个东西,叫做数字签名 数字签名(digitally signed) 名词解释:为什么用签名这个词.因为老外喜欢用支票,支票上面的签名能够证明这玩意是你的.那么数字签名顾名思义,就是用于鉴别数字信息的方法. 接下来我们思考一下.想要证明数字信息(也就是二进制数据,计算机里面的任意数据)的有效性,那么使用什么方式最合适呢?我们可以想到有"信息指纹"之称的HASH算法,在之前的文章中有讲到HASH算法专门用来做文件数据的识别.那么在网络数据传递的过程中,我们可以将明文数据,和数据的HASH值一起传递给对方.对方可以拿出HASH值来进行验证.但是在这个过程中,如何做到数据的保护呢?明文数据和HASH值如果直接传递就有都被篡改的风险.所以这里我们要对数据进行加密.明文数据有时会比较大,不适合使用RSA非对称加密算法,那么数据的HASH值是比较小的.这个数据是用于校验的,它完全可以使用RSA来加密.所以在数据传递的时候,我们将明文数据加上通过RSA加密的校验数据一并传递给对方.那么这个通过RSA加密的校验数据,我们称之为签名. 数字签名...
- 下一篇
Android进阶知识:事件分发与滑动冲突(二)
接着看代码块3,在这段很长的代码里,首先一个if中判断了该事件是否满足没有被拦截和被取消,之后第二个if判断了事件类型是否为DOWN,满足了没有被拦截和取消的DOWN事件,接下来ViewGroup才会循环其子View找到点击事件在其内部并且能够接受该事件的子View,再通过调用dispatchTransformedTouchEvent方法将事件分发给该子View处理,返回true说明子View成功消费事件,于是调用addTouchTarget方法,方法中通过TouchTarget.obtain方法获得一个包含这View的TouchTarget节点并将其添加到链表头,并将已经分发的标记设置为true。 接下来看代码块4: // Dispatch to touch targets.//走到这里说明在循环遍历所有子View后没有找到接受该
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- 设置Eclipse缩进为4个空格,增强代码规范
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS8编译安装MySQL8.0.19
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- CentOS6,CentOS7官方镜像安装Oracle11G
- Windows10,CentOS7,CentOS8安装Nodejs环境
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2配置默认Tomcat设置,开启更多高级功能