OC中的快速排序及其效率提升方法

快速排序：一种不稳定的内排序算法，时间复杂度:最差O(n²)，最好O(nlogn)。
思想：在一趟排序中，将数组分组为两部分，再对划分出的大、小两部分，分别进行快速排序，是在冒泡排序基础上的递归进行。

---

一、快速排序的基本实现

NSInteger partition(NSMutableArray *arrayM,NSInteger low, NSInteger high){
    
    NSInteger point = [arrayM[low] integerValue];//默认取第一个元素

    while (low < high) {
        
        //不出while循环之前point不变
        while (low < high && [arrayM[high] integerValue] >= point) {
            high--;//右边跳过当前元素 不需要移动
        }
        [arrayM exchangeObjectAtIndex:low withObjectAtIndex:high];
        
        while (low < high && [arrayM[low] integerValue] <= point) {
            low++;//左边跳过当前元素 不需要移动
        }
        [arrayM exchangeObjectAtIndex:low withObjectAtIndex:high];
    }
    return low;
}

//快速排序
void quickSort(NSMutableArray *arrayM, NSInteger low, NSInteger high){
    
    if (low < high) {
        NSInteger point = partition(arrayM, low, high);
        
        //分治递归
        quickSort(arrayM, 0, point - 1);
        quickSort(arrayM, point + 1, high);
    }
}

• 测试用例：

NSMutableArray *arrayM = @[@(5),@(2),@(6),@(0),@(3),@(9),@(1),@(7),@(4),@(8)].mutableCopy;

quickSort(arrayM, 0, arrayM.count - 1);
排序后的结果为：(0,1,2,3,4,5,6,7,8,9)

---

二、优化1：三数取中法

三数取中法：优化了partition方法中基准点point的合理性。

我们把刚刚的用例的5和9调换一下位置，得到新的测试用例 ：

NSMutableArray *arrayM = @[@(9),@(2),@(6),@(0),@(3),@(5),@(1),@(7),@(4),@(8)].mutableCopy;

在新的测试用例下partition方法中point取第一个元素9，明显是不合理的，因为我们希望基准点的值尽可能的居中。

以下是三数取中法优化后的partition方法：

NSInteger partition(NSMutableArray *arrayM,NSInteger low, NSInteger high){
    
    {//优化1：三数取中法
        NSInteger mid = (low + high) / 2;
        if (arrayM[low] > arrayM[high]) {
            [arrayM exchangeObjectAtIndex:low withObjectAtIndex:high];
        }
        if (arrayM[mid] > arrayM[high]) {
            [arrayM exchangeObjectAtIndex:mid withObjectAtIndex:high];
        }
        //第二个if完成后 就找出了3个元素中最大的

        //把“认为合理的mid”放在low的位置
        if (arrayM[mid] > arrayM[low]) {
            [arrayM exchangeObjectAtIndex:mid withObjectAtIndex:low];
        }
    }
    
    NSInteger point = [arrayM[low] integerValue];//基准点

    while (low < high) {
        
        //不出while循环之前point不变
        while (low < high && [arrayM[high] integerValue] >= point) {
            high--;//右边跳过当前元素 不需要移动
        }
        [arrayM exchangeObjectAtIndex:low withObjectAtIndex:high];
        
        while (low < high && [arrayM[low] integerValue] <= point) {
            low++;//左边跳过当前元素 不需要移动
        }
        [arrayM exchangeObjectAtIndex:low withObjectAtIndex:high];
    }
    return low;
}

此时point的合理性已经大概率提升了，但还是可能有比较糟糕的情况 。
例：将最初的测试用例稍加修改

NSMutableArray *arrayM = @[@(9),@(2),@(6),@(0),@(3),@(7),@(1),@(5),@(4),@(8)].mutableCopy;

此时low,mid,high为最大的3个值，partition方法第一趟比较mid为8，此时point还是不理想，但也比9强了不是吗？

---

三、优化2：减少不必要的交换

在partition方法中，基准点point的值在比较的过程中不断被交换移动，

[arrayM exchangeObjectAtIndex:low withObjectAtIndex:high];

但arrayM[low]已经被记录在了point，所以只需要将arrayM[low]和arrayM[high]单向赋值移动，不需要移动point，并在最后把point的值放在low==point的位置。

NSInteger partition(NSMutableArray *arrayM,NSInteger low, NSInteger high){
    
    NSInteger point = [arrayM[low] integerValue];//基本选点
    
    while (low < high) {
        
        //不出while循环之前point不变
        while (low < high && [arrayM[high] integerValue] >= point) {
            high--;//右边跳过当前元素 不需要移动
        }
        arrayM[low] = arrayM[high];//优化2 不exchange直接赋值
        
        while (low < high && [arrayM[low] integerValue] <= point) {
            low++;//左边跳过当前元素 不需要移动
        }
        arrayM[high] = arrayM[low];//优化2 不exchange直接赋值
    }
    
    arrayM[low] = @(point);//优化2 基准点的值放到正确位置
    
    return low;
}

---

四、优化3：数据规模小，使用更快的直接插入排序

void quickSort(NSMutableArray *arrayM, NSInteger low, NSInteger high){
    
    NSInteger threshold = 5;//分水岭
    
    if (high - low > threshold) {
        NSInteger point = partition(arrayM, low, high);
        //分治递归
        quickSort(arrayM, 0, point - 1);
        quickSort(arrayM, point + 1, high);
    }
    else{
        insertSort(arrayM);//优化3 数据规模小使用直接插入排序
    }
}

//直接插入排序 结果为：从小到大
void insertSort(NSMutableArray *arrayM){
    
    NSInteger i, j, temp;
    
    for (i = 0; i < arrayM.count; i++) {
        temp = [arrayM[i] integerValue];

        for (j = i; j > 0 && [arrayM[j - 1] integerValue] > temp; j--) {
            arrayM[j] = arrayM[j - 1];
        }
        arrayM[j] = @(temp);
    }
}

《数据结构》- 严蔚敏 289页 结论(2）
当序列中的记录“基本有序”或n值较小时，直接插入排序是最佳的排序方式

---

五、关于尾调用优化（tail-call optimization）

⚠️Objective-C此方案不可行
下面为按照尾调用优化思想修改的代码：

    if (high - low > threshold) {
           //优化前
//        NSInteger point = partition(arrayM, low, high);
//        //分治递归
//        quickSort(arrayM, 0, point - 1);
//        quickSort(arrayM, point + 1, high);
        
        //尾调用优化
        while (low < high) {
            NSInteger point = partition(arrayM, low, high);
            quickSort(arrayM, 0, point - 1);
            low = point + 1;
        }
    }

经过实际测试查看了Xcode的栈回溯后，发现并没有进行优化。
个人认为没有尾调用优化的原因是：在while循环中调用quickSort()后，由于low = point + 1，point不能被释放，所以当前“栈帧”不能被复用，只能推入新的“栈帧”。
(ps：如果知道如何实现Objective-C快排尾调用优化请赐教，十分感激）

《Effective Objective-C 2.0》45页最后一段原文。
如果某函数的最后一项操作是调用另外一个函数，那么就可以运用“ 尾调用优化 ”技术。编译器会生成调转至另一函数所需的指令码，而且不会向调用堆栈中推入新的“栈帧”（frame stack）。只有当某函数的最后一个操作仅仅是调用其他函数而不会将其返回值另作他用时，才能执行“ 尾调用优化 ”。这项优化对objc_msgSend非常关键，如果不这么做的话，那么每次调用Objective-C方法之前，都需要为调用objc_msgSend函数准备“栈帧”，大家在“栈踪迹”（stack trace）中可以看到这种“栈帧”。此外，如果不优化，还会过早地发生“栈溢出”（stack overflow）现象。

关于OC的尾调用优化，你可以写一个很小的递归例子，将Xcode ->Edit Scheme ->build configuration改为release（只有release模式编辑器才会尾调用优化），在方法内打好断点，在方法调用过程中查看Xcode展示的栈回溯。

---

最后，这里是个能运行的优化后的快排Demo，thx。