时间戳

首页 > 解决方案 > 快速排序问题 - 没有得到正确的结果

javascript - 快速排序问题 - 没有得到正确的结果

问题描述

我正在研究 HackerRank 上的Quicksort2问题。我无法弄清楚它希望我如何输出解决方案。

我试图在创建排序数组时对它们进行控制台记录，排序数组的数组和转换为字符串的数组数组。从 processData 函数返回似乎什么也没做。

function checkSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) return false;
    }
    return true;
}

function processData(input) {
    let sortedArrays = [];
    quickSort(input);

    function quickSort(input) {

        if (input.length <= 1) return input;

        let pivot = [input[0]];
        let left = [], right = [];
        for (let i = 1; i < input.length; i++) {
            input[i] < pivot ? left.push(input[i]) : right.push(input[i]);
        }

        let newArr = quickSort(left).concat(pivot, quickSort(right));
        if (checkSort(newArr)) sortedArrays.push(newArr);
        return newArr;
    }
    console.log(sortedArrays);
}

我期待它与 HackerRank 的期望输出相匹配。

标签： javascriptalgorithmquicksort

解决方案

您的实施存在几个问题：

以下是任务描述的引述：

在这个挑战中，每次分区方法完成时打印您的数组，即每当两个子数组以及枢轴合并在一起时。

但是，您正在尝试sortedArrays为每个步骤打印最终排序的数组，而不是问题状态的子数组。newArr因此，在返回之前打印子数组。不要忘记使用join.

另一个引用：

将有两行输入：

数组的大小

数组的 n 个数字

您processData需要一个解析的输入，也就是一个可以使用的数组。如果它接收到原始输入（2 行数据），那么它们应该被相应地解析。例如，它们可以被解析如下：

...
function processData(input) {
    var lines = input.split('\n')
    var len = lines[0]
    var arr = lines[1].split(' '); 
...

因此，您的固定代码可能如下所示：

function processData(input) {
    var lines = input.split('\n')
    var len = lines[0]
    var arr = lines[1].split(' ');
    quickSort(arr);
        function quickSort(input) {

        if (input.length <= 1) return input;

        let pivot = [input[0]];
        let left = [], right = [];
        for (let i = 1; i < input.length; i++) {
            input[i] < pivot ? left.push(input[i]) : right.push(input[i]);
        }

        let newArr = quickSort(left).concat(pivot, quickSort(right));
        // print the subarray once the partitioning for this step has finished
        console.log(newArr.join(' '))
        return newArr;
    }
}

推荐阅读