iOS常见算法以及应用知识点总结
算法比较
关键词
- 二分
- 递归
- 分治
- 回溯
冒泡排序
思想:两次循环,外层进行循环次数的控制,内层循环,进行数据之间的比较,大的数据上浮(下沉)
#pragmamark-Objective-C //冒泡排序 -(void)bubbleSort:(id)array{ if(!([arrayisKindOfClass:[NSArrayclass]]||[arrayisKindOfClass:[NSMutableArrayclass]])){ NSLog(@"传入的参数不是数组类型"); return; } NSMutableArray*tmpArr; if([arrayisKindOfClass:[NSMutableArrayclass]]){ tmpArr=array; }else{ tmpArr=[arraymutableCopy]; } for(inti=0;iarr[j+1]){ swap(arr[j],arr[j+1]); } } } } voidswap(inti,intj){ i=i+j; j=i-j; i=i-j; }
快速排序
思想:(快速排序是基于一种叫做“二分”的思想)从数列中,挑选出一个元素作为基准,重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以放在任一边,在这个分区退出之后,该基准就处于数列的中间位置,递归的把小于基准值元素的子数列和大于基准值元素的子数列排序。
/** 快速排序 @paramarray任意类型 @paramlow需要排序的数组的开始位置 @paramhigh需要排序的数组的结束位置 */ -(void)quickSort:(NSMutableArray*)arraylow:(int)lowhigh:(int)high{ if(array==nil||array.count==0){ return; } if(low>=high){ return; } //取中值 intmiddle=low+(high-low)/2; NSNumber*prmt=array[middle]; inti=low; intj=high; //开始排序,使得leftprmt while(i<=j){ //while([array[i]compare:prmt]==NSOrderedAscending){ //i++; //} while([array[i]intValue]<[prmtintValue]){ i++; } //while([array[j]compare:prmt]==NSOrderedDescending) while([array[j]intValue]>[prmtintValue]){ j--; } if(i<=j){ [arrayexchangeObjectAtIndex:iwithObjectAtIndex:j]; i++; j--; } } if(low i){ [selfquickSort:arraylow:ihigh:high]; } } //快速排序 inta[101],n;//定义全局变量,这两个变量需要在子函数中使用 voidquicksort(intleft,intright) { inti,j,t,temp; if(left>right) return; temp=a[left];//temp中存的就是基准数 i=left; j=right; while(i!=j){ //顺序很重要,要先从右边开始找 while(a[j]>=temp&&i 选择排序
思想:首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾,以此类推,直到所有元素均排序完毕。
大专栏iOS常见算法以及应用s="line">6
-(void)selectSort:(NSMutableArray*)array { if(array==nil||array.count==0){ return; } intmin_index; for(inti=0;i插入排序
思想:从第一个元素开始,该元素可以认为已经被排序,取出下一个元素,在已经排序的元素序列中从后向前扫描,如果该元素(已排序)大于新元素,将该元素移到下一位置,重复以上步骤,直到找到已经排序的元素小于或者等于新元素的位置,将新元素插入到该位置中
-(void)inserSort:(NSMutableArray*)array { if(array==nil||array.count==0){ return; } for(inti=0;i=0&&[array[j]compare:temp]==NSOrderedDescending){ [arrayreplaceObjectAtIndex:j+1withObject:array[j]]; j--; } [arrayreplaceObjectAtIndex:j+1withObject:temp]; } } 希尔(Shell)排序
思想:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,在对全体进行一次直接插入排序。
优化:希尔排序是基于插入排序的以下两点性质而提出的改进方法的:
(1)插入排序在对几乎已经排好序的数据操作时,效率高,既可以达到线性排序的效率。
(2)但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位
OC代码实现:
//希尔排序,初始的dk值为array.count/2 -(void)ShellSort:(NSMutableArray*)arraydk:(int)dk { if(array==nil||array.count==0||dk>=array.count){ return; } for(inti=0;i=0&&[array[j]compare:temp]==NSOrderedDescending){ [arrayreplaceObjectAtIndex:j+dkwithObject:array[j]]; j-=dk; } [arrayreplaceObjectAtIndex:j+dkwithObject:temp]; } while(dk>=1){ dk=dk/2; [selfShellSort:arraydk:dk]; } } 实际应用
压缩图片
+(NSData*)compressImage:(UIImage*)imagetoByte:(NSUInteger)maxLength { //Compressbyquality CGFloatcompression=1; NSData*data=UIImageJPEGRepresentation(image,compression); if(data.lengthmaxLength){ max=compression; }else{ break; } } UIImage*resultImage=[UIImageimageWithData:data]; if(data.length maxLength&&data.length!=lastDataLength){ lastDataLength=data.length; CGFloatratio=(CGFloat)maxLength/data.length; CGSizesize=CGSizeMake((NSUInteger)(resultImage.size.width*sqrtf(ratio)), (NSUInteger)(resultImage.size.height*sqrtf(ratio)));//UseNSUIntegertopreventwhiteblank UIGraphicsBeginImageContext(size); [resultImagedrawInRect:CGRectMake(0,0,size.width,size.height)]; resultImage=UIGraphicsGetImageFromCurrentImageContext(); UIGraphicsEndImageContext(); data=UIImageJPEGRepresentation(resultImage,compression); } returndata; } +(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); }elseif(data.length>300*1024){//0.5M-1M data=UIImageJPEGRepresentation(image,0.8); } } returndata; } 以上就是本次介绍的全部知识点内容,感谢大家的学习和对毛票票的支持。