iOS常见算法以及应用知识点总结

释放双眼,带上耳机,听听看~!

在本篇文章里小编给大家分享的是关于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<tmpArr.count; i++) {
for (int j = 0; j < tmpArr.count -1; j++) {
if ([tmpArr[j] compare:tmpArr[j+1]] == NSOrderedDescending) {
[tmpArr exchangeObjectAtIndex:i withObjectAtIndex:j+1];
}
}
}
NSLog(@"排序完的结果为:%@/n",tmpArr);
}
#pragma mark - C
//冒泡排序
void bubble_sort(int arr[], const int size){
for (int i = 0; i < size; i++) {
for (int j = 0; j<size -1 ; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);
}
}
}
}
void swap(int i,int j){
i = i + j;
j = i - j;
i = i - j;
}

快速排序

思想:(快速排序是基于一种叫做“二分”的思想)从数列中,挑选出一个元素作为基准,重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以放在任一边,在这个分区退出之后,该基准就处于数列的中间位置,递归的把小于基准值元素的子数列和大于基准值元素的子数列排序。

/**
快速排序
@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<prmt 同时right>prmt
while (i <= j) {
//    while ([array[i] compare:prmt] == NSOrderedAscending) {
//      i++;
//    }
while ([array[i] intValue] < [prmt intValue]) {
i++;
}
//    while ([array[j] compare:prmt] == NSOrderedDescending)
while ([array[j] intValue] > [prmt intValue]) {
j--;
}
if(i <= j){
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
i++;
j--;
}
}
if (low < j) {
[self quickSort:array low:low high:j];
}
if (high > i) {
[self quickSort:array low:i high:high];
}
}
//快速排序
int a[101],n;//定义全局变量,这两个变量需要在子函数中使用
void quicksort(int left,int right)
{
int i,j,t,temp;
if(left>right)
return;
temp=a[left]; //temp中存的就是基准数
i=left;
j=right;
while(i!=j){
//顺序很重要,要先从右边开始找
while(a[j]>=temp && i<j)
j--;
//再找右边的
while(a[i]<=temp && i<j)
i++;
//交换两个数在数组中的位置
if(i<j){
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//最终将基准数归位
a[left]=a[i];
a[i]=temp;
quicksort(left,i-1);//继续处理左边的,这里是一个递归的过程
quicksort(i+1,right);//继续处理右边的 ,这里是一个递归的过程
}

选择排序

思想:首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾,以此类推,直到所有元素均排序完毕。

大专栏 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<array.count; j++) {
if ([array[j] compare:array[min_index]] == NSOrderedAscending) {
[array exchangeObjectAtIndex:j withObjectAtIndex:min_index];
}
}
}
}

插入排序

思想:从第一个元素开始,该元素可以认为已经被排序,取出下一个元素,在已经排序的元素序列中从后向前扫描,如果该元素(已排序)大于新元素,将该元素移到下一位置,重复以上步骤,直到找到已经排序的元素小于或者等于新元素的位置,将新元素插入到该位置中

- (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;
}

 

为TA充电
共{{data.count}}人
人已赞赏
iOS文章

iOS中各种UI控件属性设置示例代码

2021-5-19 14:28:44

iOS文章

iOS开发平台调用后台接口的详解

2021-5-19 14:32:06

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索