STL 中的排序算法

原文：https://www.studytonight.com/cpp/stl/stl-sorting-algorithms

我们将在排序算法下研究三种方法，即:

• 分类
• 被排序
• 部分排序

sort方法

这个函数对给定范围的内容进行排序。sort()有两个版本:

1. sort(start_iterator, end_iterator ):对迭代器 start_iterator 和 end_iterator 定义的范围进行升序排序。
2. sort(start_iterator, end_iterator, compare_function):这也会对给定的范围进行排序，但是您可以定义如何通过 compare_function 进行排序。

 #include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

bool **compare_function**(int i, int j)
{
   return i > j;    // return 1 if i>j else 0
}
bool **compare_string**(string i, string j)
{ 
  return (i.size() < j.size()); 
}

int main()
{
    int arr[5] = {1,5,8,4,2};

    **sort**(arr , arr+5);    *// sorts arr[0] to arr[4] in ascending order*
    */* now the arr is 1,2,4,5,8  */*

    vector<int> **v1**;

    v1.push_back(8);
    v1.push_back(4);
    v1.push_back(5);
    v1.push_back(1);

    */* now the vector v1 is 8,4,5,1 */*
    vector<int>::iterator i, j;

    i = v1.begin();   *// i now points to beginning of the vector v1*
    j = v1.end();     *// j now points to end of the vector v1*

    **sort**(i,j);      *//sort(v1.begin() , v1.end() ) can also be used*
    */* now the vector v1 is 1,4,5,8 */*

    */* use of compare_function */*
    int a2[] = { 4,3,6,5,6,8,4,3,6 };

    **sort**(a2,a2+9,compare_function);  *// sorts a2 in descending order* 
    */* here we have used compare_function which uses operator(>), 
    that result into sorting in descending order */*

    */* compare_function is also used to sort non-numeric elements such as*/*

    string s[]={"a" , "abc", "ab" , "abcde"};

    **sort**(s,s+4,compare_string);
    */* now s is "a","ab","abc","abcde"  */*
}

partial_sort方法

partial_sort()对给定范围内的前半部分元素进行排序，另一半元素保持最初的状态。partial_sort()也有两种变体:

• partial_sort(start, middle, end ):从开始到结束对范围进行排序，中间之前的元素按升序排列，是范围内最小的元素。
• partial_sort(start, middle, end, compare_function):从开始到结束对范围进行排序，排序方式是借助 compare_function 对中间之前的元素进行排序，并且是范围内最小的元素。

 #include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main()
{
    int a[] = {9,8,7,6,5,4,3,2,1};

    **partial_sort**(a, a+4, a+9); 
    */* now a is 1,2,3,4,9,8,7,6,5  */* 

    int b[] = {1,5,6,2,4,8,9,3,7};

    */* sorts b such that first 4 elements are the greatest elements
    in the array and are in descending order */*
    **partial_sort**(b, b+4, b+9);  
    */* now b is  9,8,7,6,1,2,4,3,5 */*
}

is_sorted方法

STL 的这个函数，如果给定的范围被排序，返回真。is_sorted()有两个版本:

1. is_sorted(start_iterator, end_iterator):按升序检查迭代器 start_iterator 和 end_iterator 定义的范围。
2. is_sorted(start_iterator, end_iterator, compare_function):它也检查给定的范围，但是你可以定义排序必须如何进行。

 #include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main()
{
  int a[5] = {1,5,8,4,2}; 
  cout<<**is_sorted**(a, a+5);
  */* prints 0 , Boolean false  */*

  vector<int> **v1**;

  v1.push_back(8);
  v1.push_back(4);
  v1.push_back(5);
  v1.push_back(1);

  */* now the vector v1 is 8,4,5,1 */*
  cout<<is_sorted(v1.begin() , v1.end() );
  */* prints 0 */*
  **sort**(v1.begin() , v1.end() );
  */* sorts the vector v1 */*
  cout<<**is_sorted**(v1.begin() , v1.end());
  */*  prints 1 , as vector v1 is sorted */*    
}