2010年8月18日星期三

不能在偏序集上排序


bool myfunction (int i,int j) { return (i==4) && (j ==2); }



int main() {

   {

       {

       std::vector<int> x(4);

       for(int i=0;i<4;++i)x[i] = (i + 1);

       for(int i=0;i<4;++i)printf("%d,", x[i]);

       printf("\n");

       std::stable_sort(x.begin(), x.end(), myfunction);

       for(int i=0;i<4;++i)printf("%d,", x[i]);

       printf("\n");

       }

       {

       std::vector<int> x(4);

       for(int i=0;i<4;++i)x[i] = (i + 1);

       x[0]=2;

       x[1]=4;

       for(int i=0;i<4;++i)printf("%d,", x[i]);

       printf("\n");

       std::stable_sort(x.begin(), x.end(), myfunction);

       for(int i=0;i<4;++i)printf("%d,", x[i]);

       printf("\n");

       }

       return 0;

   }



Result



1,2,3,4,

1,2,3,4,

2,4,3,4,

4,2,3,4,





http://middleangle.com/rif/derifatives/Home/13/sorts-and-partial-orderings

[12:32:59] wangyuantao: 构造了一个反例,不能排序。序列1,2,3,4,只定义4<2,按照归并排序,结果还是1,2,3,4

[12:33:07] 翟倩(Zhai Qian): 这是谁的blog啊

[12:33:18] wangyuantao: 不认识google出来的

[12:47:14] wangyuantao: 关于偏序集上的排序和TopN算法,这篇文章被引用的比较多

http://www.siam.org/proceedings/soda/2009/SODA09_044_daskalakisc.pdf

光看了摘要,貌似最好的结果也不保证最坏情况下的复杂度比O(n^2)好。所以,就按照目前的实现两两比吧

发送自 HTC



没有评论: