排序篇

基本排序

为了方便查找,通常希望查找对象是有序的,这里就简单说常见的排序算法:

插入排序
选择排序
快速排序

插入排序

插入排序核心思想就是将某一个数字插入到 已经排好顺序的数组中.注意这里插入进去的数组之前就是有序的.所以需要在刚开始时候就应该生成一个有序的数组,在之后将其他元素逐一插入.
为了保证之前的数组有序,通常从第二个元素进行插入.

代码:

OC 版:

- (void)insertSort:(NSMutableArray<NSNumber *> *)arr {
   int tmp = 0;
   for (int i = 1; i < arr.count; i ++) {
       tmp = [arr[i] intValue];
       if (arr[i] < arr[i - 1]) {
           int j = i - 1;
           for (; j >= 0; j --) {
               if ([arr[j] intValue] > tmp) {
                   arr[j + 1] = arr[j];
               }else{
                   break;
               }
           }
           arr[j + 1] = @(tmp);
       }   
   }
	}

swift版:

/// 插入排序 ; 保证已经插入数字的前面 是有序的
    func insertSort(_ arr : inout [Int]) {
        var minValue = 0
        for i in 1..<arr.count {
            if arr[i] < arr[i - 1] {
                minValue = arr[i]
                var j = i - 1;
                for _ in 0..<i {
                    /// 这里如果当前比较的数和上一个数小,就将上一个数赋值给这个数,在最后根据这个数的下标更改到临时值
                    if arr[j] > minValue {
                        arr[j + 1] = arr[j]
                    }else {
                        break;
                    }
                    j = j - 1
                }
                arr[j + 1] = minValue;
            }
            
        }
    }

注意点:
1. 外层循环控制循环轮数,由于是插入,所以外层循环从下标为1开始,一直到最后
2. 内层循环是控制当前元素将要插入到之前有序数组的什么位置.使用--进行处理,向前插入.
3. 在向前插入时候,只是将前面的大数赋值给后一位,进行循环.在内层循环结束后,需要将开始记录的临时值赋值给最后对应下标的值.
时间空间复杂度:
空间: 需要一个记录的辅助空间.
时间:
1. 当待排序为正序时候,比较次数达到最小值 n-1;
2. 当待排序为逆序时候,比较次数为(n - 1)(n - 1) / 2, 记录移动的次数 (n + 2)(n - 1) / 2.所以时间复杂度为O(n²).

选择排序

选择排序的核心思想是在一次循环中选择到值最小的下标值,在该次循环完成后更改对应下标的值.

代码

OC版

- (void)selectSort:(NSMutableArray<NSNumber *> *)arr {
   int minIndex = 0;
   NSNumber * tmp;
   for (int i = 0; i < arr.count - 2; i ++) {
       minIndex = i;
       for (int j = i + 1; j < arr.count; j ++) {
           if ([arr[j] intValue] < [arr[minIndex] intValue]) {
               minIndex = j;
           }
       }
       if (minIndex != i) { /// 交换值
           tmp = arr[minIndex];
           arr[minIndex] = arr[i];
           arr[i] = tmp;
       }
   }
}

swift版

/// 选择排序,针对下标的处理,只有数字后面的比前面的小时候才进行交换,不稳定的,有相同数字时候可能多次的相同数字位置不同
  func selectSort (_ arr : inout [Int]){
      var minIndex = 0; /// 定义最小值对应的下标
      for i in 0..<arr.count - 2{// 控制比较轮数,最后一个数不需要进行比较
          minIndex = i;
          for j in (i+1)..<arr.count{
              if arr[minIndex] > arr[j]{
                  minIndex = j;
              }
          }
          if minIndex != i {
              arr[minIndex] = arr[minIndex] + arr[i];
              arr[i] = arr[minIndex] - arr[i];
              arr[minIndex] = arr[minIndex] - arr[i];
          }
      }
      
  }

注意点:

相比插入排序,减少了移动次数需要在最后对需要更改的值进行赋值.
时间空间复杂度:
空间: 需要一个记录的辅助空间.
时间:
1. 当待排序为正序时候,比较次数达到最小值 n-1;
2. 当待排序为逆序时候,比较次数为(n - 2)(n - 2) / 2, 记录移动的次数 (n)(n - 1) / 2. 所以时间复杂度为O(n²).

快速排序

快速排序是核心思想是通过一次循环将待排序数组分成两个小数组,其中一个小数组中是均比关键字小,反之均大.之后递归直至将数组全部排完.

代码

OC版

	/// 快速排序
- (void)sortWithArr:(NSMutableArray<NSNumber *> *) arr first:(int)first last:(int)last {
    
    if ( first >= last) {
        return;
    }
    int low = first;
    int high = last;
    int key = [arr[first] intValue];
    
    while (low < high) {
        for (; ; high --) {
            if (low >= high) {
                break;
            }
            
            if ([arr[high] intValue] < key ) {
                
                NSNumber * highNum = arr[high];
                arr[low] = highNum;
                break;
            }
        }
        
        for (; ; low ++) {
            if (low >= high) {
                break;
            }
            if ([arr[low] intValue] > key ) {
                NSNumber * lowNum = arr[low];
                arr[high] = lowNum;
                break;
            }
        }
    }
    
    if (low == high) {
        arr[low] = @(key);
    }
    [self sortWithArr:arr first:first last:low - 1];
    [self sortWithArr:arr first:low + 1 last:last];
}

swift版

 func quickSort(_ arr : inout [Int],start : Int,end : Int) {
    if start >= end {
        return;
    }
    var low = start
    var high = end
    let key = arr[start]
    while low < high {
        for _ in 0..<high {
            if (low >= high){
                break;
            }
            if arr[high] < key {
                arr[low] = arr[high]
                break
            }
            high = high - 1
        }
        
        for _ in 0..<end {
            if (low >= high){
                break;
            }
            if arr[low] > key {
                arr[high] = arr[low]
                break
            }
            low = low + 1
        }
    }
    if low == high {
        arr[low] = key
    }
    quickSort(&arr, start: start, end: low - 1)
    quickSort(&arr, start: low + 1, end: end)
}

注意点:

这里使用递归处理数组,在开始时候必须做递归终结条件处理.

在while循环处理结束后,需要对碰撞处值进行处理.

时间空间复杂度:
空间: 需要O(log(n))的辅助存储空间,这里需要一个栈空间(递归导致)
时间: O(nlog(n))的平均时间,最坏情况下(逆序)O(n²)

查找篇

基本查找

排序的基本目的就是为了查找,这里先说二分查找:

二分查找(折半查找)
二分查找核心思想就是讲有序数组进行对半拆分,减小查找范围.

代码

swift版

/// 二分查找找

   func selectNum(_ arr : [Int],key : Int) -> Int? {
       var start = 0;
       var end = arr.count - 1;
       while start <= end {
           let middle = (start + end)>>1
           if arr[middle] > key{
               end = end - 1;
           }else if arr[middle] < key{
               start = start + 1;
           }else{
               return middle;
           }
       }
       return nil
   }

时间空间复杂度:
空间: 需要两个临时值
时间: O(log(n))的平均时间