快速排序，附OC代码

快速排序原理：

以升序排列为例，在一组数列中，找到一个基准数key，把数列中比基准数小的数排到基准数左边；比基准数大的数排到右边，此为第一遍排序；

然后以上面的方式，继续排基准数左边和右边的数列，直到排完。

案例讲解：

基准数一般为选择数列第一个数字，如下图数列中的6。

待排序数列

首先记录下标，此处起点为i=0，终点j=9；从右往左找到比基准数6小的数（此处为5），记录下标（j=9）然后和6交换，结果如下图。记住右边交换完就换左边排！

第一次右往左排序

接着从左往右找比6大的数（此处为7），记录下标（i=3），和6交换，结果如下图。记住左边交换完就换右边排！

第一次从左往右排序结果

按上面方式从右往左排。从右往左找到比基准数6小的数（此处为4），记录下标（j=6）然后和6交换，结果如下图。

第二次从右往左排序结果

接着从左往右找到比基准数6大的数（此处为9），记录下标（i=4）然后和6交换，结果如下图。

第二次从左往右排序结果

从右往左找到比基准数6小的数（此处为3），记录下标（j=5）然后和6交换，结果如下图。

第三次从右往左排序结果

此时从左往右排，记住i=4，i继续往右去发现i=j=5了，所以此刻第一遍排序已完成。

接下来按上面方式继续排基准数左边和右边的数列，直到排完不可排

基准数左边待排数列 基准数右边边待排数列

代码

- (void)quickSort:(NSMutableArray *)arr startIndex:(int)startIndex endIndex:(int)endIndex
{
    if (endIndex <= startIndex) return;
    int i = startIndex;
    int j = endIndex;
    id key = arr[startIndex];
    while (true)
    {
        /*从右向左找比key小的值*/
        while ([arr[j] intValue] >= [key intValue])//判断条件要加等号，重复数字也能排
        {
            if (j == startIndex){
                break;
            }
            j--;
            
        }
        if (i >= j){
            break;
        }
        /*交换i,j对应的值*/
        id temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        
        /*从左向右找比key大的值*/
        while ([arr[i] intValue] <= [key intValue])
        {
            if (i == endIndex){
                break;
            }
            i ++;
        }

        if (i >= j){
            break;
        }

        /*交换i,j对应的值*/
        id tempj = arr[i];
        arr[i] = arr[j];
        arr[j] = tempj;
    }

    //递归继续排左右两边对象
    [self quickSort:arr startIndex:startIndex endIndex:j - 1];
    [self quickSort:arr startIndex:j + 1 endIndex:endIndex];

}

demo地址

git地址