[問卦] 有沒有史達林排序法的八卦？

[muse87131 ()]

排序演算法百百種

Merge Sort
Quick Sort
Bubble Sort

但我看過最屌的是Stalin Sort，時間複雜度只有O(n)。

直接iterate array，把不符合順序的element除掉，剩下的element就都保證是排序好的
。

人家這還是stable sort 喔

FUNCTION stalinSort(arr)
    IF length(arr) <= 1 RETURN arr

    newArr = [arr[0]]
    maxVal = arr[0]

    FOR i FROM 1 TO length(arr) - 1:
        IF arr[i] >= maxVal:
            // Element is in order, let it live
            APPEND arr[i] TO newArr
            maxVal = arr[i] // Update the standard
        ELSE:
            // Element is not in order, eliminate it
            CONTINUE

    RETURN newArr

有沒有史達林排序法的八卦？



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.45.155.93 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1773550107.A.62E.html
→ Forcast: 大整肅
→ Forcast: 後來中風
噓 deepdish: 作業自己做
→ tom77588: 把不聽話的刪掉，剩下的就會變成想要的
噓 kingstongyu: 很厲害嗎?!用ASSEMBLY寫啊~~