数据结构考试复习（2）

发表于   |  

关于排序问题，通常题目会设定一种“排序”的方法，我们直接通过模拟就可以完成。

直接的排序算法有很多，老师主要教会我们stl中的排序函数sort().

另外，stl中还有关于全排序的函数next_permutation()，以及涉及字符串翻转的函数reverse().

##0X00 sort()
如何使用sort()对数据进行排序

#include <algorithm>

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Sorts the elements in the range [first,last) into ascending order. The elements are compared using operator< for the first version, and comp for the second.

Examples:

1
2
3
vector<int> myvector
sort (myvector, myvector+3);
sort (myvector.begin(), myvector.end(), myfunction);

但是如果你时自己定义的类型或者你需要按照其他方式排序，有两种方法来达到效果：一种是自己写比较函数。另一种是重载类型的’<’操作符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class myclass {
public:
    int first， second;
    bool operator < (const myclass &m)const {
        return first < m.first;
    }//ascending order by first
};
vector< myclass > vect;
sort(vect.begin(), vect.end());

----------------------------------------------------

bool cmp(const myclass & m1, const myclass & m2) {
    return m1.second < m2.second;
}//ascending order by second
sort(vect.begin(), vect.end(), cmp);

参考：[http://www.cppblog.com/mzty/archive/2005/12/15/1770.html]

##0X01 reverse()
reverse() can reverse the vector/string

void reverse (BidirectionalIterator first, BidirectionalIterator last);

Reverses the order of the elements in the range [first,last).

And we need to include <algorithm>

Example:

1
2
3
std::vector<int> myvector;
for (int i=1; i<10; ++i) myvector.push_back(i);   // 1 2 3 4 5 6 7 8 9
std::reverse(myvector.begin(),myvector.end());    // 9 8 7 6 5 4 3 2 1

##0X02 next_permutation()
next_permutation()和prev_permutation()
分别是求一个序列的下一个排列和前一个排列。

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);
The range used is [first,last)
we need include <algorithm>
如果存在下一个序列，则返回True，同时将序列变为其下一个排列。

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int myints[] = {1,2,3};
do {
    std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
} while (next_permutation(myints,myints+3) );
cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';

Output:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
After loop: 1 2 3