這是一個合法的Quicksort實現，它的複雜性是什麼？

我試圖編寫一個快速排序，這裏是我的結果。它在Javascript中，它定義了列表。然而，我意識到我在網上看到的大多數Quicksort算法都與此截然不同，感覺就像我的算法編程太容易，與我在網上看到的算法相比，因此我感到懷疑。這是一個合法的Quicksort實現，它的複雜性是什麼？

我完全知道這個算法在內存方面效率非常低，因爲它會創建新的列表（新的內存分配），而不是進行就地排序。但是我更感興趣的是將這種算法教給朋友，這就是爲什麼我想盡可能編程最簡單的版本。所以我的問題是，這是Quicksort算法的合法（正確實施）嗎？或者它做了別的事情？（記住：我不是問這是否有效，因爲我知道它不是！）

另外，這種算法的複雜性是什麼？我試圖計算它，我的分析是：在每次迭代中，假設兩個列表（左側和右側）具有相同數量的元素，這會生成一個深度爲logN的遞歸樹，並且因爲在樹的每個級別中，對所有的數組遍歷進行總結，最後進行N次迭代，這意味着對於每個級別，我們都有N次迭代，因此複雜度爲O（N Log N）。這是最好的情況，最糟糕的情況是由於分區錯誤導致樹不均衡，最終導致複雜性下降。這種分析是否正確？

function quicksort(list){ 


    var size = list.length; 


    // Base cases 
    if(size == 0) return [];  
    if(size == 1) return [list[0]]; 


    // Get the pivot as the middle element 
    var middle = Math.floor(size/2);  
    var pivot = list[middle]; 

    // Init two lists. Left = less than pivot. Right = greater than pivot. 
    var list_left = []; 
    var list_right = []; 


    // Push every element of the list into either the left or right list 
    for(i=0; i<size; i++){  

     if(i == middle) continue; // Skip the pivot 


     if(list[i] <= pivot) 
      list_left.push(list[i]); 
     else   
      list_right.push(list[i]); 
    } 

    // Return the concatenation of the quicksorted left list 
    // pivot, and quicksorted right list (here's the recursion) 

    return quicksort(list_left).concat(pivot).concat(quicksort(list_right)); 

}

來源

2016-09-27 Felo Vilches

這似乎是正確的，但很簡單（可能是最簡單的）快速排序的實現。看來你意識到了太大的空間複雜性，所以我不會去那裏。你的Big-O似乎也是正確的。順便說一句，爲了簡單起見，如果這是你正在尋找的東西，那麼'middle' pivot可以用數組的第一個或最後一個元素替換。 –

是的，這是一個非常廣泛接受的Quicksort功能版本。

考慮一個版本快速排序的寫入在Haskell（從Learn You A Haskell截取）：

quicksort :: (Ord a) => [a] -> [a] 
quicksort [] = [] 
quicksort (x:xs) = 
    let smallerSorted = quicksort [a | a <- xs, a <= x] 
     biggerSorted = quicksort [a | a <- xs, a > x] 
    in smallerSorted ++ [x] ++ biggerSorted

首先元件被劃分成兩組：smallerSorted和biggerSorted，然後每個分區被遞歸排序，然後concatenated。平均情況是O（nlogn），最壞的情況是O（n ）。

來源

2016-09-27 00:34:50 4castle

-1

平均情況下的性能爲O（n log n）的最壞情況下的空間複雜度爲O（n）輔助（幼稚）O（log n）的輔助（塞奇威克1978）

來源

2016-09-27 00:35:07 peterbest69

我想您的實施非常簡單易懂。這很好，足以教你的朋友！平均性能是O（NlogN），最壞的情況是O（N^2）

有許多不同的版本選擇「pivot」或改進的，正如你所提到的。

下面是quicksort的另一個「in-place」版本。

function partition(a, left, right, pivotIndex) 
pivotValue := a[pivotIndex] 
swap(a[pivotIndex], a[right]) 
storeIndex := left 
for i from left to right-1 
    if a[i] <＝ pivotValue 
     swap(a[storeIndex], a[i]) 
     storeIndex := storeIndex + 1 
swap(a[right], a[storeIndex]) 
return storeIndex 

procedure quicksort(a, left, right) 
if right > left 
    select a pivot value a[pivotIndex] 
    pivotNewIndex := partition(a, left, right, pivotIndex) 
    quicksort(a, left, pivotNewIndex-1) 
    quicksort(a, pivotNewIndex+1, right)

來源

2016-09-27 00:42:52 HappyHal

這是一個合法的Quicksort實現，它的複雜性是什麼？

回答

相關問題