IOS 中 sort 方法的兼容问题

摘要：快速排序在解决中方法问题时，笔者没有考虑时间复杂度的问题，使用的排序算法进行重写，在实际产品环境中引发不小的性能问题。中方法的兼容问题笔者发现或者中方法不生效不同浏览器实现机制差异，故判断后进行该方法的重写处理，代码如下

在解决 Sarafi 中 sort 方法问题时，笔者没有考虑时间复杂度的问题，使用 O(n2) 的排序算法进行重写，在实际产品环境中引发不小的性能问题。

阅读 v8 array.js 源码（Array.js）后发现，Chrome 在实现 sort 方法时对小数组（length <= 10）进行插入排序，对大数组进行快速排序 O(nlogn)，来降低该方法的时间复杂度。

快速排序的核心是不断把原数组做切割，切割成小数组后再对小数组进行相同的处理，这是一种典型的分治的算法设计思路，选取数组中第一个元素作为基准，可对其进行简单实现如下：

function QuickSort(arr, func) {
    if (!arr || !arr.length) return [];
    if (arr.length === 1) return arr;
    
    var pivot = arr[0];
    var smallSet = [];
    var bigSet = [];
    for (var i = 1; i < arr.length; i++) {
        if (func(arr[i], pivot) < 0) {
            smallSet.push(arr[i]);
        } else {
            bigSet.push(arr[i]);
        }
    }
    
    return basicSort(smallSet, func).concat([pivot]).concat(basicSort(bigSet, func));
}

上面的算法创建一个新的数组作为计算结果，从空间使用的角度看是不经济的，Javascript 的快速排序算法中并没有像上面的代码那样创建一个新的数组，而是在原数组的基础上，通过交换元素位置实现排序，故而类似于 push、 pop、 splice 这几个方法，sort 方法也是会修改原数组对象的。

function swap(arr, from, to) {
    if (from === to) return;

    let temp = arr[from];
    arr[from] = arr[to];
    arr[to] = temp;
}
 
function QuickSortWithPartition(arr, fn, from, to) {
    from = from === void 0 ? 0 : from;
    to = to === void 0 ? arr.length : to;

    if (from >= to - 1) {
        return arr;
    }

    let pivot = arr[from];
    let smallIndex = from;
    let bigIndex = from + 1;

    for (; bigIndex < to; bigIndex++) {
        if (fn(arr[bigIndex], pivot) < 0) {
            smallIndex++;
            swap(arr, smallIndex, bigIndex);
        }
    }

    swap(arr, smallIndex, from);

    QuickSortWithPartition(arr, fn, from, smallIndex - 1);
    QuickSortWithPartition(arr, fn, smallIndex + 1, to);

    return arr;
}

其中，from 是起始索引，to 是终止索引，如果这两个参数缺失，则表示处理整个数组。

因为上面的分区过程中，大数分区和小数分区都是从左向右增长，其实我们可以考虑从两侧向中间遍历，这样能有效地减少交换元素的次数。举个例子，假如我们有一个数组 [2, 1, 3, 1, 3, 1, 3]，采用上面的分区算法一共会碰到三次比基准元素小的情况，所以会发生三次交换；而如果我们换个思路，把从右往左找到小于基准的元素，和从左往右找到大于基准的元素交换，这个数组只需要交换一次即可完成排序（把第一个3和最后一个1交换）。

function QuickSortWithPartitionOp(arr, fn, from, to) {
    from = from === void 0 ? 0 : from;
    to = to === void 0 ? arr.length : to;

    if (from >= to - 1) {
        return arr;
    }

    let pivot = arr[from];
    let smallEnd = from;
    let bigBegin = to - 1;

    while (smallEnd < bigBegin) {
        while (fn(arr[bigBegin], pivot) >= 0 && smallEnd < bigBegin) {
            bigBegin--;
        }

        while (fn(arr[smallEnd], pivot) <= 0 && smallEnd < bigBegin) {
            smallEnd++;
        }

        if (smallEnd < bigBegin) {
            swap(arr, smallEnd, bigBegin);
        }
    }

    swap(arr, smallEnd, from);

    QuickSortWithPartitionOp(arr, fn, from, smallEnd - 1);
    QuickSortWithPartitionOp(arr, fn, smallEnd + 1, to);

    return arr;
}

快速排序算法平均时间复杂度是 O(nlogn)，但它的最差情况下时间复杂度会增大到 O(n2)，其性能好坏的关键就在于分区是否合理：如果每次都能平均分成相等的两个分区，那么只需要 logn 层递归；而如果每次分区都不合理，总有一个分区是空的，则需要 n 层迭代。

对于一个内容随机的数组而言，不太可能出现最差情况，但日常处理的数组往往并不是内容随机的，一种很容易的解决方案是不要选取固定位置的元素作为基准元素，而是随机从数组里挑出一个元素作为基准元素，这样可以极大概率地避免最差情况，然而这并不等于避免最差情况，特别是在数组很大的时候，更要求我们更谨慎地选取基准元素。

三数取中法是挑选基准元素的一种常用方法：即挑选基准元素时，先把第一个元素、最后一个元素和中间一个元素挑出来，这三个元素中大小在中间的那个元素就被认为是基准元素。

function getPivot(arr, fn, from, to) {
    let mid = (from + to) >> 1;

    if (fn(arr[from], arr[mid]) < 0) {
        swap(arr, from, mid);
    }

    if (fn(arr[from], arr[to]) > 0) {
        swap(arr, from, to);
    }

    if (fn(arr[to], arr[mid]) < 0) {
        swap(arr, to, mid);
    }

    return arr[from];
}

其他比较典型的取中值手段包括：

一种是平均间隔取一个元素，多个元素取中位数（即多取几个，增加可靠性）

一种是对三数取中进行递归运算，先把大数组平均分成三块，对每一块进行三数取中，会得到三个中值，再对这三个中值取中位数

v8 源码中的基准元素选取更为复杂：如果数组长度不超过1000，则进行基本的三数取中；如果数组长度超过1000，那么 v8 的处理是除去首尾的元素，对剩下的元素每隔200左右挑出一个元素，对这些元素排序，找出中间的那个，并用这个元素跟原数组首尾两个元素一起进行三数取中。

设想一下，一个数组里如果所有元素都相等，基准元素不管怎么选都是一样的，那么在分区的时候，必然出现除基准元素外的其他元素都被分到同一个分区的情况，进入最差性能的 case。

那么对于重复元素应该怎么处理呢？
从性能的角度，如果发现一个元素与基准元素相同，那么它应该被记录下来，避免后续再进行不必要的比较。

function QuickSortWithPartitionDump(arr, fn, from, to) {
    from = from === void 0 ? 0 : from;
    to = to === void 0 ? arr.length - 1 : to;

    if (from >= to) {
        return arr;
    }

    let pivot = getPivot(arr, fn, from, to);
    let smallEnd = from;
    let bigBegin = to;
    let i = from + 1;

    while (i <= bigBegin) {
        let r = fn(arr[i], pivot);
        if (r < 0) {
            swap(arr, smallEnd++, i++);
        } else if (r > 0) {
            swap(arr, i, bigBegin--);
        } else {
            i += 1;
        }
    }

    QuickSortWithPartitionDump(arr, fn, from, smallEnd - 1);
    QuickSortWithPartitionDump(arr, fn, bigBegin + 1, to);

    return arr;
}

对于小数组，可能使用快速排序的速度还不如平均复杂度更高的插入排序，故而出于减少递归深度的考虑，数组长度较小时，使用插入排序算法。

function insertSort(arr, fn, from, to) {
    for (let i = from; i < to; i++) {
        for (let j = i + 1; j < to; j++) {
            let t = fn(arr[i], arr[j]);
            let r = (typeof t === "number" ? t : t ? 1 : 0) > 0;
            if (r) {
                let tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }

    return arr;
}

快速排序如果递归太深的话很可以出现“爆栈”，上面提到的对小数组采用插入排序算法，以及采用内省排序算法都可以减少递归深度，不过 v8 引擎中还做了一些不太常见的优化：每次分区后，v8 引擎会选择元素少的分区进行递归，而将元素多的分区直接通过循环处理，无疑可以大大减小递归深度。

由于快速排序时间复杂度的不稳定性，David Musser 于1997设计了内省排序法（Introsort），这个算法在快速排序的基础上，监控递归的深度：一旦长度为 n 的数组经过 logn 层递归（快速排序算法最佳情况下的递归层数）还没有结束的话，就认为这次快速排序的效率可能不理想，转而将剩余部分换用其他排序算法，通常使用堆排序算法（Heapsort，最差时间复杂度和最优时间复杂度均为 O(nlogn)）。

笔者发现 Safari 或者 iPhone 中 sort 方法不生效（不同浏览器实现机制差异），故判断后进行该方法的重写处理，代码如下：

;(function(w){
    if(/msie|applewebkit.+safari/i.test(w.navigator.userAgent)){
        var _sort = Array.prototype.sort;
        Array.prototype.sort = function(fn){
            if(!!fn && typeof fn === "function"){
                if(this.length < 2) return this;
                var i = 0, j = i + 1, l = this.length, tmp, r = false, t = 0;
                for(; i < l; i++){
                    for(j = i + 1; j < l; j++){
                        t = fn.call(this, this[i], this[j]);
                        r = (typeof t === "number" ? t : !!t ? 1 : 0) > 0 ? true : false;
                        if(r){
                            tmp = this[i];
                            this[i] = this[j];
                            this[j] = tmp;
                        }
                    }
                }
                return this;
            } else {
                return _sort.call(this);
            }
        };
    }
})(window);