1

我正在尝试使用 Javascript 编写排序算法。伪代码在我的链接中。这是我的 Go Playground 链接。 http://play.golang.org/p/wQwO6Wvd7b

如您所见，它适用于其他语言。（我用相同的代码尝试了 Python、C、C++、Ruby、Go，它们都运行良好。）所以我用 Javascript 做了完全相同的事情，但它不起作用，我不知道为什么。感谢 Chris 在我之前的帖子：Javascript 排序。分配失败过程内存不足错误

我发现我在 Javascript 中的代码超出了递归的索引限制，但我不知道为什么以及如何在 Javascript 中实现它，而其他语言只是在我编码时做正确的工作。我肯定错过了 Javascript 和递归中的一些基本内容。任何机构可以帮我弄清楚吗？（不是作业，只是独立自学）我对 Javascript 很陌生。

我认为我不需要在 Javascript 中进行排序，但我想知道我做错了什么。

下面是我用于错误检查的代码。 

  var arr = [-1, 5, 7, 4, 0, 1, -5];
  console.log("Unsorted Array:", arr);
  console.log("# of elements in array:", arr.length)

  function Partition(arr, first_index, last_index) {
        console.log("---")  
        console.log("# of elements in array:", arr.length)
        console.log("First index is", first_index);
        console.log("Last index is", last_index);
        console.log("---")  
        var x = arr[last_index];
        var i = first_index - 1;

        for (var j = 0; j < arr.length-1; j++) {
              if (j > 100) {
                    console.log("Looping way too much.");
                    return;
              }
              if (arr[j] <= x) {
                    i += 1;
                    console.log("Swap index:", i, j);
                    var temp_1 = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp_1;
              }
        }
        console.log("Swap index:", (i+1), last_index);
        var temp_2 = arr[i+1];
        arr[i+1] = arr[last_index];
        arr[last_index] = temp_2;

        return i+1;
  }

  function QSort(arr, first_index, last_index) {
        console.log("QuickSort index:", first_index, last_index);

        if (first_index < last_index) {
              var mid = Partition(arr, first_index, last_index);
              QSort(arr, first_index, mid-1);
              QSort(arr, mid+1, last_index);
        }
  }

  QSort(arr, 0, arr.length-1);
  console.log("Sorted Array:", arr);

我猜为什么这个循环太多了。我发现我在递归方面做错了。

数组中的元素数：8
第一个索引是 2
最后一个索引是 6

交换索引：2 0
交换索引：3 2
交换索引：4 3
交换索引：5 4
交换索引：6 5
交换索引：7 6
交换索引：8 6
快速排序索引：2 7

数组中的元素数：9
第一个索引是 2
最后一个索引是 7 一直

到

4

3 回答 3

1

我不知道这在其他语言中是如何工作的，因为这写得不正确。分区方法中的循环适用于整个数组，而实际上它应该只适用于被告知要处理的部分（在 first_index 和 last_index 之间）

这行代码：

for (var j = 0; j < arr.length-1; j++)

应该：

for (var j = first_index; j < last_index; j++)
于 2013-09-06T22:51:16.290 回答
1

函数内部的 for 循环Partition应写为：

for (var j = first_index; j < last_index; j++) {...}

代替

for (var j = 0; j < arr.length-1; j++) {...}

0从to循环arr.length-1使它在原始数组中创建新元素，而不是仅仅交换它们。

于 2013-09-06T22:54:01.960 回答
0

SPOILER ALERT - 这个小提琴有一个快速排序的工作版本。我对你的版本有点挣扎，所以我写了自己的。

像快速排序这样的算法为错误提供了很多机会（很多地方要差一个，等等）

作为一般建议，您可能希望通过仅传递数组来调用快速排序方法：

function quick_sort(array) {
    qsort(array, 0, array.length);
    console.log(array);
}

希望这可以帮助

http://jsfiddle.net/mwa4G/

http://en.literateprograms.org/Quicksort_(JavaScript)

于 2013-09-06T22:41:28.680 回答