三数取中值快排

//测试调用
    NSMutableArray *arr = [@[@"3", @"5", @"4", @"2", @"6"] mutableCopy];
    arr = [self quickSortWithArray:arr];
    NSLog(@"result = %@", arr);

/**
 * 方法名：QuickSort 说明：三数取中值快排 因为选第一个或者选最后一个可能会面对已经排好序的序列，那样会导致快排像冒泡一样
 * 时间复杂度是O(N^2) 三数取中值减少这种情况
 */
- (NSMutableArray *)quickSortWithArray:(NSMutableArray *)array {
    [self quickSortWithArray:array low:0 high:array.count - 1];
    return array;
}
- (void)quickSortWithArray:(NSMutableArray *)array low:(NSInteger)low high:(NSInteger)high {
    if (low < high) {
        NSInteger keyPos = [self partitionWithArray:array low:low high:high];
        [self quickSortWithArray:array low:low high:keyPos - 1];
        [self quickSortWithArray:array low:keyPos + 1 high:high];
    }
}
- (NSInteger)partitionWithArray:(NSMutableArray *)array low:(NSInteger)low high:(NSInteger)high {
    NSString *key = [self median3WithArray:array low:low high:high];
    while (low < high) {
        while (low < high && [array[high] compare:key] >= 0)
            --high;
        array[low] = array[high];
        while (low < high && [array[low] compare:key] <= 0)
            ++low;
        array[high] = array[low];
    }
    array[low] = key;
    return low;
}
- (NSString *)median3WithArray:(NSMutableArray *)array low:(NSInteger)low high:(NSInteger)high {
    NSInteger mid = (low + high) / 2;
    if ([array[low] compare:array[mid]] == NSOrderedDescending) {
        NSString *temp = array[low];
        array[low] = array[mid];
        array[mid] = temp;
    }
    if ([array[mid] compare:array[high]] == NSOrderedDescending) {
        NSString *temp = array[mid];
        array[mid] = array[high];
        array[high] = temp;
    }
    if ([array[low] compare:array[mid]] == NSOrderedDescending) {
        NSString *temp = array[low];
        array[low] = array[mid];
        array[mid] = temp;
    }
    NSString *tem = array[low];
    array[low] = array[mid];
    array[mid] = tem;
    return array[low];
}