在Object-C中学习排序算法

[self mb_exchangeWithIndexA:j indexB:i];

}

self.comparator(nil, nil);

[self mb_exchangeWithIndexA:j indexB:l];

return j;

}

过多反复键值使Quick Sort降至O(n^2)

应用双快速排序后, 我们的快速排序算法可以轻松的处理包含大年夜量元素的数组

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

1.算法图示

算法图示

2.代码实现

#pragma mark - /**双路快排*/ 
///应用双快速排序后, 我们的快速排序算法可以轻松的处理包含大年夜量元素的数组 
- (void)mb_identicalQuickSort{ 
    //要特别留意界线的情况 
    [self mb_quickSort:self indexL:0 indexR:(int)self.count - 1]; 
} 
- (void)mb_identicalQuickSort:(NSMutableArray *)array indexL:(int)l indexR:(int)r{ 
    if (l >= r) return; 
    int p = [self __partition2:array indexL:l indexR:r]; 
    [self mb_quickSort:array indexL:l indexR:p-1]; 
    [self mb_quickSort:array indexL:p + 1 indexR:r]; 
} 
- (int)__partition2:(NSMutableArray *)array indexL:(int)l indexR:(int)r{ 
    // 随机在arr[l...r]典范围中, 选择一个数值作为标定点pivot 
    [self mb_exchangeWithIndexA:l indexB:(arc4random()%(r-l+1))]; 
    id v = array[l]; 
    // arr[l+1...i) = v 
    int i = l + 1, j = r; 
    while (true) { 
          
        while (i  l + 1 && self.comparator(array[j],v) == NSOrderedDescending) 
            j--; 
          
        if (i > j) { 
            break; 
        } 
        [self mb_exchangeWithIndexA:i indexB:j]; 	
			 5/7   首页 上一页 3 4 5 6 7 下一页 尾页	
			

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


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