actionscript-3 - 自定义排序算法的速度问题

Question

我正在做一个手动创建排序算法的项目。

经过几次测试，我发现我的堆排序比快速排序快得多(我认为应该相反)，我的选择排序也比插入排序快。有谁知道这里有什么问题吗？

我正在使用从-100到100的整数进行测试，随机生成，数组中的5000个值(我多次修改了这个数字，仍然是同样的问题)。 我的快速排序没有就位。 我想也许flash的递归函数很慢？我的堆排序使用循环，与快速排序不同。但这只是一个假设。

这是我的代码，如果有帮助的话。我启动一个计时器，运行类的 exec() 函数，停止计时器并计算耗时。代码来自维基百科。 堆排序与快速排序的问题:

public class Quick {
public static function exec(seq:Vector.<int>):Vector.<int> {
    if (seq.length<=1) {
        return seq;
    }
    var smallPart:Vector.<int>=new Vector.<int>
    var bigPart:Vector.<int>=new Vector.<int>
    var n:int=seq.length;
    var pivotPosition:int=Math.floor(Math.random()*n);
    var pivot:int=seq.splice(pivotPosition,1)[0];
    for (var i:int=0; i<n-1; i++) {
        if (seq[i]<=pivot) {
            smallPart.push(seq[i]);
        } else {
            bigPart.push(seq[i]);
        }
    }
    seq=exec(smallPart).concat(exec(bigPart),Vector.<int>([pivot]));
    return seq;
}

}

public class Heap{
public static function exec(seq:Vector.<int>) {
    var n:int=seq.length;
    heapify(seq);
    var end:int=n-1;
    while (end > 0) {
        var temp:int=seq[end];
        seq[end]=seq[0];
        seq[0]=temp;
        siftDown(seq, 0, end-1);
        end--;
    }
    return seq
}
public static function heapify(seq:Vector.<int>) {
    var n:int=seq.length
    var start:int=n/2-1
    while (start >= 0) {
        siftDown(seq, start, n-1);
        start--;
    }
}
public static function siftDown(seq:Vector.<int>, start:int, end:int) {
    var root:int=start;
    while (root * 2 + 1 <= end) {
        var child:int=root*2+1;
        var swap:int=root;
        if (seq[swap]<seq[child]) {
            swap=child;
        }
        if (child+1<=end&&seq[swap]<seq[child+1]) {
            swap=child+1;
        }
        if (swap!=root) {
            var temp:int=seq[root];
            seq[root]=seq[swap];
            seq[swap]=temp;
            root=swap;
        } else {
            break;
        }    
    }
}

}

插入排序与选择排序的问题:

public class Insertion{
public static function exec(seq:Vector.<int>) {
    var n:int=seq.length;
    for (var i:int=1; i<n; i++) {
        var holder:int=seq[i];
        var j:int=i-1;
        while (seq[j]>holder) {
            seq[j+1]=seq[j];
            j-=1;
            if (j<0) {
                break
            }
        }
        seq[j+1]=holder;
    }
    return seq
}

}

public class Selection{
public static function exec(seq:Vector.<int>):void{
    var currentMinimum:int;
    var n:int=seq.length;
    for (var i:int = 0; i < n-1; i++) {
        currentMinimum=i;
        for (var j:int = i+1; j < n; j++) {
            if (seq[j]<seq[currentMinimum]) {
                currentMinimum=j;
            }
        }
        if (currentMinimum!=i) {
            var temp:int=seq[i];
            seq[i]=seq[currentMinimum];
            seq[currentMinimum]=temp;
        }
    }
}

}

Answer 1

好吧，我实际上并不了解 ActionScript ，但有很多可能性:

语言问题

我不知道actionscript是如何工作的，但在C++和可能的其他语言中，如果你通过值而不是引用传递向量，它会显着减慢速度。(感谢alxx清除了这一点)上)

在快速排序的情况下，您似乎创建了很多新向量。如果这个操作很慢(我再次提醒你，我不知道 ActionScript )，它可能会偏向于堆排序。

正如 The_asMan 所说，也许您的计时方法不准确，也许您应该使用不同的语言功能。

算法问题

您正在使用 [-100, 100] 之间的 5000 个值。这意味着将会有大量的重复项。快速排序速度快的主要原因之一是您可以使用很多的优化。如果存在重复值，普通(无优化)快速排序可能会非常慢。

此外，还有许多其他优化可以使快速排序在实践中更快。

感知问题

呵呵。感知问题。特洛洛尔;)

插入排序不一定比选择排序快(我不确定您从哪里得到这个想法)。插入排序非常快的主要情况是当列表几乎已排序时。在这种情况下，每个元素的插入只需要几次交换。但在一般情况下(随机数)，它并没有比选择排序有显着的优势。

希望这有帮助。