STL sort原理及用法详解



排序的算法有很多种，在我们平时的编程中，我们很多时候会用的着排序，这些时候我们每次都要自己来实现吗？未必，C++标准模版库为我们提供了这样一个函数实现 sort()，用来满足我们日常对排序的需求。

标准模版库中sort函数包含在头文件 <algorithm> 中，std::sort()

 

  1. default (1)   
  2. template <class RandomAccessIterator>  
  3.   void sort (RandomAccessIterator first, RandomAccessIterator last);  
  4. custom (2)    
  5. template <class RandomAccessIterator, class Compare>  
  6.   void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);  
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() 函数实例：

 

  1. #include <iostream>   
  2. #include <algorithm>   
  3. using namespace std;  
  4.   
  5. bool compare(int x,int y)  
  6. {  
  7.     return x<y?true:false;  
  8. }  
  9.   
  10. int arr[5] = {3,2,5,8,4};  
  11.   
  12. int main()  
  13. {  
  14.     //cout << ”Hello world!” << endl;   
  15.     int i = 0;  
  16.     for(i=0;i<5;i++)  
  17.         cout<<arr[i]<<”  ”;  
  18.     cout<<endl;  
  19.     sort(arr,arr+5,compare);  
  20.     for(i=0;i<5;i++)  
  21.         cout<<arr[i]<<”  ”;  
  22.     return 0;  
  23. }