ChenSort

ChenSort copied to clipboard

const quickSort = (array) => { const sort = (arr, left = 0, right = arr.length - 1) => { if (left >= right) { return } let i = left let j = right const baseVal = arr[j] while (i < j) { while (i < j && arr[i] <= baseVal) { i++ } arr[j] = arr[i] while (j > i && arr[j] >= baseVal) { j-- } arr[i] = arr[j] } arr[j] = baseVal / sort(arr, left, j - 1) sort(arr, j + 1, right) } const newArr = array.concat() sort(newArr) return newArr }

function chenSort(list) { if (list.length < 2) { return; }

let maxValue = list[0];
let minValue = maxValue;
for (let i = 1, len = list.length; i < len; ++i) {
    if (list[i] > maxValue) {
        maxValue = list[i];
    }
    if (list[i] < minValue) {
        minValue = list[i];
    }
}

if (maxValue === minValue) {
    return;
}

let bucketSize = Math.min(list.length, 5000);
let maxBucketIndex = bucketSize - 1;

let buckets = new Array(bucketSize);
let slot;

const factor = maxBucketIndex / (maxValue - minValue);
for (let i = 0, len = list.length; i < len; ++i) {
    slot = Math.trunc((list[i] - minValue) * factor);
    if (buckets[slot] === undefined) {
        buckets[slot] = [];
    }
    buckets[slot].push(list[i]);
}

function compare(left, right) {
    return left - right;
}

let index = 0;
for (let i = 0, len = buckets.length; i < len; ++i) {
    if (buckets[i] != null) {
        if (buckets[i].length > 1) {
            if (buckets[i].length >= 1000) {
                chenSort(buckets[i]);
            } else {
                buckets[i].sort(compare);
            }
            for (let element of buckets[i]) {
                list[index++] = element;
            }
        } else {
            list[index++] = buckets[i][0];
        }
    }
}

}

function main() { let arr = []; for (let i = 0; i < 100000000; ++i) { arr.push(Math.ceil(Math.random() * 1000000)); } let startTime = new Date(); quickSort(arr); console.log(`快速排序完成，用时: ${new Date()-startTime}`); startTime = new Date(); chenSort(arr); console.log(`chen排序完成，用时: ${new Date()-startTime}`); }

main();

算法的核心思想是以空间换时间，使用改进的桶分配和存放算法来尽可能地减少比较和互换的次数，达到性能的提升。如果由于实现不当，或平台环境本身的原因，导致桶分配和存放的开销很大，那么性能就可能比快排更慢。比如 ChenSort 的第一个 Java 版本，由于实现不当，引起了大量的自动装箱和拆箱，导致性能比快排慢很多，优化后性能就起飞了。我不太熟悉 JS，不知道是否有更高效的实现方法呢？