算法(快排思想):求无序数组中的中位数
/**
求无序数组当中的中位数(快排思想,选中关键字,高低交替扫描)
示例:
[@"1",@"9",@"6",@"8",@"3",@"2"]
输出:
@"3"
*/
+ (void)findMedianValue {
NSMutableArray *array = [NSMutableArray arrayWithObjects:@"1",@"9",@"6",@"8",@"3",@"2", nil];
NSLog(@"输入数据:%@",array);
NSInteger low = 0;
NSInteger high = array.count - 1;
NSInteger mid = high/2;
NSInteger result = [self arraySort:array IndexStart:low IndexEnd:high];
while(result != mid) {
if (result < mid) {
result = [self arraySort:array IndexStart:result+1 IndexEnd:high];
}else {
result = [self arraySort:array IndexStart:low IndexEnd:result-1];
}
}
NSLog(@"中位数是:%@",array[mid]);
}
+ (NSInteger)arraySort:(NSMutableArray *)array IndexStart:(NSInteger)indexStart IndexEnd:(NSInteger)indexEnd {
NSInteger keyValue = [array[indexEnd] integerValue];
NSInteger lastEnd = indexEnd;
while (indexStart < indexEnd) {
while (indexStart < indexEnd && [array[indexStart] integerValue] <= keyValue) {
indexStart++;
}
while (indexStart < indexEnd && [array[indexEnd] integerValue] >= keyValue) {
indexEnd--;
}
if (indexStart < indexEnd) {
NSString *temp = array[indexStart];
array[indexStart] = array[indexEnd];
array[indexEnd] = temp;
}
}
NSString *temp = array[indexEnd];
array[indexEnd] = array[lastEnd];
array[lastEnd] = temp;
return indexStart;
}
运行: