生活木有捷徑

寫在前面

• 算法，對于iOS開發(fā)者來說，既熟悉又陌生。首先，在iOS開發(fā)過程中，對算法要求不高，用到算法時候也是少之甚少，除非是一些接近底層開發(fā)需要用到一些算法。但是，算法作為基礎，又是開發(fā)者的必備技能，尤其是求職面試中一項重要考察指標。
• 遂，筆者在此整理一下常用的算法，以供后用。

算法中的概念

• 排序算法穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。（算法的穩(wěn)定性與不穩(wěn)定性是可以相互轉化的）腦補一下
• 時間復雜度、空間復雜度，自行搜索，不再贅述。

需要講解的算法

• 冒泡排序算法
• 選擇排序算法
• 快速排序算法
• 歸并排序算法
• 翻轉二叉樹（遞歸實現）

冒泡排序算法

• 算法實現思想：
  1、比較相鄰的元素，若第一個比第二個大，就交換這兩個元素的位置；
  2、對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對，但除了最后一個元素；
  3、持續(xù)每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

• 時間復雜度：min = O(n),max =O(n^2);

• 算法穩(wěn)定性：穩(wěn)定，判斷標準：相同值的兩個元素不會更換位置；（將冒泡排序算法的穩(wěn)定性轉化為不穩(wěn)定性的方式：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、初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空；
  3、第1趟排序： 在無序區(qū)R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區(qū)的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€數增加1個的新有序區(qū)和記錄個數減少1個的新無序區(qū)；
  ...
  4、第i趟排序：第i趟排序開始時，當前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當前無序區(qū)中選出關鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個記錄R交換，使R[1..i]和R分別變?yōu)橛涗泜€數增加1個的新有序區(qū)和記錄個數減少1個的新無序區(qū)。

• 時間復雜度：min = O(n),max =O(n^2);

• 算法穩(wěn)定性：不穩(wěn)定；（不穩(wěn)定的原因舉例：5 5 3 變?yōu)?3 5 5，第一趟排序，第一個5會和3的位置互換，從而破壞該算法的穩(wěn)定性）

• 算法實現：（升序排序）

• 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-完成的時候，此時令循環(huán)結束）。

• 時間復雜度：max = O(n^2) 、 average = O(n*log2n)；

• 算法穩(wěn)定性：不穩(wěn)定；

• 算法實現 （升序排序）

• 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的值（如果第一次循環(huán)且key是
                             a[left]，那么就是給key）*/
        
        while (i < j && array[i] <= key) {/*這是i在當組內向前尋找，同上，不過注意與key的大小關系停止循環(huán)和上面相反，
                                           因為排序思想是把數往兩邊扔，所以左右兩邊的數大小與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、初始狀態(tài)：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)**;

• 算法穩(wěn)定性 ： 穩(wě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
/**
 *  左節(jié)點
 */
@property (nonatomic, strong) TreeNode *left;
/**
 *  右節(jié)點
 */
@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 更改翻轉二叉樹（遞歸實現)標題名寫錯；

寫到最后

• 以上內容，就是我對常用算法的簡單總結。大家如有其他意見歡迎評論。

傳送門

掃一掃下面的二維碼，歡迎關注我的個人微信公眾號攻城獅的動態(tài)（ID:iOSDevSkills），可在微信公眾號進行留言，更多精彩技術文章，期待您的加入！一起討論，一起成長！一起攻城獅！

公眾號