快速排序和sort——不稳定排序的举例

只要把 if(x.s.length()==y.s.length())return x.k

提交之后挂了，于是我得到了这个用例

"Jlhvvd wfwnphmxoa qcuucx qsvqskq cqwfypww dyphntfz hkbwx xmwohi qvzegb ubogo sbdfmnyeim tuqppyipb llwzeug hrsaebveez aszqnvruhr xqpqd ipwbapd mlghuuwvec xpefyglstj dkvhhgecd kry"

把它转化为长度数组：6 10 6 7 8 8 5 6 6 5 10 9 7 10 10 5 7 10 10 9 3

利用我封装的sort输出ID的程序;

//给vector拓展，加上id并排序
template
bool cmp(T x,T y)
{return x
vector> sortWithId(vectorv)
{vector>ans;ans.resize(v.size());for(int i=0;ip1,pairp2){return cmp(p1.first,p2.first);});return ans;      
}

我输出了这个数组的排序ID：

看起来没毛病啊！

于是我把这个题目代码放本地运行：

结果是对的啊！

同一份代码，在OJ和本地运行结果不一样，只能是因为环境不一样，可能是编译器相关，也可能是库函数不一样。

4，STL版本

我想起来在我试图在网上搜索sort不稳定的用例的时候，我看到这样一篇博客：

stl中的sort内部的引用（源码剖析+自我实现）_永远鲜红の幼月的博客-CSDN博客

文中提到STL是有不同版本的，而且他贴出来的代码和我在vs2010里面看到的确实不一样。

所以我就想到，应该是因为OJ的sort函数和我本地的sort函数不一样。

进一步，OJ的sort函数肯定是不稳定排序，但我本地的sort函数呢？至少目前还没有找到不稳定的用例。

5，sort重写

为了利用OJ验证我本地的sort函数是不是稳定排序，我需要用我本地的sort函数替代OJ里面的sort函数。

经过简单的处理，我得到了这样的代码：

#define _STD	::std::
const int _ISORT_MAX = 32;#define _DEBUG_LT_PRED(pred, x, y)	pred(x, y)template inlinevoid _Insertion_sort(_BidIt _First, _BidIt _Last, _Pr _Pred){	// insertion sort [_First, _Last), using _Predfor(auto i=_First;i!=_Last;i++)for(auto j=i+1;j!=_Last;j++)if (!_DEBUG_LT_PRED(_Pred, *i, *j))_STD iter_swap(i, j);}
template inlinevoid _Med3(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Pr _Pred){	// sort median of three elements to middleif (_DEBUG_LT_PRED(_Pred, *_Mid, *_First))_STD iter_swap(_Mid, _First);if (_DEBUG_LT_PRED(_Pred, *_Last, *_Mid))_STD iter_swap(_Last, _Mid);if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First))_STD iter_swap(_Mid, _First);}template inlinevoid _Median(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Pr _Pred){	// sort median element to middleif (40 < _Last - _First){	// median of ninesize_t _Step = (_Last - _First + 1) / 8;_Med3(_First, _First + _Step, _First + 2 * _Step, _Pred);_Med3(_Mid - _Step, _Mid, _Mid + _Step, _Pred);_Med3(_Last - 2 * _Step, _Last - _Step, _Last, _Pred);_Med3(_First + _Step, _Mid, _Last - _Step, _Pred);}else_Med3(_First, _Mid, _Last, _Pred);}template inline_STD pair<_RanIt, _RanIt>_Unguarded_partition(_RanIt _First, _RanIt _Last, _Pr _Pred){	// partition [_First, _Last), using _Pred_RanIt _Mid = _First + (_Last - _First) / 2;_Median(_First, _Mid, _Last - 1, _Pred);_RanIt _Pfirst = _Mid;_RanIt _Plast = _Pfirst + 1;while (_First < _Pfirst&& !_DEBUG_LT_PRED(_Pred, *(_Pfirst - 1), *_Pfirst)&& !_Pred(*_Pfirst, *(_Pfirst - 1)))--_Pfirst;while (_Plast < _Last&& !_DEBUG_LT_PRED(_Pred, *_Plast, *_Pfirst)&& !_Pred(*_Pfirst, *_Plast))++_Plast;_RanIt _Gfirst = _Plast;_RanIt _Glast = _Pfirst;for (; ; ){	// partitionfor (; _Gfirst < _Last; ++_Gfirst)if (_DEBUG_LT_PRED(_Pred, *_Pfirst, *_Gfirst));else if (_Pred(*_Gfirst, *_Pfirst))break;else_STD iter_swap(_Plast++, _Gfirst);for (; _First < _Glast; --_Glast)if (_DEBUG_LT_PRED(_Pred, *(_Glast - 1), *_Pfirst));else if (_Pred(*_Pfirst, *(_Glast - 1)))break;else_STD iter_swap(--_Pfirst, _Glast - 1);if (_Glast == _First && _Gfirst == _Last)return (_STD pair<_RanIt, _RanIt>(_Pfirst, _Plast));if (_Glast == _First){	// no room at bottom, rotate pivot upwardif (_Plast != _Gfirst)_STD iter_swap(_Pfirst, _Plast);++_Plast;_STD iter_swap(_Pfirst++, _Gfirst++);}else if (_Gfirst == _Last){	// no room at top, rotate pivot downwardif (--_Glast != --_Pfirst)_STD iter_swap(_Glast, _Pfirst);_STD iter_swap(_Pfirst, --_Plast);}else_STD iter_swap(_Gfirst++, --_Glast);}}template inlinevoid _Sort2(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred){	// order [_First, _Last), using _Pred_Diff _Count;for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; ){	// divide and conquer by quicksort_STD pair<_RanIt, _RanIt> _Mid =_Unguarded_partition(_First, _Last, _Pred);_Ideal /= 2, _Ideal += _Ideal / 2;	// allow 1.5 log2(N) divisionsif (_Mid.first - _First < _Last - _Mid.second){	// loop on second half_Sort2(_First, _Mid.first, _Ideal, _Pred);_First = _Mid.second;}else{	// loop on first half_Sort2(_Mid.second, _Last, _Ideal, _Pred);_Last = _Mid.first;}}if (_ISORT_MAX < _Count){	// heap sort if too many divisions_STD make_heap(_First, _Last, _Pred);_STD sort_heap(_First, _Last, _Pred);}else if (1 < _Count)_Insertion_sort(_First, _Last, _Pred);	// small}template inlinevoid sort2(_RanIt _First, _RanIt _Last, _Pr _Pred){	// order [_First, _Last), using _Pred_Sort2((_First), (_Last), _Last - _First, _Pred);}

其中_Insertion_sort函数是我自己写的，其他是从我本地IDE移植过来的。

PS：原谅我写了一个选择排序

把题目里面的sort(v.begin(),v.end(),cmp);改成sort2(v.begin(),v.end(),cmp);提交，发现可以通过。

再把cmp比较函数里面的if(x.s.length()==y.s.length())return x.k

这是我们需要的sort不稳定的用例吗？显然不是！

6，稳定分支控制

sort是是快速排序、堆排序、插入排序三者的结合，其中快速排序、堆排序是不稳定排序，插入排序是稳定排序。

而被我改写之后，就变成的快速排序、堆排序、我的选择排序，选择排序是不稳定排序。

其中堆排序的分支在数据量很小时是调用不到的，所以我又把_Insertion_sort改写成了冒泡排序，这个是稳定排序：

template inlinevoid _Insertion_sort(_BidIt _First, _BidIt _Last, _Pr _Pred){	// insertion sort [_First, _Last), using _Predfor(auto i=_First;i!=_Last;i++)for(auto j=_First;j-_First<_Last-i-1;j++)if (_DEBUG_LT_PRED(_Pred, *(j+1), *j))_STD iter_swap(j, (j+1));}

再次提交，我得到了这个用例：

Npwfcxhzs diftsrym vzkdo uxwlha eyocyxo vdsdiyryer xqqghawjp rnpowjs wmqerrs egrriqsivq rvtlymg paecqitg klukaw otyerkmmnk chyenhxez trpge iqfcxax qwwpz amcnilipmj xwespxz jqzqbs riytunnotn ktbbursmxl xyqhan jitujj etkxlxdmx csljl zbbyu vxyntzvpa qrtufudlap hwhvjcjv yqfzij jlhet vuwiyf wozdclg xqegx kwyvqfwve lkchg oxxzctzolz efwrp xflitpgxl gwpiomzlh mcirgs uwkcquzu lxqtbe emyjgor fszjyon xwnopy gzni

把它长度提取出来：

9 8 5 6 7 10 9 7 7 10 7 8 6 10 9 5 7 5 10 7 6 10 10 6 6 9 5 5 9 10 8 6 5 6 7 5 9 5 10 5 9 9 6 8 6 7 7 6 4

还是用我的程序，调用sort并输出ID：

经过打断点确认了没有调用到堆排序，插入排序也是稳定的，所以这就是sort函数不稳定的用例。

准确的说，是sort函数里面的快速排序不稳定的用例。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！