時間復(fù)雜度：nlog(n)

//
//  main.m
//  Algorithms
//
//  Created by yuki on 2017/3/25.
//  Copyright ? 2017年 kang.yu.sh. All rights reserved.
//

#import <Foundation/Foundation.h>
static NSMutableArray *list;

void sumalute(NSInteger min,NSInteger max){
    if (max - min < 1) {//one element
        return;
    }
    
    NSInteger i = min;
    NSInteger j = max;
    NSNumber *target = list[min];
    for ( ; j >= min; j--) {
        NSNumber *after = list[j];
        if (after.integerValue > target.integerValue) {//?? small
            continue;
        }
        
        for (; i < j; i ++) {
            if (((NSNumber *)list[i]).integerValue > target.integerValue) {//?? big
                NSNumber *current = list[i];
                list[i] = list[j];
                list[j] = current;
                break;
            }
        }
        
        if (j == i) {
            NSNumber *current = list[min];
            list[min] = list[j];
            list[j] = current;
            NSLog(@"min>>: %ld, max>>: %ld, j>>: %ld" , min, max, j);
            NSLog(@"%@",list);
            break;
        }
    }
    
    sumalute(min, j-1);
    sumalute(j+1, max);
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        list = [NSMutableArray arrayWithObjects:@"4",@"5",@"6",@"5",@"8",@"7",@"3",@"2", nil];
        
        sumalute(0, list.count-1);
        
        NSLog(@"%@",list);
        
    }
    return 0;
}