时间复杂度：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;
}
