我們可以稱這個函數爲快速排序嗎

Question

我發現這個函數是用python寫在互聯網上的，我很困惑，如果它是一個快速排序或不是因爲它被寫入一行而且它工作的很好很快，我認爲它與O（N * log n）的，即使在最壞情況下的複雜工作，所以這是代碼：

def qsort(L): 
    return (qsort([x for x in L[1:] if x < L[0]]) +\ 
      L[0:1] + \ 
      qsort([x for x in L[1:] if x >= L[0]])) if L else [] 

Answer 1

是的，它是快速排序，因爲它的完美匹配算法定義：拿起從任意一個元素列表中，將低於此元素的值移動到列表的開頭（選定元素之前）並遞歸執行快速排序：

qsort([x for x in L[1:] if x < L[0]]) 

然後

更大或相等的值的列表（選擇後元件）的端部，並執行快速排序遞歸

qsort([x for x in L[1:] if x >= L[0]]) 

如果列表爲空（遞歸終止）當然結果是空列表。