作者lO (今天早上)
看板Prob_Solve
标题[问题] 关於在这种情况之下sort的复杂度
时间Mon Jun 28 14:51:36 2010
假设我现在要将一堆资料做排序(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
1F：→ tkcn:只排序负数那段，在整段搬到最前面就好啦 06/28 15:30
2F：→ bleed1979:关键应该是"负数在哪以及有多少个完全没办法知道" 06/28 15:34
3F：→ lO:其实我例子举得不好 负数是连在一起没错 但是不一定只有一段 06/28 15:39
4F：→ lO:正数一定是连续且排序的 只不过也是一段一段的 06/28 15:40
5F：推 tkcn:那就把负数全搬到前面在排序呀。把排序好的跟没排序混在一起 06/28 15:50
6F：→ tkcn:，怎样也不可能比分开来快。 06/28 15:51
7F：推 FRAXIS:如果未排序元素所占的比例很低 用insertion sort就可以了吧 06/28 16:46
8F：→ yoco315:这刚好是 flashsort 的适用领域, 对你这 case 应该有 O(n) 06/28 20:22