快速排序应该是应用最广泛的算法，流行的原因主要是因为实现简单，适用于不同的输入数据且在一般应用中比其他算法都快的多，其实跟上篇文章中的归并排序差不多类似，主要是通过分治思想，将数组不断的切割，最后求解。不过两者不同的是归并排序是在递归之后进行比较，也就是说递归之前左右两边的数据是无序的，快速排序是在递归之前先将数组进行排序，就是递归之前的左右两边的数组都是有序的，时间复杂度为O(nlogn).
快排递归代码:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
-(
void
)quickSort:(
NSMutableArray
*)arr lowIndex:(
NSInteger
)low highIndex:(
NSInteger
)high{
if
(low>=high) {
return
;
}
NSInteger
j=[
self
partiticon:arr lowIndex:low highIndex:high];
//获取切割位置
[
self
quickSort:arr lowIndex:low highIndex:j-1];
//左边排序数组arr[low..j-1]
[
self
quickSort:arr lowIndex:j+1 highIndex:high];
}
-(
NSInteger
)partiticon:(
NSMutableArray
*)arr lowIndex:(
NSInteger
)low highIndex:(
NSInteger
)high{
//将数组分为arr[low..i-1] arr[i],arr[i+1..high]
NSInteger
i=low,j=high+1;
//左右扫描指针
NSInteger
compareValue=[[arr objectAtIndex:low] integerValue];
//最开始的比较值
while
(
true
) {
//扫描左右，检查是否需要交换数据
while
([arr[++i] integerValue]<compareValue) {
if
(i==high) {
break
;
}
}
while
([arr[--j] integerValue]>compareValue) {
if
(j==low) {
break
;
}
}
if
(i>=j) {
break
;
}
NSString
*temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
NSString
*lowTemp=arr[low];
arr[low]=arr[j];
arr[j]=lowTemp;
return
j;
//返回具体的比较位置，左边都不大于arr[j]，右边都不小于arr[j]
}
|
测试代码:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
MySort *sort=[[MySort alloc]init];
NSMutableArray
*arr=[[
NSMutableArray
alloc]initWithCapacity:10];
[arr addObject:@
"1"
];
[arr addObject:@
"3"
];
[arr addObject:@
"8"
];
[arr addObject:@
"12"
];
[arr addObject:@
"18"
];
[arr addObject:@
"1"
];
[arr addObject:@
"10"
];
[arr addObject:@
"4"
];
[arr addObject:@
"25"
];
[arr addObject:@
"2"
];
[sort quickSort:arr lowIndex:0 highIndex:arr.count-1];
for
(
NSInteger
i=0; i<[arr count]; i++) {
NSLog
(@
"数值:%@"
,arr[i]);
}
NSLog
(@
"iOS技术交流群:228407086"
);
NSLog
(@
"原文地址:http://www.cnblogs.com/xiaofeixiang"
);
|
测试效果:
本文转自Fly_Elephant博客园博客，原文链接：http://www.cnblogs.com/xiaofeixiang/p/4591206.html，如需转载请自行联系原作者
