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

以上就是本次介绍的全部知识点内容，感谢大家的学习和对的支持。