快速排序算法(OC实现)

1.快速排序的意义：
快速排序是一种优雅的排序算法，快速排序使用分而治之的策略。（一种递归式问题解决方法），快速排序是一种常用的排序算法，比起选择排序快的多，例如C语言标准库中的函数qsort实现的就是快速排序。

2.快速排序的工作原理
（假设这个数组含有三个元素）[33,15,10]
1.首先从数组中选择一个元素，这个元素被称为基准值。（一般情况下将数组的第一个元素作为基准值）。

屏幕快照 2019-01-30 上午10.35.04.png

2.接下来找出比基准值小的元素以及比基准值大的元素。

屏幕快照 2019-01-30 上午10.35.49.png

这个过程被称为分区，现在你有：
1.一个由小于基准值的数字组成的子数组；
2.基准值；
3.一个由大于基准值的数字组成的子数组。

这里只是进行了分区，得到的两个数组是无序的。但是如果这两个数组是有序的，对整个数组进行排序将非常容易。 屏幕快照 2019-01-30 上午10.39.14.png 屏幕快照 2019-01-30 上午10.39.53.png 屏幕快照 2019-01-30 上午10.40.39.png

不管将哪个元素用作基准值，这都管用。假设你将15用作基准值

屏幕快照 2019-01-30 上午10.43.42.png

这个数组只有一个元素，而你知道如何对这些数组进行排序。现在你就知道如何对包含三个元素的数组进行排序了，步骤如下。
1.选择基准值
2.将数组分成两个子数组，小于基准值的元素和大于基准值的元素。
3.对这两个子数组进行快速排序。
包含四个元素的数组呢。

屏幕快照 2019-01-30 上午10.47.43.png

左边的子数组包含三个元素，而你知道如何对包含三个元素的数组进行排序，对其 递归调用快速排序。

屏幕快照 2019-01-30 上午10.59.23.png 屏幕快照 2019-01-30 上午10.59.57.png 屏幕快照 2019-01-30 上午11.00.45.png 屏幕快照 2019-01-30 上午11.00.57.png 屏幕快照 2019-01-30 上午11.01.48.png

下面是OC实现快速算法的代码实现

- (void)viewDidLoad {
    [super viewDidLoad];
    //待排序的无序数组
    NSMutableArray *disorderArr = [[NSMutableArray alloc] initWithObjects:@(100), @(88),@(66),@(101),@(1),@(9),@(0),@(10),nil];
    [self quickSortArray:disorderArr withLeftIndex:0 andRightIndex:disorderArr.count - 1];
    NSLog(@"%@",disorderArr);
}

- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
    if (leftIndex >= rightIndex) {// 基线条件：为空或只包含一个一个元素的数组是有序的，不需要排序
        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);//当i=j 的时候 说明这个时候基准值处于中间的位置，那么左边的所有值都比基准值小，右边的所有值都比基准值大

    /**** 递归排序 ***/
    //排序基准数左边的
    [self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
    //排序基准数右边的
    [self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}

得到结果

屏幕快照 2019-01-30 下午2.05.57.png