Benjamin

静以修身,俭以养德,非澹薄无以明志,非宁静无以致远。
随笔 - 279, 文章 - 0, 评论 - 196, 引用 - 0
数据加载中……

STL算法(Algorithms):排序

一、sort:对一定范围内的所有元素排序

原型:

template <class RandomAccessIterator>

  void sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>

  void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );
例子代码:

// sort algorithm example

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

 

bool myfunction (int i,int j) { return (i<j); }

 

struct myclass {

  bool operator() (int i,int j) { return (i<j);}

} myobject;

 

int main () {

  int myints[] = {32,71,12,45,26,80,53,33};

  vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33

  vector<int>::iterator it;

 

  // using default comparison (operator <):

  sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33

 

  // using function as comp

  sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

 

  // using object as comp

  sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)

 

  // print out content:

  cout << "myvector contains:";

  for (it=myvector.begin(); it!=myvector.end(); ++it)

    cout << " " << *it;

 

  cout << endl;

 

  return 0;

}

二、stable_sort:归并排序

原型:

template <class RandomAccessIterator>

  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>

  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,

                     Compare comp );
例子代码:

// stable_sort example

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

 

bool compare_as_ints (double i,double j)

{

  return (int(i)<int(j));

}

 

int main () {

  double mydoubles[] = {3.14, 1.41, 2.72, 4.67, 1.73, 1.32, 1.62, 2.58};

 

  vector<double> myvector;

  vector<double>::iterator it;

 

  myvector.assign(mydoubles,mydoubles+8);

 

  cout << "using default comparison:";

  stable_sort (myvector.begin(), myvector.end());

  for (it=myvector.begin(); it!=myvector.end(); ++it)

    cout << " " << *it;

 

  myvector.assign(mydoubles,mydoubles+8);

 

  cout << "\nusing 'compare_as_ints' :";

  stable_sort (myvector.begin(), myvector.end(), compare_as_ints);

  for (it=myvector.begin(); it!=myvector.end(); ++it)

    cout << " " << *it;

 

  cout << endl;

 

  return 0;

}

三、partial_sort_copy:对序列中的某个范围的元素进行排序(部分排序)

原型:

template <class InputIterator, class RandomAccessIterator>

  RandomAccessIterator

    partial_sort_copy ( InputIterator first,InputIterator last,

                        RandomAccessIterator result_first,

                        RandomAccessIterator result_last );

template <class InputIterator, class RandomAccessIterator, class Compare>

  RandomAccessIterator

    partial_sort_copy ( InputIterator first,InputIterator last,

                        RandomAccessIterator result_first,

                        RandomAccessIterator result_last, Compare comp );
示例代码:

// partial_sort example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool myfunction (int i,int j) { return (i<j); }

int main () {
  int myints[] = {9,8,7,6,5,4,3,2,1};
  vector<int> myvector (myints, myints+9);
  vector<int>::iterator it;

  // using default comparison (operator <):
  partial_sort (myvector.begin(), myvector.begin()+5, myvector.end());

  // using function as comp
  partial_sort (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);

  // print out content:
  cout << "myvector contains:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}

四、partial_sort_copy部分排序后拷贝
原型:

template <class InputIterator, class RandomAccessIterator>

  RandomAccessIterator

    partial_sort_copy ( InputIterator first,InputIterator last,

                        RandomAccessIterator result_first,

                        RandomAccessIterator result_last );

template <class InputIterator, class RandomAccessIterator, class Compare>

  RandomAccessIterator

    partial_sort_copy ( InputIterator first,InputIterator last,

                        RandomAccessIterator result_first,

                        RandomAccessIterator result_last, Compare comp );

示例:

// partial_sort_copy example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool myfunction (int i,int j) { return (i<j); }

int main () {
  int myints[] = {9,8,7,6,5,4,3,2,1};
  vector<int> myvector (5);
  vector<int>::iterator it;

  // using default comparison (operator <):
  partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end());

  // using function as comp
  partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end(), myfunction);

  // print out content:
  cout << "myvector contains:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}
五、nth_element:使第n个元素处在序列中的第n个位置,并在这个元素前都是比这个元素小的,
这个元素后面都是比这个这元素大,但是这前后两个序列并不一定都是有序的
(排过序);
 原型:

template <class RandomAccessIterator>

  void nth_element ( RandomAccessIterator first, RandomAccessIterator nth,

                     RandomAccessIterator last );

 

template <class RandomAccessIterator, class Compare>

  void nth_element ( RandomAccessIterator first, RandomAccessIterator nth,

                     RandomAccessIterator last, Compare comp );

例子代码:
// nth_element example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool myfunction (int i,int j) { return (i<j); }

int main () {
  vector<int> myvector;
  vector<int>::iterator it;

  // set some values:
  for (int i=1; i<10; i++) myvector.push_back(i);   // 1 2 3 4 5 6 7 8 9

  random_shuffle (myvector.begin(), myvector.end());

  // using default comparison (operator <):
  nth_element (myvector.begin(), myvector.begin()+5, myvector.end());

  // using function as comp
  nth_element (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);

  // print out content:
  cout << "myvector contains:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}




 

posted on 2012-01-07 16:32 Benjamin 阅读(360) 评论(0)  编辑 收藏 引用 所属分类: 泛型编程


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理