爲什麼我的Shell排序很慢？

我試圖在JavaScript中實現一堆排序算法，我無法弄清楚爲什麼我的shell排序非常慢。它比我的合併排序慢6倍，只比我的插入排序快一點。我在網上看到了另一個實現，但我更關注於使其清晰易讀（因爲我有一個面向noob的博客），更快的實現對我來說太簡明瞭。關於如何保持總體規劃但讓它更快運行的任何想法？爲什麼我的Shell排序很慢？

var shellSort = function(list) { 
    var gapSize = Math.floor(list.length/2); 

    while(gapSize > 0) { 
     _shellInsertionSort(list, gapSize); 
     gapSize = Math.floor(gapSize/2); 
    } 

    return list; 
    }; 

    function _shellInsertionSort(list, gapSize) { 
    var temp, i, j; 

    for(i = gapSize; i < list.length; i += gapSize) { 
     j = i; 
     while(j > 0 && list[ j - gapSize ] > list[j]) { 
     temp = list[j]; 
     list[j] = list[ j - gapSize ]; 
     list[ j - gapSize ] = temp; 
     j -= gapSize; 
     } 
    } 
    };

我歸併排序：

var mergeSort = function(list) { 
    if (list.length <= 1) { 
     return list; 
    } 

    var left = [], 
     right = [], 
     middle = Math.floor(list.length/2), 
     i; 

    for(i = 0; i < middle; i++) { 
     left.push(list[i]); 
    } 

    for(; i < list.length; i++) { 
     right.push(list[i]); 
    } 

    left = mergeSort(left); 
    right = mergeSort(right); 

    return _merge(left, right); 
    }; 

    function _merge(left, right) { 
    var result = []; 

    // Should be able to just get rid of arguments in while loop 
    while(left.length || right.length) { 
     if(left.length > 0 && right.length > 0) { 
     if(left[0] <= right[0]) { 
      result.push(left.shift()); 
     } else { 
      result.push(right.shift()); 
     } 
     } 
     else if(left.length) { 
     return result.concat(left); 
     } 
     else { 
     return result.concat(right); 
     } 
    } 
    }

我的測試：

var testSpeed = function(testSize, rounds) { 
    var testArrays = [], 
     algorithms = Array.prototype.slice.call(arguments, 2), 
     results = [], 
     i, j; 

    for(i = 0; i < rounds; i++) { 
     testArrays[i] = []; 
     for(j = 0; j < testSize; j++) { 
     testArrays[i].push(Math.ceil(Math.random() * testSize)); 
     } 
    } 

    for(i = 0; i < algorithms.length; i++) { 
     for(j = 0; j < rounds; j++) { 
     if(!results[i]) { 
      results[i] = []; 
     } 
     results[i].push(testAlgorithm(algorithms[i], testArrays[j])); 
     } 
    } 

    return results; 
    }; 

    var testAlgorithm = function(algorithm, set) { 
    var clone = set.slice(), 
     start = new Date().getTime(), 
     end; 

    algorithm(clone); 

    end = new Date().getTime(); 

    return end - start; 
    };

來源

2014-02-28 EmptyArsenal

這可能是更適合http://codereview.stackexchange.com/。 –

在最糟糕的情況下，您的差距序列的shell排序是二次的，那麼您爲什麼認爲它不應該比合並排序慢呢？ –

儘管我根本不徹底檢查你的代碼（代碼審查可能是一個更好的地方，要求代碼審查），我相信你正在使用的差距順序不是很好;不像其他間隙序列，它具有O（N^2）最差情況下的時間複雜度。 – rici

我把你的算法一起，做了一個功能簡單的樣品它，記錄時間（與米利斯（）代替你如何測試它，我不明白）並輸出平均時間。 Shell排序爲0.02毫秒100號的數組..未考慮到大多數毫秒錄音與殼排序地板（因爲它有時0）帳戶。我做了歸併排序相同，這是0.21毫秒..希望這回答了它https://www.khanacademy.org/computer-programming/sort-algorithms/6199294078746624

來源

2015-02-14 20:54:50

將代碼包含在您的答案中。 –

爲什麼我的Shell排序很慢？

回答

相關問題