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

[lO (今天早上)]

假設我現在要將一堆資料做排序(int)
但是這些資料只有一部分是沒有排序到的
EX:

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


簡單來說其實就是只要把那堆負數抓出來排序完丟到最前面
但是負數在哪以及有多少個完全沒辦法知道

在這種情況之下哪一種排序最好呢?


我自己的想法是merge sort
因為好像要交換的case不多@@?


我也不是很清楚 所以上來問問大家

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.132.15.156
※ 編輯: lO              來自: 220.132.15.156       (06/28 14:52)
※ lO:轉錄至看板 C_and_CPP                                         06/28 14:52
→ tkcn:只排序負數那段，在整段搬到最前面就好啦
→ bleed1979:關鍵應該是"負數在哪以及有多少個完全沒辦法知道"
→ lO:其實我例子舉得不好 負數是連在一起沒錯 但是不一定只有一段
→ lO:正數一定是連續且排序的 只不過也是一段一段的
推 tkcn:那就把負數全搬到前面在排序呀。把排序好的跟沒排序混在一起
→ tkcn:，怎樣也不可能比分開來快。
推 FRAXIS:如果未排序元素所佔的比例很低 用insertion sort就可以了吧
→ yoco315:這剛好是 flashsort 的適用領域, 對你這 case 應該有 O(n)