javascript - 在数组的 2/3 上调用自身的排序算法

Question

我尝试实现一个排序算法，其工作方式如下:给定一个长度为 n 的数组，该算法应该在前 2/3 递归调用自身，然后在最后 2/3 上再次调用数组的前 2/3。在每次调用时，算法应该在查看两个或更少元素时对当前数组进行排序并退出。该方法应将数组 A 和两个索引作为参数。

所以这里的主要困难是创建代表数组 2/3 的索引。我的想法是执行 x = Math.floor((i-j)/3) 这样 x 是第一个 1/3 和第二个 1 中的元素数/3。因此前 2/3 可以由 [i,x*2] 界定，最后 2/3 由 [x+1,j] 界定。你认为这个想法有什么错误吗？

我想出了以下算法，但排序不正确。所以算法或上面的想法都有缺陷。有什么问题吗？

var threeSort = function(A,i,j) {

  var diff = j-i;

  if (diff <= 2) {
        if (A[j] < A[i]) {
        var tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
      }
      return;
  }

  var x = Math.floor(diff/3);

  threeSort(A,i,x*2);
  threeSort(A,x+1,j);
  threeSort(A,i,x*2);
};

var arr = [3,4,1,4,2];
threeSort(arr, 0, arr.length-1);

https://jsfiddle.net/jyqyhxko/2/

Answer 1

var diff = j-i;
if (diff <= 2) {

假设 i = 0, j = 2。范围 0..2 包含 3 个项目，

进行此更正以避免对双元素片段进行递归排序:

if (diff < 2) {

下一期:您的 x 是相对偏移。要获取递归调用的绝对索引，您可以像

一样使用它

if (j-i < 2){
  if (A[j] < A[i]) {
    var tmp = A[i];
    A[i] = A[j];
    A[j] = tmp; 
  };
  return;
};

var d = Math.floor((j - i + 1) / 3);

threeSort(A,i,j-d);
threeSort(A,i+d,j);
threeSort(A,i,j-d);

fiddle