1

我正在尝试实现计数排序算法。基于算法简介中的伪代码（如果你不知道它只是一本书），我想出了这个代码：

var countingSort = function(array, array2, k){
    var a = [];
    a.length = k;
    for(var i in a){
        a[i] = 0;
    }
    for(var j in array){
        a[array[j]] += 1;
    }
    for(var i in a){
        a[i] += a[i - 1];
    }
    for(var j = array.length; j >= 0; j--){
        array2[a[array[j]]] = array[j];
        a[array[j]] -= 1;
    }
};

但是，当我使用该函数时，我的数组保持不变（我输入了所有参数！）如何解决这个问题？有人可以解释发生了什么吗？

4

1 回答 1

0

首先，您不应该for in简单地使用循环，因为它不仅会遍历数组中的元素，还会遍历Array对象的所有属性。这里有更多信息

在您的情况下，一个简单的 for 循环就足够了。

此外，您应该使用描述性名称，以便您（现在或稍后查看代码时）或其他人可以更清楚地理解代码。

我假设您程序中的变量含义如下：

  1. array存储要排序的初始数据。
  2. array2存储最终的排序列表。
  3. k是数组中的最大值（所有值都在 0..k 范围内）
  4. a是用于计算值的唯一出现次数的数组array

这些可以重命名为：

  1. 这个很好array
  2. array2可以重命名为sorted
  3. k可以重命名为max
  4. a可以重命名为count

您做错的另一件事是在最后一个 for 循环中。您正在开始循环，array.length但数组在 javascript 中的索引为 0，因此您的第一个值超出范围。你应该从array.length - 1.

至于设置a.length = k，这在 javascript 中是不必要的，因为数组是对象，而对象没有直接的长度概念。您可以在 javascript 中将数组视为动态列表。

添加所有声明的更改，您的代码如下所示：

function countingSort(array, sorted, max){
    var i, j;

    var count = [];

    // initialize counting array
    for(i = 0; i <= max; i++){
        count[i] = 0;
    }

    // count unique occurrences
    for(i = 0; i <= max; i++){
        count[array[i]] += 1;
    }

    // compute proper indices
    for(i = 1; i <= max; i++){
        count[i] += count[i - 1];
    }

    // sort
    for(i = array.length - 1; i >= 0; i--){
        sorted[count[array[i]] - 1] = array[i];
        count[array[i]] -= 1;
    }
}

运行示例：

var countingSort = function(array, sorted, max) {
  var i, j;

  var count = [];

  // initialize counting array
  for (i = 0; i <= max; i++) {
    count[i] = 0;
  }

  // count unique occurrences
  for (i = 0; i <= max; i++) {
    count[array[i]] += 1;
  }

  // compute proper indices
  for (i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }

  // sort
  for (i = array.length - 1; i >= 0; i--) {
    sorted[count[array[i]] - 1] = array[i];
    count[array[i]] -= 1;
  }
}

document.getElementById("button").onclick = function() {
  var i, array, max, sorted = [];

  array = document.getElementById("input").value.split(',');
  // convert strings to numbers
  for (i = 0; i < array.length; i++) {
    array[i] = +array[i];
  }
  // find max
  var max = Number.MIN_VALUE;
  for (i = 0; i < array.length; i++) {
    if (max < array[i]) {
      max = array[i];
    }
  }
  countingSort(array, sorted, max);
  document.getElementById("result").value = sorted;
}
input {
  width: 100%;  
  margin: 10px 0;
  padding: 10px;
  border: 1px solid #018bbc;
  border-radius: 5px;  
}
<input type="text" id="input" placeholder="Enter comma separated list of integers">
<button type="button" id="button">Sort</button>
<input type="text" id="result" disabled placeholder="Sorted array is displayed here...">

此外，这是一个计数排序的版本，恕我直言，它似乎比上面的一般方法更直观、更简单：

var countingSort = function(array, sorted, max) {
  var i, j, count = [];

  // initialize counting array
  for (i = 0; i <= max; i++) {
    count[i] = 0;
  }

  // count unique occurences
  for (i = 0; i < array.length; i++) {
    count[array[i]] ++;
  }

  // sort
  for (i = 0, j = 0; i <= max; i++) {
    while (count[i] > 0) {
      sorted[j++] = i;
      count[i] --;
    }
  }
};

于 2015-03-29T04:18:27.087 回答