首页 > 代码库 > [草稿]std::sort
[草稿]std::sort
本章描述C++泛型算法sort的设计和使用。
个人认为，排序相关的泛型算法是C++中相对比较复杂的部分。
sort的内部实现并不是固定的，在不同版本的C++中，采用的排序算法可能是不同的，但是最坏时间复杂度必须是O(n log n)。
GNU Standard C++ library采用了三步混合排序方式：首先使用内省排序（本身采用快速排序和堆排序的混合），然后使用插入排序。
参见：http://en.wikipedia.org/wiki/Sort_(C%2B%2B)
(关于内省排序，参见：http://zh.wikipedia.org/wiki/%E5%86%85%E7%9C%81%E6%8E%92%E5%BA%8F)
或许是因为实现方法不固定，C++官方网站也并没有提供相关的实现方法。
我们先来看看C++官方网站上对sort的描述
http://www.cplusplus.com/reference/algorithm/sort/
（注：以下内容是我对C++官方网站上内容的理解，不准确的地方请见谅）
- sort函数的声明：
sort函数有两种形式，
一种是默认采用operator<进行比较的形式：
template <class RandomAccessIterator>void sort (RandomAccessIterator first, RandomAccessIterator last);
一种是采用自定义比较方式的形式：
template <class RandomAccessIterator, class Compare>void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
所以，如果你想对自定义类型的一组数据将进行排序，那么你有两种选择：1. 重载operator<; 2.采用第二种形式。
- sort函数的作用：
对[first,last)序列中的元素进行排序（如果采用上边的第一种方式，则按降序排列）。
非稳定排序，即 相等的两个元素，在排序之后并不能保证其原来的先后循序。（如果需要稳定排序，请采用stable_sort）。
其他内容（还不够详细）：
- sort函数的时间复杂度：
最差时间复杂度 O(n log n)
- sort函数的排序方式：
非稳定排序（如果需要稳定排序，请采用stable_sort）。
不同版本的C++中，sort采用的排序算法可能是不同的。GNU采用内省排序和插入排序的混合方式。
以下是我写得一个简单的例子
#include <algorithm>#include <iostream>#include <vector>using std::cout;using std::endl;using std::vector;class Whatever{public: Whatever(int size, char name) : mSize(size), mName(name) {} int getSize() { return mSize; } char getName() { return mName; } bool operator< (const Whatever& what) const { return (this->mSize < what.mSize); }private: int mSize; char mName;};void print(vector<int> vec){ for (vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++) { cout << *iter << ‘ ‘; } cout << endl;}void print(vector<Whatever> vec){ for (vector<Whatever>::iterator iter = vec.begin(); iter != vec.end(); iter++) { cout << iter->getSize() << iter->getName() << ‘ ‘; } cout << endl;}bool compare(int i, int j){ return (i > j);}bool compareWhat(Whatever i, Whatever j){ return (i < j);}int main(void){ int vecVal[] = {12, 10, 13, 15, 20, 18, 11}; vector<int> vec(vecVal, vecVal+7); sort(vec.begin(), vec.end()); print(vec); sort(vec.begin(), vec.end(), compare); print(vec); vector<Whatever> vecWhat; for (int i = 0; i < 100; i++) { Whatever what(rand()%50, char(97+rand()%25)); vecWhat.push_back(what); } print(vecWhat); sort(vecWhat.begin(), vecWhat.end(), compareWhat); print(vecWhat); return 0;}
[草稿]std::sort