2

不幸的是，我以前从未自己编写过代码。我的实现在基于对“日期”字段进行排序的自定义类上运行。是的，我完全知道我可以使用内置的 Javascript 排序并指定比较器函数，但这不是我感兴趣的。

目前我从一个反向排序的列表开始，然后在调用我的“target_sort”（QuickSort）之后，我得到一个排序不太好的列表。

代码：

function target_sort_wrapper(array) {
    target_sort(array, array.length, 0, array.length);
}


//Quicksort to swap around targets based on dates
//"array" is DDATA, where DDATA[i] are targets
function target_sort(array, length, left, right) {
    if (length < 2) {
        return;
    }
    var pivotIndex = choosePivot(array, length); //returns the index    

    partition(array, pivotIndex, left, right);

    target_sort(array, pivotIndex, 0, pivotIndex - 1);
    target_sort(array, pivotIndex, pivotIndex + 1, array.length);

}

function partition(array, pivotIndex, left, right) {
    //first, put the pivot as the first element to make things easier
    array.swap(pivotIndex, 0);
    var pivot = array[0];
    var i = left + 1;
    for (var j = left + 1; j < right; j++) {
        if (dateValue(array[j].date) < dateValue(pivot.date)) {
            //dateValue converts stuff like "Jun18" into 618, to numerically compare
            array.swap(i, j);
            i = i + 1;
        }
    }
    //don't forget to put pivot back where it belongs
    array.swap(left, i - 1);
}

function choosePivot(array, length) {
    return Math.floor(Math.random() * length); //0 (inclusive) to length (exclusive) 
}

    Array.prototype.swap = function (i, j) {
        var temp = this[i];
        this[i] = this[j];
        this[j] = temp;
        return this;
    }

这是输出。首先打印反向排序的列表，然后是我的“target_sort”的结果：

Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 
============================================================= 
Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun25 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun19 Jun25 Jun25 Jun25 Jul05 Jun25 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul05 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jun25 Jul06 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jun25 Jul06 Jul06 Jun25 Jul06 Jun25 Jun25 Jun25 Jun25 Jul05 Jun25 Jul05 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul06 Jul05 Jul05 Jul05 Jul06

我觉得它快到了，但还是有什么不对劲。

我已经坚持了几天了，非常感谢您的帮助。

干杯。

4

2 回答 2

7

递归调用被破坏：

target_sort(array, pivotIndex, 0, pivotIndex - 1);

一件显而易见的事情是，您将pivotIndex两个分区的长度作为没有任何意义的。

另一个是索引被破坏了。正如您所看到的，左索引是0，但如果您在第二个递归级别并且想要获得上级右分区的左分区，那显然不是真的。

还有一件事：枢轴选择器不必知道数组：

function choosePivot(length)

提示：编程不是猜谜游戏，在开始之前，请确定“变量”的确切含义。什么是长，左，右？例如：正确的索引是否包含在内（它是指向分区的一部分还是刚好超出它）。然后挑选一张纸和铅笔，找出合适的索引和长度。相信我，你想得越仔细，你就会越快完成。调试会浪费很多时间。然后，只是为了验证您是否走在正确的轨道上，请使用一个小型玩具数组来实现，并添加一些console.log消息以查看发生了什么。

于 2012-07-24T19:55:59.033 回答
2

我现在已经创建了一个正确的版本，感谢 Karoly 的提示。概括：

  • 不应该做关于长度的事情，而是左右
  • 我总是为递归调用选择一个糟糕的支点（再次，必须左右，并且必须落在子数组的正确范围内）

代码：

function target_sort_wrapper(array) {
    target_sort(array, 0, array.length);
}


//Quicksort to swap around targets based on dates
//"array" is DDATA, where DDATA[i] are targets
function target_sort(array, left, right) {
    if ((right-left) < 2) {
        return;
    }

    var pivotIndex = choosePivot(left, right); //returns the index  

    pivotIndex = partition(array, pivotIndex, left, right);

    target_sort(array, left, pivotIndex);
    target_sort(array, pivotIndex+1, right);

}

function partition(array, pivotIndex, left, right) {
    //first, put the pivot as the first element to make things easier
    var pivot = array[pivotIndex];
    array.swap(pivotIndex, left);
    var i = left + 1; 
    for(var j = left + 1; j < right; j++) {
        //if (array[j] > pivot) { } //do nothing, satisfies invariant
        if (dateValue(array[j].date) < dateValue(pivot.date)) {
        //if (array[j] < pivot) {
            array.swap(i, j);
            i = i + 1; 
        }
    }
    //don't forget to put pivot back where it belongs
    array.swap(left, i-1);
    return (i-1);
}

function choosePivot(left, right) {
    return (left + Math.floor(Math.random() * (right-left)));

}

Array.prototype.swap = function(i, j) {
    var temp = this[i];
    this[i] = this[j];
    this[j] = temp;
    return this;
}
于 2012-07-24T22:15:43.307 回答