【CPP】排序的稳定性

【CPP】排序的稳定性

排序的稳定性： 如果两个元素的数值相等，那么在排序之后两者的相对位置不会发生变化（A在B前面，排序之后，A还是在B前面），这样的特性称之为“稳定”。 经典例子： 稳定的排序：冒泡排序、插入排序、归并排序等 不稳定的排序: 快速排序、堆排序等

不稳定排序，以快速排序为例做演示，他的核心思想是分治： 1、 先从序列中取出一个数作为basic number。 2、将比此数大的元素放到它的右边，小于或等于它的元素放到它的左边。 3、对左右区间重复第二步，直到各区间只有一个数为止。

实验例子： 创建Tree结构体类型，里面有编号，树的高度。以高度为基准进行排序。

#include #include #include using namespace std;struct Tree{ int number; int height; Tree(const int _number, const int _height) { number = _number; height = _height; } friend ostream& operator << (ostream &out, Tree &object) { out << "(" << object.number << ", " << object.height << ")"; return out; }};int main(){ std::vector vec; for( int i = 0; i < 10; ++i ) { int randomHeight = (i+1)*10; if( i&1 ) { randomHeight = 0; } vec.push_back( Tree(1+i, randomHeight) ); } for(auto it: vec) { cout << it << "\t"; } cout << endl; sort( vec.begin(), vec.end(), //冒泡排序的分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 [](const Tree t1, const Tree t2)->bool { if( t1.height <= t2.height ) return true; return false; } ); for(auto it: vec) { cout << it << "\t"; } cout << endl;}

output:

(1, 10) (2, 0) (3, 30) (4, 0) (5, 50) (6, 0) (7, 70) (8, 0) (9, 90) (10, 0) (10, 0) (8, 0) (6, 0) (4, 0) (2, 0) (1, 10) (3, 30) (5, 50) (7, 70) (9, 90)

height为0的元素相对位置发生了变化。 稳定的排序，以冒泡排序为例，接着上面的场景：

for( int i = 0; i < 10; ++i ) { for( int j = 0; j < 10 - i -1; ++j ) { if( vec[j].height > vec[j+1].height ) { swap( vec[j], vec[j+1] ); } } }

output：

(1, 10) (2, 0) (3, 30) (4, 0) (5, 50) (6, 0) (7, 70) (8, 0) (9, 90) (10, 0) (2, 0) (4, 0) (6, 0) (8, 0) (10, 0) (1, 10) (3, 30) (5, 50) (7, 70) (9, 90)

在这里，C++提供了结构体拷贝构造函数，所以swap得以顺利work。 下面的swap实现版本来自 ​​​inline _LIBCPP_INLINE_VISIBILITY#ifndef _LIBCPP_HAS_NO_ADVANCED_SFINAEtypename enable_if< is_move_constructible<_Tp>::value && is_move_assignable<_Tp>::value>::type#elsevoid#endifswap(_Tp& __x, _Tp& __y) _NOEXCEPT_(is_nothrow_move_constructible<_Tp>::value && is_nothrow_move_assignable<_Tp>::value){ _Tp __t(_VSTD::move(__x)); __x = _VSTD::move(__y); __y = _VSTD::move(__t);}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。