排序的算法有很多种,在我们平时的编程中,我们很多时候会用的着排序,这些时候我们每次都要自己来实现吗?未必,C++标准模版库为我们提供了这样一个函数实现 sort(),用来满足我们日常对排序的需求。
标准模版库中sort函数包含在头文件 <algorithm> 中,std::sort()
default (1) template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last); custom (2) template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
说明:
1、默认情况下是对 [first,last)区间的元素采用由小到大的方式排列
2、可以自定义比较函数,也可以调用stl内提供的比较函数,less<T>() 、greater<T>()
3、排序的区间可以必须是通过迭代器遍历的(数组下标也算),迭代器的类型为随机迭代器;
stl set map 使用红黑树 avl树作为底层数据结构的实现,不支持随机迭代器,所以不能使用sort来排序;
自己定义的数据结构支持这种随机迭代器时,也可以使用sort()算法来排序
4、排序是通过多次内存的copy来实现的,所以链表不能使用stl 算法sort来对其排序(next指针修改问题);
对于链表的排序,stl list<T>中可以实现对双端链表的排序
算法中的sort的时间复杂度:
stl <algorithm> 中的sort算法实现,采用快排的思想,平均的时间复杂度是 N(logN);算法中还提供了其他的集中排序函数 sort_heap() stable_sort() 时间复杂度都在 N(logN)
SLT 算法中的 sort() 函数实例:
#include <iostream> #include <algorithm> using namespace std; bool compare(int x,int y) { return x<y?true:false; } int arr[5] = {3,2,5,8,4}; int main() { //cout << "Hello world!" << endl; int i = 0; for(i=0;i<5;i++) cout<<arr[i]<<" "; cout<<endl; sort(arr,arr+5,compare); for(i=0;i<5;i++) cout<<arr[i]<<" "; return 0; }