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(lowi){
[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.lengthmaxLength&&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;
}
以上就是本次介绍的全部知识点内容，感谢大家的学习和对毛票票的支持。