三路快速排序

快速排序是由东尼·霍尔所成长的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则须要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序平日明显比其他 Ο(nlogn) 算法更快，因为它的内部轮回（inner loop）可以在大年夜部分的架构上很有效力地被实现出来。

对于包含有大年夜量反复数据的数组, 三路快排有巨大年夜的优势

对于一般性的随机数组和近乎有序的数组, 三路快排的效力固然不是最优的, 然则是在异常可以接收典范围里

是以, 在一些说话中, 三路快排是默认的说话库函数中应用的排序算法。比如Java:)

快速排序的优化可推敲当分区距离小的的时刻转而应用插入排序

1.算法图示

2.代码实现

#pragma mark - /**三路快排*/ 
//对于包含有大年夜量反复数据的数组, 三路快排有巨大年夜的优势 
- (void)mb_quick3WaysSort{ 
    //要特别留意界线的情况 
    [self mb_quick3WaysSort:self indexL:0 indexR:(int)self.count - 1]; 
} 
/// 递归的三路快速排序算法 
- (void)mb_quick3WaysSort:(NSMutableArray *)array indexL:(int)l indexR:(int)r{ 
    if (l >= r)  return; 
      
    self.comparator(nil, nil); 
    // 随机在arr[l...r]典范围中, 选择一个数值作为标定点pivot 
    [self mb_exchangeWithIndexA:l indexB:(arc4random_uniform(r-l+1) + l)]; 
      
    id v = array[l]; 
      
    int lt = l; // array[l+1...lt] < v 
    int gt = r + 1; // array[gt...r] > v 
    int i = l + 1; // array[lt+1...i) == v 
      
    while (i < gt) { 
        if ( [self compareWithBarOne:array[i] andBarTwo:v] == NSOrderedAscending) { 
            self.comparator(nil, nil); 
            [self mb_exchangeWithIndexA:i indexB:lt + 1]; 	
			
 6/7   首页 上一页 4 5 6 7 下一页 尾页
	
			

　　推荐阅读
　　关于大数据，你应该知道的75个专业术语
上篇（25 个术语）如不雅你刚接触大年夜数据，你可能会认为这个范畴很难以懂得，无大年夜下手。不过，你可以大年夜下面这份包含了 25 个大年夜数据术语的清单入手，那么我们开端吧。算法（Algorithm）：算法可以懂得>>>详细阅读


本文标题：在Object-C中学习排序算法
地址：http://www.17bianji.com/lsqh/36561.html
 1/2    1