排序算法性能如何随数据中的重复元素而变化

Question

对于相同大小的数组，排序算法（合并、快速）的性能是否会因重复元素而降低。

我可以说吗

var arr = [6,4,7,1,8,3,9,2,10,5]; --> Sorts faster because of unique elements
var arr = [1,1,3,3,3,2,4,4,5,10]; --> Slower because repeated elements

我尝试编写一个简单的快速排序实现，它给了我上述行为。我是不是做错了什么

var Quicksort = function(arr, si, ei) {

    if (si >= ei) return;

    var pivot = arr[ei];
    var pi = si;

    for (var i = si; i < ei; i++) {

        if (arr[i] < pivot) {
            Swap(arr, pi, i);
            pi++;
        }
    }


    Swap(arr, pi, ei);

    Quicksort(arr, 0, pi - 1);
    Quicksort(arr, pi + 1, ei);

    return arr;

}

function Swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// Execute 
var input = [];
for (var i = 0; i < 1000; i++) {
    input.push(Math.floor(Math.random() * 100000));
}
console.log(input);

var result = Quicksort(input, 0, input.length - 1);

console.log(result);

谢谢

Answer 1

相等值或不同值的数量不影响合并或快速排序的效率。

影响快速排序效率的是如何选择枢轴值以及数组是否已经排序。

阅读：http://www.geeksforgeeks.org/when-does-the-worst-case-of-quicksort-occur/

就归并排序而言，影响其效率的是您在归并阶段最终进行了多少次比较。

阅读：When will the worst case of Merge Sort occur?

因此，数字出现的频率不会影响排序算法。

当然，假设您有一个大小为 n 的数组，其中所有值都等于 x，快速排序会表现良好，因为数组已经排序。

如：[6,6,6,6,6]，快速排序将在 n² 中执行。

我相信还有其他排序算法可以更好地处理值重复很多的数组，我想说计数排序 (http://www.geeksforgeeks.org/counting-sort/) 将是一个很好的方法。

排序算法性能如何随数据中的重复元素而变化

How does Sort algorithm performance vary with repeated elements in data

algorithm

sorting

array-algorithms