1-3 五大排序算法

冒泡排序 O(n^2)

    NSArray *arr = @[@(49),@(38),@(65),@(97),@(76),@(13),@(27),@(48)];
    NSMutableArray *mArr = [NSMutableArray arrayWithArray:arr];
    ///> 生序排序  大的在后面。大的往后面挪动 并不是和第一个比较大小
    ///> 每一次冒泡 都会把 最大的排在后面
    for (NSInteger i = 0; i < mArr.count; i++) {
        for (NSInteger j = 0; j < mArr.count - 1 - i; j++) {
            if (((NSNumber *)mArr[j]).integerValue > ((NSNumber *)mArr[j + 1]).integerValue) {
                [mArr exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
            }
        }        
    }
    NSLog(@"appDidEnterForeground1 %@",mArr);

快排 O(nlog n) 期望时间，O(n^2) 最坏情况

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归以此达到整个数据变成有序序列
    NSMutableArray *marr = @[@(29),@(23),@(54),@(3),@(34),@(4),@(34),@(54),@(24),@(40)].mutableCopy;
    
    [self fastSortingWith:marr left:0 right:marr.count - 1];
    
    NSLog(@"%@",marr);

///>. 第一次排序就将比我大的排后面。小的排前面 左右开弓。直到左面小与右面
- (void)fastSortingWith:(NSMutableArray *)arr left:(NSInteger)l right:(NSInteger)r {
    if (l >= r) {//如果数组长度为0或1时返回
        return;
    }
    NSInteger i = l;
    NSInteger j = r;
    NSInteger key = [arr[i] integerValue];
    while (i < j) {
        ///> 从右面查找。小的 交换到 i的位置     i做为交换位 NB
        while (i < j && [arr[j] integerValue] >=  key) {
            j--;
        }
        arr[i] = arr[j];
        
        ///> 从左面查找大 的交换位置 j
        while (i < j && [arr[i] integerValue] <=  key) {
            i++;
        }
        arr[j] = arr[i];
    }
    
    ///> 交换位 归位
    arr[i] = @(key);

    ///> 递归左面
    [self fastSortingWith:arr left:l right:i-1];
    ///> 递归右面
    [self fastSortingWith:arr left:i+1 right:r];
}

插入排序.插入到有序的数组中 O(n^2)

- (void)insertSort:(NSMutableArray *)array {
    
    for (NSInteger i = 1; i < array.count; i++) {
        
        NSInteger j = i;  //j是一个坑， 确定坑的位置，再把数从坑里取出来，注意顺序
        
        NSInteger temp = [array[i] integerValue];   //temp 是从坑里取数
        
        //把a[i]插入有序序列   因为已经排序好。所以直接找到对应的位置j就好
        while (j > 0 && temp < [array[j - 1] integerValue]) {    //j > 0 防止越界。写&&前面效率更高
            
            array[j] = array[j - 1];
            
            j--;
            
        }        
        array[j] = @(temp);
    }
}

选择排序 将最小的放到前面 O(n^2)

for (int i=0; i<arr_M.count; i++) {      
        for (int j=i+1; j<arr_M.count; j++) {         
            if (arr_M[i]<arr_M[j]) {            
                [arr_M exchangeObjectAtIndex:i withObjectAtIndex:j];              
            }            
        }    
    }

归并排序

分开 然后一个一个merge成一个新的数组

iOS开发-冒泡、快排、 插入排序、选择排序、及二分查找