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

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);}

感谢大家的回复！