iOS常见算法以及应用知识点有哪些
算法比较
关键词
二分递归分治回溯
冒泡排序
思想：两次循环，外层进行循环次数的控制，内层循环，进行数据之间的比较，大的数据上浮（下沉）
#pragma mark - Objective-C//冒泡排序- (void)bubbleSort:(id)array{ if (!([array isKindOfClass:[NSArray class]] || [array isKindOfClass:[NSMutableArray class]])) { NSLog(@"传入的参数不是数组类型"); return; } NSMutableArray *tmpArr; if ([array isKindOfClass:[NSMutableArray class]]) { tmpArr = array; }else{ tmpArr = [array mutableCopy]; } for (int i = 0; i
快速排序
思想：（快速排序是基于一种叫做“二分”的思想）从数列中，挑选出一个元素作为基准，重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以放在任一边，在这个分区退出之后，该基准就处于数列的中间位置，递归的把小于基准值元素的子数列和大于基准值元素的子数列排序。
/** 快速排序 @param array 任意类型 @param low 需要排序的数组的开始位置 @param high 需要排序的数组的结束位置 */- (void)quickSort:(NSMutableArray*)array low:(int)low high:(int)high{ if (array == nil || array.count == 0) { return; } if (low >= high) { return; } //取中值 int middle = low + (high - low)/2; NSNumber *prmt = array[middle]; int i = low; int j = high; //开始排序，使得left 选择排序 思想：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾，以此类推，直到所有元素均排序完毕。 大专栏 iOS常见算法以及应用s="line">6 - (void)selectSort:(NSMutableArray *)array{ if(array == nil || array.count == 0){ return; } int min_index; for (int i = 0; i < array.count; i++) { min_index = i; for (int j = i + 1; j 插入排序 思想：从第一个元素开始，该元素可以认为已经被排序，取出下一个元素，在已经排序的元素序列中从后向前扫描，如果该元素（已排序）大于新元素，将该元素移到下一位置，重复以上步骤，直到找到已经排序的元素小于或者等于新元素的位置，将新元素插入到该位置中 - (void)inserSort:(NSMutableArray *)array{ if(array == nil || array.count == 0){ return; } for (int i = 0; i < array.count; i++) { NSNumber *temp = array[i]; int j = i-1; while (j >= 0 && [array[j] compare:temp] == NSOrderedDescending) { [array replaceObjectAtIndex:j+1 withObject:array[j]]; j--; } [array replaceObjectAtIndex:j+1 withObject:temp]; }} 希尔(Shell)排序 思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，在对全体进行一次直接插入排序。 优化：希尔排序是基于插入排序的以下两点性质而提出的改进方法的：（1）插入排序在对几乎已经排好序的数据操作时，效率高，既可以达到线性排序的效率。（2）但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位 OC代码实现： //希尔排序,初始的dk值为array.count/2- (void)ShellSort:(NSMutableArray *)array dk:(int)dk{ if(array == nil || array.count == 0||dk>=array.count){ return; } for (int i = 0; i < array.count; i ++) { NSNumber *temp = array[i]; int j = i - dk; //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入 while (j >= 0 && [array[j] compare:temp] == NSOrderedDescending) { [array replaceObjectAtIndex:j+dk withObject:array[j]]; j-=dk; } [array replaceObjectAtIndex:j+dk withObject:temp]; } while (dk>=1) { dk = dk/2; [self ShellSort:array dk:dk]; }} 实际应用 压缩图片 +(NSData *)compressImage:(UIImage *)image toByte:(NSUInteger)maxLength{ // Compress by quality CGFloat compression = 1; NSData *data = UIImageJPEGRepresentation(image, compression); if (data.length < maxLength) return data; //采用二分法提高性能 CGFloat max = 1; CGFloat min = 0; for (int i = 0; i < 6; ++i) { compression = (max + min) / 2; data = UIImageJPEGRepresentation(image, compression); if (data.length < maxLength * 0.9) { min = compression; } else if (data.length > maxLength) { max = compression; } else { break; } } UIImage *resultImage = [UIImage imageWithData:data]; if (data.length < maxLength) return data; // Compress by size NSUInteger lastDataLength = 0; while (data.length > maxLength && data.length != lastDataLength) { lastDataLength = data.length; CGFloat ratio = (CGFloat)maxLength / data.length; CGSize size = CGSizeMake((NSUInteger)(resultImage.size.width * sqrtf(ratio)), (NSUInteger)(resultImage.size.height * sqrtf(ratio))); // Use NSUInteger to prevent white blank UIGraphicsBeginImageContext(size); [resultImage drawInRect:CGRectMake(0, 0, size.width, size.height)]; resultImage = UIGraphicsGetImageFromCurrentImageContext(); UIGraphicsEndImageContext(); data = UIImageJPEGRepresentation(resultImage, compression); } return data;}+(NSData *)compressImage:(UIImage *)image{ NSData *data=UIImageJPEGRepresentation(image, 1.0); if (data.length>300*1024) { if (data.length>1024*1024) {//1M以及以上 data=UIImageJPEGRepresentation(image, 0.5); }else if (data.length>300*1024) {//0.5M-1M data=UIImageJPEGRepresentation(image, 0.8); } } return data;}
上一篇：Android怎么实现悬浮窗