简述：排序算法，参见http://www.cplusplus.com/reference/algorithm/?kw=algorithm
待解决问题：各种排序算法的实现
/*
template <class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); Sort elements in range
Sorts the elements in the range [first,last) into ascending order.
[将[first, last)中的元素升序排列]
The elements are compared using operator< for the first version, and comp for the second.
[元素的比较是通过operator<进行的(或者comp)]
Equivalent elements are not guaranteed to keep their original relative order (see stable_sort).
[相等元素的原有排序不会被保证(如果要保证原有排序，参见stable_sort)]
*/ #include <iostream>
#include <algorithm>
#include <vector> bool myfunction (int i, int j){
return (i<j);
} class myclass
{
public:
bool operator() (int i, int j){
return (i<j);
}
}; int main()
{
int myints[] = {,,,,,,,};
std::vector<int> myvector(myints, myints+); // 32 71 12 45 26 80 53 33 std::sort(myvector.begin(), myvector.begin()+); //(12 32 45 71)26 80 53 33 std::sort(myvector.begin()+, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80) std::sort(myvector.begin(), myvector.end(), myclass()); //(12 26 32 33 45 53 71 80) std::cout<<"myvector contains:";
for(std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
std::cout<<' '<<*it;
std::cout<<'\n'; system("pause");
return ;
}
/*
template <class RandomAccessIterator>
void stable_sort (RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare>
void stable_sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); Sort elements preserving order of equivalents
Sorts the elements in the range [first,last) into ascending order, like sort, but stable_sort preserves the relative order of the elements with equivalent values.
[将[first, last)中的元素升序排列，不同与sort()，该算法会保留相等元素的相对排序]
The elements are compared using operator< for the first version, and comp for the second.
[元素的比较通过operator<来进行(或者通过comp)]
*/ #include <iostream>
#include <algorithm>
#include <vector> 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}; std::vector<double> myvector; myvector.assign(mydoubles, mydoubles+); std::cout<<"using default comparison:";
std::stable_sort(myvector.begin(), myvector.end());
for(std::vector<double>::iterator it = myvector.begin(); it != myvector.end(); ++it)
std::cout<<' '<<*it;
std::cout<<'\n'; myvector.assign(mydoubles, mydoubles+); std::cout<<"using custom comparison:";
std::stable_sort(myvector.begin(), myvector.end(), compare_as_ints);
for(std::vector<double>::iterator it = myvector.begin(); it != myvector.end(); ++it)
std::cout<<' '<<*it;
std::cout<<'\n'; system("pause");
return ;
}
/*
template <class RandomAccessIterator>
void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); template <class RandomAccessIterator, class Compare>
void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); Partially sort elements in range
[局部排序]
Rearranges the elements in the range [first,last), in such a way that the elements before middle are the smallest elements in the entire range and are sorted in ascending order, while the remaining elements are left without any specific order.
[将最小的一些元素按升序排列在[first, middle)中，剩下的未指定排序的元素放在[middle, last)中]
The elements are compared using operator< for the first version, and comp for the second.
[元素的比较通过operator<进行(或者通过comp)]
*/ #include <iostream>
#include <algorithm>
#include <vector> bool myfunction (int i, int j){
return (i<j);
} int main()
{
int myints[] = {, , , , , , , };
std::vector<int> myvector(myints, myints+); std::vector<int>::iterator it; std::cout<<"Before calling partial_sort:";
for(it = myvector.begin(); it != myvector.end(); ++it)
std::cout<<' '<<*it;
std::cout<<'\n'; std::partial_sort(myvector.begin(), myvector.begin()+, myvector.end(), myfunction); std::cout<<"Before calling partial_sort:";
for(it = myvector.begin(); it != myvector.end(); ++it)
std::cout<<' '<<*it;
std::cout<<'\n'; system("pause");
return ;
}
/*
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); Sort element in range
Rearranges the elements in the range [first,last), in such a way that the element at the nth position is the element that would be in that position in a sorted sequence.
[将[first, last)中第nth小的元素排列在第nth位置上]
The other elements are left without any specific order, except that none of the elements preceding nth are greater than it, and none of the elements following it are less.
[至于其他元素则不会指定排序，但要使所有小于第nth个元素的元素都排在它前面，而大于它的元素都排在后面]
The elements are compared using operator< for the first version, and comp for the second.
[元素的比较是通过operator<进行的(或者comp)]
*/ #include <iostream> // std::cout
#include <algorithm> // std::nth_element, std::random_shuffle
#include <vector> // std::vector bool myfunction (int i,int j) { return (i<j); } int main ()
{
std::vector<int> myvector; // set some values:
for (int i=; i<; i++) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9 std::random_shuffle (myvector.begin(), myvector.end()); std::nth_element (myvector.begin(), myvector.begin()+, myvector.end(),myfunction); std::cout << "myvector contains:";
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n'; system("pause");
return ;
} //注：实际上输出的是一个全排序的结果，这是因为该算法设置了一个优化，当区间元素个数不大于32时，直接做一次全排序，只有当元素个数超过32时，才采用局部排序算法
/*
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); Copy and partially sort range
Copies the smallest elements in the range [first,last) to [result_first,result_last), sorting the elements copied. The number of elements copied is the same as the distance between result_first and result_last (unless this is more than the amount of elements in [first,last)).
[将[first, last)中最小的一些元素复制到[result_first, result_last)中并排序，被复制的元素个数为result_last-result_first个]
The range [first,last) is not modified.
[区间[first, last)中的元素没有被改变]
The elements are compared using operator< for the first version, and comp for the second.
[元素的比较通过operator<来进行(或者通过comp)]
*/ #include <iostream>
#include <algorithm>
#include <vector> int myfunction(int i, int j){
return i<j;
} int main()
{
int myints[] = {, , , , , , , , };
std::random_shuffle(myints, myints+); std::vector<int> myvector(); std::partial_sort_copy(myints, myints+, myvector.begin(), myvector.end(), myfunction); std::cout<<"myvector contains:";
for(std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
std::cout<<' '<<*it;
std::cout<<'\n'; system("pause");
return ;
}