简谈常用算法

写在前面

  • 算法,对于iOS开发者来说,既熟悉又陌生。首先,在iOS开发过程中,对算法要求不高,用到算法时候也是少之甚少,除非是一些接近底层开发需要用到一些算法。但是,算法作为基础,又是开发者的必备技能,尤其是求职面试中一项重要考察指标。
  • 遂,笔者在此整理一下常用的算法,以供后用。

算法中的概念

  • 排序算法稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。(算法的稳定性与不稳定性是可以相互转化的)脑补一下
  • 时间复杂度、空间复杂度,自行搜索,不再赘述。

需要讲解的算法

  • 冒泡排序算法
  • 选择排序算法
  • 快速排序算法
  • 归并排序算法
  • 翻转二叉树(递归实现)
冒泡排序算法
  • 算法实现思想: 1、比较相邻的元素,若第一个比第二个大,就交换这两个元素的位置; 2、对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对,但除了最后一个元素; 3、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
  • 时间复杂度:min = O(n),max =O(n^2);
  • 算法稳定性:稳定,判断标准:相同值的两个元素不会更换位置;(将冒泡排序算法的稳定性转化为不稳定性的方式:array[j] < array[j+1]改为array[j] <= array[j+1]
  • 算法实现:(降序排序
  • C语言实现:
int algorithm(){
    int array[] = {24, 17, 85, 13, 9, 54, 76, 45, 5, 63};
    int count = sizeof(array)/sizeof(int);
    for (int i = 0; i < count - 1; i ++) {
      for (int j = 0; j < count - 1 - i; j ++) {
          if (array[j] < array[j+1]) {
            int temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
        }
     }
  }
    for (int index = 0; index < count; index ++) {
      printf("%d", array[index]);
    }
    return 0;
}
  • swift语言实现:
func testBubbling() {
    //冒泡排序
    var dataArray = [24, 17, 85, 13, 9, 54, 76, 45, 5, 63]
    let count = dataArray.count
    for i in 0..<count-1 {
      for j in 0..<count-1-i {
            print("i:\(i) j:\(j)")
        if dataArray[j] < dataArray[j+1] {
                let temp = dataArray[j]
                dataArray[j] = dataArray[j+1]
                dataArray[j+1] = temp
        }
      }
    }
      for index in 0..<count {
          print("result:\(dataArray[index])")
      }
  }
  • Objective-C语言实现:
  - (NSArray *)bubbleAlforithm:(NSArray *)array{
    NSMutableArray *dataArray = [NSMutableArray arrayWithArray:array];
    NSInteger count = dataArray.count;
    for (int i = 0; i < count - 1; i ++) {
        for (int j = 0; j < count - 1 - i; j ++) {
                if (dataArray[j] < dataArray[j + 1]) {
                    id temp = dataArray[j];
                    [dataArray replaceObjectAtIndex:j withObject:dataArray[j+1]];
                    [dataArray replaceObjectAtIndex:j+1 withObject:temp];
          }
      }
     }
    return dataArray;
  }
选择排序算法
  • 算法实现思想: 1、n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果: 2、初始状态:无序区为R[1..n],有序区为空; 3、第1趟排序: 在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区; ... 4、第i趟排序:第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
  • 时间复杂度:min = O(n),max =O(n^2);
  • 算法稳定性:不稳定;(不稳定的原因举例:5 5 3 变为 3 5 5,第一趟排序,第一个5会和3的位置互换,从而破坏该算法的稳定性)
  • 算法实现:(升序排序
  • C语言实现:
void selectAlgorithm(int array[]){
  int count = sizeof(array)/sizeof(int);
  int index;
  for (int i = 0; i < count - 1; i ++) {
      index = i;
      for (int j = i + 1; j < count; j ++) {
          if (array[index] > array[j]) {
          index = j;
      }
  }
  if (index != i) {
      int temp = array[i];
      array[i] = array[index];
      array[index] = temp;
    }
  }
}
  • swift语言实现:
func selectorMethods(array: [Int]) -> [Int] {
  var dataArray = array
  let count = dataArray.count
  var index: Int

  for i in 0..<count-1 {
      index = i
      for j in i+1..<count {
      if dataArray[index] > dataArray[j] {
          index = j
      }
  }

      if index != i {
        let temp = dataArray[i]
        dataArray[i] = dataArray[index]
        dataArray[index] = temp
     }
    }
  return dataArray
  }
  • OC语言实现:
- (NSArray *)selectAlgorithm:(NSArray *)array{
    NSMutableArray *tempArray = [NSMutableArray arrayWithArray:array];
    NSInteger count = tempArray.count;
    int index;
    for (int i = 0; i < count - 1; i ++) {
      index = i;
      for (int j = i + 1; j < count; j ++) {
          if (tempArray[index] > tempArray[j]) {
              index = j;
      }
    }

        if (index != i) {
              id temp = tempArray[i];
              [tempArray replaceObjectAtIndex:i withObject:tempArray[index]];
              [tempArray replaceObjectAtIndex:index withObject:temp];
      }
    }
  return tempArray;
}
快速排序算法
  • 算法实现思想: 1、设置两个变量i、j,排序开始的时候:i=0,j=N-1; 2、以第一个数组元素作为关键数据,赋值给key,即key=A[0]; 3、从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换; 4、从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换; 5、重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
  • 时间复杂度:max = O(n^2) 、 average = O(n*log2n);
  • 算法稳定性:不稳定;
  • 算法实现 (升序排序
  • C语言实现:
void algorithm(int *array, int left, int right){
    
    if (left >= right) {/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
        return ;
    }
    
    int i = left;
    int j = right;
    int key = array[left];
    
    while (i < j) { /*控制在当组内寻找一遍*/
        
        while (i < j && array[j] >= key) {/*而寻找结束的条件就是,1,找到一个小于或者大于key的数(大于或小于取决于你想升
                                           序还是降序)2,没有符合条件1的,并且i与j的大小没有反转*/
            j --;
        }
        array[i] = array[j];/*找到一个这样的数后就把它赋给前面的被拿走的i的值(如果第一次循环且key是
                             a[left],那么就是给key)*/
        
        while (i < j && array[i] <= key) {/*这是i在当组内向前寻找,同上,不过注意与key的大小关系停止循环和上面相反,
                                           因为排序思想是把数往两边扔,所以左右两边的数大小与key的关系相反*/
            i ++;
        }
        
        array[j] = array[i];
        
    }
    
    array[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
    //递归
    algorithm(array, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    algorithm(array, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
                                    /*当然最后可能会出现很多分左右,直到每一组的i = j 为止*/
}
  • Swift语言实现:
func fastAlgorithm(array:[Int], left:Int, right:Int) ->Void{
        
        if left >= right{
            return
        }
        var tempArray = array
        var i = left
        var j = right
        let key = tempArray[left]
        
        while(i < j){
            while(i < j && tempArray[j] >= key){
                j--
            }
            
            tempArray[i] = tempArray[j]
            
            while(i < j && tempArray[i] <= key){
                i++
            }
            tempArray[j] = tempArray[i]
        }
        
        tempArray[i] = key
        fastAlgorithm(tempArray, left: left, right: i - 1)
        fastAlgorithm(tempArray, left: i + 1, right: right)
    }
  • Objective-C语言实现:
- (void )fast:(NSArray *)array left:(int)left right:(int)right{
    
    if (left >= right) {
        return ;
    }
    
    NSMutableArray *tempArray = [NSMutableArray arrayWithArray:array];
    int i = left;
    int j = right;
    int key = [tempArray[left] intValue];
    
    while (i < j) {
        while (i < j && [tempArray[j] intValue] >= key) {
            j --;
        }
        tempArray[i] = tempArray[j];
        
        while (i < j && [tempArray[i] intValue] <= key) {
            i ++;
        }
        tempArray[j] = tempArray[i];
    }
    
    tempArray[i] = [NSNumber numberWithInt:key];
    
    [self fast:tempArray left:left right:i - 1];
    [self fast:tempArray left:i + 1 right:right];
    
}
归并排序算法
  • 算法实现思想: 1、申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列; 2、设定两个指针,最初位置分别为两个已经排序序列的起始位置; 3、比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置; 4、 重复步骤3直到某一指针超出序列尾; 5、将另一序列剩下的所有元素直接复制到合并序列尾。
  • 举例说明:假设存在数列:{4,189,80,290,35,8,2} 1、初始状态:4,189,80,290,35,8,2 2、第一次归并后:{4,189},{80,290},{35,8},{2} 比较次数:3 3、第二次归并后:{4,80,189,290},{2,8,35} 比较次数:4 4、第三次归并后:{2,4,8,35,80,189,290} 比较次数:4 5、总比较次数:3+4+4 = 11
  • 时间复杂度:** O(n log n)**;
  • 算法稳定性 : 稳定;
  • 算法实现:
  • C语言实现:
void Merge(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex){
    
    int i = startIndex;
    int j = midIndex + 1;
    int k = startIndex;
    while (i != midIndex && j != endIndex) {
        if (sourceArr[i] > sourceArr[j]) {
            tempArr[k++] = sourceArr[j ++];
        }else{
            tempArr[k++] = sourceArr[i ++];
        }
    }
    while (i != midIndex + 1) {
        tempArr[k++] = sourceArr[i++];
    }
    while (j != endIndex + 1) {
        tempArr[k ++] = sourceArr[j++];
    }
    for (i = startIndex; i < endIndex; i ++) {
        sourceArr[i] = tempArr[i];
    }
}

//recursion operation
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex){
    
    int midIndex;
    if (startIndex < endIndex) {
        midIndex = (startIndex + endIndex)/2;
        MergeSort(sourceArr, tempArr, startIndex, midIndex);
        MergeSort(sourceArr, tempArr, midIndex + 1, endIndex);
        Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
    }
}
  • Objective-C语言实现:
- (NSArray *)mergeWithArray:(NSArray *)sourceArray
            startIndex:(NSInteger)startIndex
              midIndex:(NSInteger)midIndex
              endIndex:(NSInteger)endIndex{
    NSMutableArray *sourceMutableArray = [NSMutableArray arrayWithArray:sourceArray];
    NSMutableArray *tempMutableArray = [[NSMutableArray alloc] init];
    
    NSInteger i = startIndex;
    NSInteger j = midIndex + 1;
    NSInteger k = startIndex;
    while (i != midIndex && j != endIndex){
        if (sourceMutableArray[i] > sourceMutableArray[j]) {
            //tempMutableArray[k] = sourceMutableArray[j];
            [tempMutableArray replaceObjectAtIndex:k withObject:sourceMutableArray[j]];
            k ++;
            j ++;
        }else{
            //tempMutableArray[k] = sourceMutableArray[i];
            [tempMutableArray replaceObjectAtIndex:k withObject:sourceMutableArray[i]];
            k ++;
            i ++;
        }
    }
    while (i != midIndex + 1) {
        [tempMutableArray replaceObjectAtIndex:k withObject:sourceMutableArray[i]];
        k ++;
        i ++;
    }
    while (j != endIndex + 1) {
        [tempMutableArray replaceObjectAtIndex:k withObject:sourceMutableArray[j]];
        k ++;
        j ++;
    }
    for (i = startIndex; i < endIndex; i ++) {
        [sourceMutableArray replaceObjectAtIndex:i withObject:tempMutableArray[i]];
    }
    return sourceMutableArray;
}

- (NSArray *)mergeSortWithArray:(NSArray *)sourceArray
                     startIndex:(NSInteger)startIndex
                       endIndex:(NSInteger)endIndex{
    if (startIndex < endIndex) {
        NSInteger midIndex = (startIndex + endIndex)/2;
        NSArray *tempArray =  [self mergeSortWithArray:sourceArray
                                            startIndex:startIndex
                                              endIndex:endIndex];
        NSArray *tempArray2 = [self mergeSortWithArray:tempArray
                                            startIndex:midIndex + 1
                                              endIndex:endIndex];
        return [self mergeWithArray:tempArray2
                         startIndex:startIndex
                           midIndex:midIndex
                           endIndex:endIndex];
       
    }
    return nil;
}
  • Swift语言实现:
     func mergeSort(array: [Int])-> [Int]{
        var helper = Array(count: array.count, repeatedValue: 0)
        var array = array
        mergeSort(&array, helper: &helper, low: 0, high: array.count - 1)
        return array
        
    }
    
    func mergeSort(inout array: [Int], inout helper:[Int], low: Int, high: Int){
        guard low < high else{
            return
        }
        let middle = (high + low)/2 + low
        mergeSort(&array, helper: &helper, low: low, high: middle)
        mergeSort(&array, helper: &helper, low: middle + 1, high: high)
        merge(&array, helper: &helper, low: low, middle: middle, high: high)
        
    }
    
    func merge(inout array: [Int], inout helper: [Int], low: Int, middle:Int, high:Int){
        for i in low...high{
            helper[i] = array[i]
        }
        
        var helperLeft = low
        var helpeRight = middle + 1
        var current = low
        
        while helperLeft <= middle && helpeRight <= high{
            if helperLeft <= helpeRight{
                array[current] = helper[helperLeft]
                helperLeft++
            }else{
                array[current] = helper[helpeRight]
                helpeRight++
            }
            current++
        }
        guard middle - helperLeft >= 0 else{
            return
        }
        for i in 0...middle - helperLeft{
            array[current+i] = helper[helperLeft + i]
        }
    }
翻转二叉树(递归实现)算法

算法实现(递归):

  • .h文件
@interface TreeNode : NSObject
/**
 *  左节点
 */
@property (nonatomic, strong) TreeNode *left;
/**
 *  右节点
 */
@property (nonatomic, strong) TreeNode *right;

@end

@class TreeNode;
@interface InvertTreeNode : NSObject

/**
 *  翻转二叉树算法
 *
 *  @param node 二叉树
 *
 *  @return 翻转后的二叉树
 */
- (TreeNode *)invertTree:(TreeNode *)node;

@end
  • .m文件
@implementation TreeNode
@end

@implementation InvertTreeNode

- (TreeNode *)invertTree:(TreeNode *)node{
    
    if (!node) {
        return nil;
    }
    
    node.left = [self invertTree:node.left];
    node.right = [self invertTree:node.right];
    
    TreeNode *temp = node.left;
    node.left = node.right;
    node.right = temp;
    
    return node;
}

@end

更改记录

  • 2017.3.21 更改翻转二叉树(递归实现)标题名写错;

写到最后

  • 以上内容,就是我对常用算法的简单总结。大家如有其他意见欢迎评论。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据学习笔记

Java程序设计(Java9版):第3章 流程控制

第3章 流程控制 学习要点 掌握三种流程控制 掌握简单的输入输出 了解三种循环设计方法 掌握数组、字符串和枚举类型 3.1 面向过程介绍...

3727
来自专栏zaking's

用js来实现那些数据结构05(栈02-栈的应用)

  上一篇文章我们一起实现了栈,那么这一篇文章我们一起来用栈解决问题。看看如何用栈来解决进制转换,平衡圆括号以及汉诺塔问题,使我们对栈有更为深入的理解。 1、进...

3237
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(11-15打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

1251
来自专栏java初学

top K 问题

48216
来自专栏SeanCheney的专栏

《Pandas Cookbook》第05章 布尔索引1. 计算布尔值统计信息2. 构建多个布尔条件3. 用布尔索引过滤4. 用标签索引代替布尔索引5. 用唯一和有序索引选取6. 观察股价7. 翻译SQ

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

2052
来自专栏Java开发者杂谈

遍历算法(1)

遍历算法主要用在在处理迷宫问题,图,最短路径,以及枚举所有可能等问题上。下面我们通过一个简单的例子,来入门深度优先和广度优先算法: 1 package co...

3786
来自专栏python3

python3--类的组合,初始类的继承

圆环是由两个圆组成的,圆环的面积是外面圆的面积减去内部圆的面积。圆环的周长是内部圆的周长加上外部圆的周长

1582
来自专栏ml

向前字典排序

          next_permutation算法对区间元素进行一次组合排序,使之字典顺序大于原来的排序,有如下两个使用原形,对迭代器区间[first,l...

2739
来自专栏Code_iOS

算法:冒泡排序

1、输入规模:count 【就是 n】 2、算法基本操作:if (compare(array, j + 1, j)) 【先有比较再有交换】 3、是否只...

2132
来自专栏小二的折腾日记

牛客网刷题总结-剑指offer(1)

这里一般的思路肯定是,从行或者列开始找,根据递增的顺序,找到行或者列之后再判断列或者行,知道找到为止。最好的方法是,从左下角或者右上角开始找。原因是:这样的一行...

1011

扫码关注云+社区

领取腾讯云代金券