Re: [問題] 關於在這種情況之下sort的複雜度

[loveme00835 (恋さや)]

根據你說的兩個題目的特性 :

→ lO:其實我例子舉得不好 負數是連在一起沒錯 但是不一定只有一段
→ lO:正數一定是連續且排序的 只不過也是一段一段的

再回頭看看你給的例子 :

1,2,3,4,5,6,7,8,-5,-6,-7,-4,-2,-8,-1,9,10,11,12,13,14,15

可以把正數、負數分開蒐集起來, 各自形成新的序列

正序列 : 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
負序列 : -5,-6,-7,-4,-2,-8,-1

掃描的過程, 時間複雜度為 O( n ). (假設原本的序列長度為 n)

上面的正序列已經排過了, 所以不要對他做任何處理, 我們只需要排負序
列的部份, 這時候如果只是單純要排整數, 用快速排序就能解決了, 假設
負序列的長度為 w, 排序的總時間複雜度只有 O( wlogw )

最後最後, 你要的結果應該是 : "排序後的負序列" | "正序列" 兩序列
接起來的結果, 這個步驟時間複雜度是 O( n )

總共的時間複雜度為 : O( n ) + O( wlogw ) + O( n ), 這時候就由負
數佔原序列的比例來決定程式的執行速度了

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.121.197.115
※ 編輯: loveme00835     來自: 140.121.197.115      (06/28 17:32)
推 lO:感謝你^^ 看到這篇我也剛好寫完了
→ loveme00835:你最後選擇的是 0.0 ?
推 lO:其實...因為情況有點特殊0.0
→ lO:我要sort的是一個二維陣列 但是是形狀很畸形的二維陣列
→ lO:是以二維陣列的頭來當作sort標準
→ lO:但是除了mergeSort之外 其他的好像都是要"交換"
→ lO:每一個row的size都不一樣 實在不知道怎麼交換
→ lO:所以只好用mergesort了 複製值的時候再malloc..
推 lO:真是抱歉>"<
→ loveme00835:XD