对具有相同数字的数组进行快速排序

Question

我正在尝试学习快速排序算法的工作原理。我是通过阅读CLR算法这本书来做到这一点的。我似乎无法弄清楚算法是如何处理相同数字的数组的，而且我在网上也找不到任何示例。例如，快速排序算法的进度是多少：

{5h, 5i, 5j, 5k, 5m, 5n}

这里的字符(h，i，j，k，m，n)只是为了区分不同的5，提前感谢你的帮助！

Answer 1

如果他们使用合理的变量名，That damn book本可以更容易理解，但我猜他们不想背离用于所有数学计算的常规单字母变量约定。

我试图保留它们的函数和变量名称，并且几乎复制了代码，包括它们使用的“数组从1开始”的约定。我模仿了非随机枢轴版本。

演示：http://jsfiddle.net/p7R99/

或者只是将以下内容放入.html文件中

<pre id="out">
</pre>

<script>
function QUICKSORT(A, p, r) {
    if (p < r) {
        var q = PARTITION(A, p, r);
        output("q=" + q + " and A=" + arr(A) + "\n");
        QUICKSORT(A, p, q - 1);
        QUICKSORT(A, q + 1, r);
    }
}

function PARTITION(A, p, r) {
    var x = A[r];
    var i = p - 1;
    for (var j = p; j < r - 1; j++) {
        if (intval(A[j]) <= intval(x)) {
            i = i + 1;
            swap(A, i, j);
        }
    }
    swap(A, i + 1, r);
    return i + 1;
}

function intval(str) {
    return parseInt(str, 10);
}



function swap(A, i, j) {
    var tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

function output(msg) {
    var ele = document.getElementById("out");
    ele.innerHTML += msg;
}
function arr(A) {
    return A.slice(1).join(" ");
}


var A = [undefined, "5h", "5i", "5j", "5k", "5m", "5n"];
QUICKSORT(A, 1, A.length);
</script>

结果

q=1 and A= 5i 5j 5k 5m 5n 5h
q=6 and A= 5i 5j 5k 5m 5h 5n
q=4 and A= 5i 5j 5m 5k 5h 5n
q=2 and A= 5j 5i 5m 5k 5h 5n

Answer 2

这是少数几种快速排序可以提供O (n^2)性能的情况之一，因为(使用不太仔细的实现)有可能你的一个分区最终是空的。

如果您事先了解输入，并且它们基本相同，则可能需要考虑使用Counting sort或three way quicksort