编写QuickSort算法 - 输出不太正确

Question

不幸的是,我以前从未对此进行过编码.我的实现基于对"日期"字段进行排序而在自定义类上运行.是的我完全知道我可以使用内置的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  

我觉得它已经到了那里,但仍然有些事情发生了.

我已经被困在这几天了,非常感谢任何帮助.

干杯.

Answer 1

递归调用被破坏:

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

一个显而易见的事情是你传递pivotIndex两个分区的长度是没有任何意义的.

另一个是索引被打破了.正如您所看到的那样,左侧索引是0,但如果您在第二个递归级别并且想要获得上级右侧分区的左侧分区,则显然不会成立.

还有一件事:枢轴选择器不必了解阵列:

function choosePivot(length)

提示:编程不是一个猜谜游戏,在你开始之前,决定你的"变量"究竟意味着什么.什么是长度,左,右？例如:正确的索引是否包含(它是指向分区的一部分还是超出它).然后挑选纸和笔,找出合适的索引和长度.相信我,你想的越仔细,你就会越快完成.调试浪费了很多时间.然后,只是为了验证您是否在正确的轨道上使用小玩具阵列进行实施,并添加一些console.log消息以查看正在发生的事情.