iOS 快速排序
核心代码
///=================快速排序
- (void)sort {
self.array = [NSMutableArray array];
for(inti =0; i <30; i++) {
intsum =arc4random()%20000000;
[self.array addObject:@(sum)];
}
NSLog(@"排序前 === %@",self.array);
[self sort:0 end:(int)self.array.count];
NSLog(@"排序后 === %@",self.array);
}
- (void)sort:(int)begin end:(int)end {
if(end - begin <2) {
return;
}
//确定轴点元素
int mid = [self pivotIndex:begin end:end];
//对子序列做快速排序
[self sort:begin end:mid];
[self sort:mid+1 end:end];
}
/// 确定轴点元素
/// @param begin 开始
/// @param end 结束
- (int)pivotIndex:(int)begin end:(int)end {
//备份begin位置的元素
id pivot = self.array[begin];
//end 指向最后一个元素
end--;
while(begin < end) {
while(begin < end) {
if([self cmp:pivot end:self.array[end]] <0) {//右边元素 > 轴点元素
end--;
}else{//右边元素 <= 轴点元素
self.array[begin++] = self.array[end];
break;
}
}
while(begin < end) {
if([self cmp:pivot end:self.array[begin]] >0) {//左边元素 < 轴点元素
begin++;
}else{
self.array[end--] = self.array[begin];
break;
}
}
}
//将轴点元素放入最终的位置
self.array[begin] = pivot;
//返回轴点元素的位置
return begin;
}
- (int)cmp:(id)first end:(id)second {
int one = [first intValue];
int two = [second intValue];
if(one > two) {
return 1;
}
if(one < two) {
return -1;
}
return 0;
}
