0

我正在尝试在 Node.js 上编写 shellsort，就像在 Algorithms, 4th ed 一书中一样。塞奇威克，韦恩。那里有所有用 Java 编写的示例。

这是我的模块：

"use strict";

module.exports = (function() {

  function sort(array) {
    let size = array.length;
    let h = 1;
    while(h < size/3) {
      h = h * 3 + 1;
    }
    while(h >= 1) {
      for(let i = h; i < size; i++) {
        for(let j = i; j >= h && less(array, j, j-h); j = j-h) {
          exch(array, j, j-h);
        }
      }
      h = h/3;
    }
  }

  function less(array, i, min) {
    return array[i] < array[min];
  }

  function exch(array, i, min) {
    let temp = array[i];
    array[i] = array[min];
    array[min] = temp;
  }

  return {
    sort: sort
  };

})();

我使用 mocha 和 chai 来测试这个功能：

function isSorted(array) {
  for(let i = 1, size = array.length; i < size; i++) {
    if (array[i] < array[i-1]) {
      return false;
    }
  }
  return true;
}

和外壳排序不起作用：摩卡测试屏幕截图

4

2 回答 2

0

Javascript中shell排序算法的实现

function shellSort(arr){
    
    var len  = arr.length;
    var gapSize =  Math.floor(len/2);
 
    while(gapSize > 0){
        for(var i = gapSize; i < len; i++) {
 
            var temp = arr[i];
            var j = i;
 
            while(j >= gapSize && arr[j - gapSize] > temp) {
                arr[j] = arr[j - gapSize];
                j -= gapSize;
            }
            arr[j] = temp;
        }
        gapSize = Math.floor(gapSize/2);
    }
    return arr;
}

function isSorted(array) {
  for(let i = 1, size = array.length; i < size; i++) {
    if (array[i] < array[i-1]) {
      return false;
    }
  }
  return true;
}

 
var randomArray = [45,86,3,5,97,95,4,24,7,88,93,27,45,90,54,89,74,5,90,73,74,857,834,8394,4231,485,32,54,674,12];
var mySortedArray = shellSort(randomArray);

console.log(mySortedArray);
console.log(isSorted(mySortedArray));

输出：

[3, 4, 5, 5, 7, 12, 24, 27, 32, 45, 45, 54, 54, 73, 74, 74, 86, 88, 89, 90, 90, 93, 95, 97, 485, 674, 834, 857, 4231, 8394]
true
于 2016-01-23T19:01:52.537 回答
0

如果你使用 .你h可能会变成一个浮点数h = h / 3。试试h = Math.floor(h / 3);吧。

于 2016-01-23T19:15:59.537 回答