iOS面试中常被问到的算法—排序算法

面试过程中常常被问到算法，为此特别整理一下以备不时之需。
一、冒泡排序

NSMutableArray *arr_M = [NSMutableArray arrayWithObjects:@1,@4,@2,@3,@5,nil];
   for (int i = 0; i < arr_M.count; ++i) {

        //遍历数组的每一个`索引`（不包括最后一个,因为比较的是j+1）
        for (int j = 0; j < arr_M.count-1; ++j) {

            //根据索引的`相邻两位`进行`比较`
            if (arr_M[j] < arr_M[j+1]) {

                [arr_M exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }

        }
    }

二、选择排序

+ (void)selectSort:(NSMutableArray *)array  
{  
    if(array == nil || array.count == 0){  
        return;  
    }  
      
    int min_index;  
    for (int i = 0; i < array.count; i++) {  
        min_index = i;  
        for (int j = i + 1; j<array.count; j++) {  
            if ([array[j] compare:array[min_index]] == NSOrderedAscending) {  
                [array exchangeObjectAtIndex:j withObjectAtIndex:min_index];  
            }  
              
            printf("排序中:");  
            [self printArray:array];  
        }  
    }  
}  

三、插入排序

+ (void)inserSort:(NSMutableArray *)array  
{  
    if(array == nil || array.count == 0){  
        return;  
    }  
      
    for (int i = 0; i < array.count; i++) {  
        NSNumber *temp = array[i];  
        int j = i-1;  
          
        while (j >= 0 && [array[j] compare:temp] == NSOrderedDescending) {  
            [array replaceObjectAtIndex:j+1 withObject:array[j]];  
            j--;  
              
            printf("排序中:");  
            [self printArray:array];  
        }  
          
        [array replaceObjectAtIndex:j+1 withObject:temp];  
    }  
}  

四、快速排序

+ (void)quickSort:(NSMutableArray *)array low:(int)low high:(int)high  
{  
    if(array == nil || array.count == 0){  
        return;  
    }  
    if (low >= high) {  
        return;  
    }  
      
    //取中值  
    int middle = low + (high - low)/2;  
    NSNumber *prmt = array[middle];  
    int i = low;  
    int j = high;  
      
    //开始排序，使得left<prmt 同时right>prmt  
    while (i <= j) {  
//        while ([array[i] compare:prmt] == NSOrderedAscending) {  该行与下一行作用相同  
        while ([array[i] intValue] < [prmt intValue]) {  
            i++;  
        }  
//        while ([array[j] compare:prmt] == NSOrderedDescending) { 该行与下一行作用相同  
        while ([array[j] intValue] > [prmt intValue]) {  
            j--;  
        }  
          
        if(i <= j){  
            [array exchangeObjectAtIndex:i withObjectAtIndex:j];  
            i++;  
            j--;  
        }  
          
        printf("排序中:");  
        [self printArray:array];  
    }  
      
    if (low < j) {  
        [self quickSort:array low:low high:j];  
    }  
    if (high > i) {  
        [self quickSort:array low:i high:high];  
    }  
}