排序算法，它自己在一個數組的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]和[x+1,j]的最後2/3限定。你覺得這個想法有什麼錯誤嗎？

我想出了下面的算法沒有正確排序，所以算法或上面的想法都有缺陷。你有沒有看到任何問題？

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,1，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