计数排序数组值没有改变

Question

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

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;
    }
};

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

Answer 1

首先，简而言之，您不应该使用 for in 循环，因为它不仅遍历数组中的元素，而且遍历 Array 上的所有属性目的。 Here's more info

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

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

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

array存放待排序的初始数据
array2 存储最终的排序列表。
k 是数组中的最大值（所有值都在 0..k 范围内）
a 是用于计算 array

这些可以重命名为：

这个很好 array
array2可以重命名为sorted
k可以重命名为max
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] --;
    }
  }
};

计数排序数组值没有改变

Counting Sort array values aren't changing

javascript

arrays

sorting

array-algorithms

counting-sort