快速排序

四 快速排序

因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想

- (void)viewDidLoad {

    [super viewDidLoad];

    NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(6), @(1),@(2),@(5),@(9),@(4),@(3),@(7),nil];

    [self quickSortArray:arr withLeftIndex:0 andRightIndex:arr.count - 1];

    NSLog(@"%@",arr);

}

- (void)quickSortArray:(NSMutableArray*)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex

{

    if(leftIndex >= rightIndex) {//如果数组长度为0或1时返回

        return;

    }

    NSInteger i = leftIndex;

    NSInteger j = rightIndex;

    //记录比较基准数

    NSInteger key = [array[i] integerValue];

    while(i < j) {

        /**** 首先从右边j开始查找比基准数小的值 ***/

        while(i < j && [array[j] integerValue] >= key) {//如果比基准数大，继续查找

            j--;

        }

        //如果比基准数小，则将查找到的小值调换到i的位置

        array[i] = array[j];

        /**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/

        while(i < j && [array[i]integerValue] <= key) {//如果比基准数小，继续查找

            i++;

        }

        //如果比基准数大，则将查找到的大值调换到j的位置

        array[j] = array[i];

    }

    //将基准数放到正确位置

    array[i] =@(key);

    /**** 递归排序 ***/

    //排序基准数左边的

    [self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];

    //排序基准数右边的

    [self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];

}

来源：iOS算法笔记-快速排序-OC实现 - 简书

详解：快排