UOJ Logo huangsi的博客

博客

用最短的代码实现排序

2018-01-08 18:42:11 By huangsi

问题描述:在如下的函数体中添加内容,使S(l,r)a[]中的lr位置进行排序。

void S(int l,int r){}

一开始我觉得选择排序已经够短了。就像这样:

void S(int l,int r){for(int i=l;i<r;i++)for(int j=i+1;j<=r;j++)if(a[i]>a[j])swap(a[i],a[j]);}

这样一共只用了93B,好像已经不能再优化了(可能再卡一卡还是能略微小一些的,但是大的优化是不多了)。

后来我有了一个诡异的想法,可以巧妙地利用递归:

void S(int l,int r){if(r==l+1){if(a[l]>a[r])swap(a[l],a[r]);}else if(r>l+1)S(l,r-1),S(l+1,r),S(l,r-1);}

这是什么原理呢。。。大家一看就明白了吧。如果序列长度小于2,我们直接不管它。如果长度就是2,我们比较a[l]a[r]。如果长度大于2,我们进行一个递归。首先,递归排序S(l,r-1),目的是让最大值不出现在第一个位置。其次,递归排序S(l+1,r),把最大值放到最后一个位置。这样,a[l]a[r-1]就只有第l到第r-1的数了。最后,再调用一次S(l,r-1),完成排序。当然,不要在意它的时间复杂度。(逃

可是这样反而变长了啊。。。那我们再优化一下:

void S(int l,int r){if(a[l]>a[r])swap(a[l],a[r]);if(r>l)S(l,r-1),S(l+1,r);}

我们把r==l+1的条件去掉了。这样省掉了一个if和一个else。同时,由于这样的比较已经保证了a[r]不可能是最小值,第一次递归过后最小值一定在a[l],于是第三次递归也就不需要了。此外,r>l+1的条件也可以换成r>l,没有什么影响。

这份代码只有75B,完虐选择排序。同时,时间复杂度由$O(3^n)$优化到了$O(2^n)$。

这个问题是不是已经有人研究过了啊?如果大家有想法的话也可以和我交流。以及,有没有人会一个比选择排序更短的多项式算法啊。。。

UPD:现在最短的代码74B:

void S(int l,int r){swap(a[a[l]>a[r]?l:r],a[r]);if(r>l)S(l,r-1),S(l+1,r);}

以及,用指针继续缩短到68B:

void S(int*l,int*r){swap(*(*l>*r?l:r),*r);if(r>l)S(l,r-1),S(l+1,r);}

感谢大家的回复!

评论

Marco_L_Tsien
@negiizhao
negiizhao
```c++ swap(a[a[l]>a[r]?l:r],a[r]); ```
AnzheWang
void S(int l,int r){sort(a+l,a+r+1);} //37B,多项式复杂度:O(n log n),完美解决你的要求。
AnzheWang
void S(int l,int r){for(;l<r;++l)for(int j=l;j<=r;swap(a[a[l]>a[j]?l:j],a[j++]));}//选择排序还能更短
mcfxmcfx
能用swap那是不是什么stl都能用啊(比如sort)
WrongAnswer
既然允许用swap,那么说明已经包含了STL并且引用了namespace std。所以这个代码确实是合法的: void S(int l,int r){sort(a+l,a+r+1);} 建议把题目改成不包含任何头文件,也不引用任何namespace,只允许修改S函数内的实现。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。