文章/答案/技术大牛

发布

社区首页 >问答首页 >在数组的2/3上调用自己的排序算法

问在数组的2/3上调用自己的排序算法
EN

Stack Overflow用户

提问于 2016-05-15 16:03:42

回答 1查看 99关注 0票数 0

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

因此，这里的主要困难是创建表示数组的2/3的索引。我的想法是做x = Math.floor((i-j)/3)，使x是前1/3和第2 1/3中的元素数。所以前2/3可以被[i,x*2]限制，最后2/3可以被[x+1,j]限制。你看到这个想法有什么错误吗？

我想出了以下算法，它没有对correctly.So进行排序，无论是算法还是上面的想法都有缺陷。你看到什么问题了吗？

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/

arrays

algorithm

sorting

javascript

回答 1

Stack Overflow用户

回答已采纳

发布于 2016-05-15 16:56:32

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

假设i= 0，j=2.range 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);

小提琴

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/37240531

复制

相似问题

问在数组的2/3上调用自己的排序算法
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在数组的2/3上调用自己的排序算法EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在数组的2/3上调用自己的排序算法
EN