如何在 Node.js 上编写 shell 排序

Question

我正尝试在 Node.js 上编写 shell 排序，就像算法书第 4 版中那样。塞奇威克，韦恩。 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;
}

和 shell 排序无效：mocha test screenshot

Answer 1

在 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

Answer 2

如果您使用 h = h / 3，您的 h 可能会变成浮点数。请尝试 h = Math.floor(h / 3);。

如何在 Node.js 上编写 shell 排序

How to write shell sort on Node.js

javascript

sorting

node.js

shellsort

在 Javascript