算法-快速排序-白红宇

快速排序应该是应用最广泛的算法，流行的原因主要是因为实现简单，适用于不同的输入数据且在一般应用中比其他算法都快的多，其实跟上篇文章中的归并排序差不多类似，主要是通过分治思想，将数组不断的切割，最后求解。不过两者不同的是归并排序是在递归之后进行比较，也就是说递归之前左右两边的数据是无序的，快速排序是在递归之前先将数组进行排序，就是递归之前的左右两边的数组都是有序的，时间复杂度为O(nlogn).

快排递归代码:

                            
-(
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]
}
         
       

测试代码:

                            
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，如需转载请自行联系原作者