javascript - 如何使用事件驱动比较编写 QuickSort？

Question

我正在编写一个网络应用程序，它会向用户询问一系列问题，这些问题只是两个值的主观比较。他们选择更大的那个，然后它构成了排序所需的下一个比较。目标是对58个项目进行排序，并显示排序列表。

我想使用快速排序，因为在 80% 的情况下，它需要的比较次数少于归并排序，归并排序需要 342 次比较。 (我编写了一个程序，运行了 5,000,000 次模拟排序 58 项数组，发现 342 是 QS 要求的比较次数的第 80 个百分位数。)由于这是在 JavaScript 中完成的，所以我需要算法等待一个每次都需要比较事件，然后，当事件被触发时，继续算法。我很难想象这会是什么样子。

我非常确定，为了以这种方式实现 QS——除非有一些我没有想到的带有 JavaScript 闭包的聪明方法——我不能递归地实现它。我找到了一个 iterative implementation of QS ，并试图弄清楚如何拆分它，以便事件触发器将从它停止的地方继续算法。

我会发布我的代码，但老实说，我认为考虑到它的困惑和脱节，弊大于利。我喜欢 JavaScript 的完整实现，但即使是伪代码也会有所帮助。

Answer 1

我使用 JavaScript Promises 和递归解决了这个问题。我认为这是一个非常干净的解决方案。

class QS {
    constructor(array) {
        this._array = array;
        this._comparisons = 0;
    }

    run() {
        new Promise(r => {
            return this.runQS(0, this._array.length - 1, r);
        }).then(() => {
            console.log(this._array);
            console.log(this._comparisons);
        });
    }

    runQS(low, high, resolve, part) {
        if (low < high) {
            return new Promise(r => {
                this.partition(low, high, r);
            }).then(p => {
                return new Promise(r => {
                    this.runQS(low, p - 1, r, p);
                });
            }).then(p => {
                return new Promise(r => {
                    this.runQS(p + 1, high, r, p);
                });
            }).then(() => {
                resolve(part);
            });
        } else {
            resolve(part);
        }
    }

    partition(low, high, res) {
        let self = this,
            i = low - 1,
            j = low,
            partProm = Promise.resolve();

        function inner(i, j, doSwap) {
            if (doSwap) {
                i++;
                self.swap(i, j);
            }

            j++;
            if (j < high) {
                addThen(i, j);
            } else {
                i++;
                self.swap(i, high);
                res(i);
            }
        }

        function addThen(i, j) {
            partProm = partProm.then(() => {
                self._comparisons++;
                return new Promise(r => {
                    promptUser(self._array, j, high, r);
                });
            }).then(s => {
                inner(i, j, s);
            });
        }

        if (low < high) {
            addThen(i, j);
        }
    }

    swap(i, j) {
        let temp = this._array[i];
        this._array[i] = this._array[j];
        this._array[j] = temp;
    }
}

promptUser() 的占位符是:

function promptUser(a, i, j, resolve) {
    setTimeout(() => {
        console.log('Comparing ' + a[i] + ' against ' + a[j]);
        resolve(a[i] < a[j]);
    }, 10);
}

将 resolve 传递到由按钮的 onclick 触发的函数中并不难。