简谈常用算法

2017-03-18 本文已影响587人 Jack_lin

生活木有捷径

写在前面

算法，对于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 更改翻转二叉树（递归实现)标题名写错；

写到最后

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

传送门

扫一扫下面的二维码，欢迎关注我的个人微信公众号攻城狮的动态（ID:iOSDevSkills），可在微信公众号进行留言，更多精彩技术文章，期待您的加入！一起讨论，一起成长！一起攻城狮！

公众号

简谈常用算法

写在前面

算法中的概念

需要讲解的算法

冒泡排序算法

选择排序算法

快速排序算法

归并排序算法

翻转二叉树（递归实现）算法

更改记录

写到最后

猜你喜欢

热点阅读