这是一个合法的快速排序实现吗?它的复杂性是什么?

Is this a legit Quicksort implementation, and what is its complexity?

本文关键字：实现 快速排序 是什么 复杂性 一个      更新时间：2023-09-26

我试图编写一个快速排序程序，下面是我的结果。它是用Javascript编写的，它会对列表进行排序。然而，我意识到我在网上看到的大多数快速排序算法与此非常不同，感觉我的算法与我在网上看到的相比太容易编程了，因此我很怀疑。

我完全意识到这个算法在内存方面是非常低效的，因为它创建了新的列表(新的内存分配)，而不是进行就地排序。但我更感兴趣的是把这个算法教给我的朋友，这就是为什么我要编一个尽可能简单的程序。我的问题是，这是快速排序算法的合法(正确的实现)吗?或者它还有别的作用?(请记住:我不是在问这是否有效，因为我知道它不是!)

这个算法的复杂度是多少?我试着计算它，我的分析是:在每个迭代中,假设列表(左和右)都有同等数量的元素,这产生一个递归树深度logN和因为在树的每一层,如果我们总结所有的数组遍历,我们最终得到的N迭代,然后,这意味着每一个层面上,我们有N迭代,因此O (N Log N)的复杂性。是最好的情况,而最坏的情况下当树变得不平衡由于糟糕的分区,最终在O(N^2)复杂性。这种分析正确吗?

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));
}

平均情况性能0 (n log n)最坏情况空间复杂度O(n) auxiliary (naive) O(log n) auxiliary (Sedgewick 1978)

是的，这是一个被广泛接受的快速排序函数版本。

考虑用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两组，然后对每一组进行递归排序，再进行拼接。平均情况是O(nlogn)，最坏情况是O(n2)。

相关问题:为什么极简主义，例如Haskell快速排序不是一个"真正的"快速排序?

我觉得你的实现很简洁，很容易理解。很好，足够教你的朋友了!平均性能为O(NlogN)，最差性能为O(N^2)

有许多不同的版本选择"枢轴"或改进你提到的。

下面是快速排序的另一个"就地"版本。

 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)
相关文章：