算法（Algorithms）

适用范围：入门级
难度系数：3

1、最大、最小值(max, min)

max: Returns the largest of a and b. If both are equivalent, a is returned.
min:Returns the smallest of a and b. If both are equivalent, a is returned.

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

int main () {
  cout << "min(1,2)==" <<min(1,2) << '\n';
  cout << "max(2,1)==" <<max(2,1) << '\n';
  cout << "min('a','z')==" <<min('a','z') << '\n';
  cout << "max('a','z')==" <<max('a','z') << '\n';
  cout << "min(3.14,2.72)==" <<min(3.14,2.72) << '\n';
  cout << "max(3.14,2.73)==" <<max(3.14,2.73) << '\n';
  return 0;
}

2、交换(swap)

格式：swap(a,b)
参数：该函数接受两个必须交换的必需参数a和b。参数可以是任何数据类型。
返回值：该函数不返回任何内容，它交换两个变量的值。

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  int a=3,b=4;
  string c="cat",d="dog";
  swap(a,b);
  cout<<a<<"  "<<b<<endl;
  swap(c,d);
  cout<<c<<" "<<d;
}

edit & run

3、排序函数(sort)

格式：sort(first_pointer,first_pointer+n,cmp) 该函数可以给数组，或者链表list、向量排序。

实现原理：sort并不是简单的快速排序，它对普通的快速排序进行了优化，此外，它还结合了插入排序和堆排序。系统会根据你的数据形式和数据量自动选择合适的排序方法，这并不是说它每次排序只选择一种方法，它是在一次完整排序中不同的情况选用不同方法，比如给一个数据量较大的数组排序，开始采用快速排序，分段递归，分段之后每一段的数据量达到一个较小值后它就不继续往下递归，而是选择插入排序，如果递归的太深，他会选择堆排序。

此函数有3个参数：
参数1：第一个参数是数组的首地址，一般写上数组名就可以，因为数组名是一个指针常量。
参数2：第二个参数相对较好理解，即首地址加上数组的长度n（代表尾地址的下一地址）。
参数3：默认可以不填，如果不填sort会默认按数组升序排序。也就是1,2,3,4排序。可以实现降序。也可以自定义一个排序函数，改排序方式为降序什么的，也就是4,3,2,1这样。

使用此函数需先包含：#include <algorithm>
并且导出命名空间：using namespace std;
简单例子：对数组A的0~n-1元素进行升序排序，只要写sort(A,A+n)即可；对于向量V也一样，sort(v.begin(),v.end())即可。

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

bool compare(int a,int b){
    return a>b;  //如果是return a<b 就是升序排序；
}

int main(){
  int a[]={5,2,3,4,1,6,0};
  string b="asbtlk";
    char c[]={'e','g','a','y'};
     sort(a,a+7);  //默认从小到大，升序
     //降序有两种方式，第一是直接调用函数，第二种是greater<数据类型>()
     //sort(a,a+7,compare);
     //sort(a,a+5,greater<int>()); 
     //从大到小
    for (int i = 0; i <7 ; ++i) {
        cout<<a[i]<<' ';
    }
    cout<<endl;
    sort(c,c+4);
    cout<<c<<endl;
    sort(b.begin(),b.end()); //sort(b.begin(),b.begin()+3);
    cout<<b<<endl;
}

如果是多维数组，采用以下方法：

/****************************************************************
 * multi array STL sort.
 * author: Alex Li
 * date:  2023-4
 * version: 1.0
****************************************************************/
 
#include <iostream>
#include <algorithm>
using namespace std;
#define R 3
#define C 3
 
void SortFun(int arr[R][C]){
    // One by one sort
    // individual rows.
    for (int i = 0; i < R; i++)
        sort(arr[i], arr[i] + C);
 }
 // Printing the sorted matrix
void Display(int arr[R][C]){
     for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++)
            cout << (arr[i][j]) << " ";
        cout << endl;
    }
}

int main(){
    // Initialize the 2D array
    int arr[3][3]
        = { { 3,2,1 }, { 6, 5, 4 }, { 9, 8, 7 } };
    //sort(arr[0],arr[0]+3);
    // Sort the 2D array using the function
    SortFun(arr);
    Display(arr);
    return 0;
}

结构体排序方法：

/****************************************************************
 * A C++ program to demonstrate STL sort() using  our own comparator for stuct
 * author: Alex Li
 * date: 2023-4
 * version: 1.0
 ****************************************************************/

#include <iostream>
#include <algorithm>
using namespace std;
  
// An interval struct has a start time and end time
struct Interval {
    int start, end;
};
  
// Compares two intervals according to starting times.
bool compareInterval(Interval i1, Interval i2)
{
    return (i1.start < i2.start);
}
  
int main()
{
    Interval arr[]
        = { { 6, 8 }, { 1, 9 }, { 2, 4 }, { 4, 7 } };
    //how many elements in the array.
    int n = sizeof(arr) / sizeof(arr[0]);
  
    // sort the intervals in increasing order of start time
    sort(arr, arr + n, compareInterval);
  
    cout << "Intervals sorted by start time : \n";
    for (int i = 0; i < n; i++)
        cout << "[" << arr[i].start << "," << arr[i].end
             << "] ";
  
    return 0;
}

3、反转(reverse)

实现数组、字符串、向量的元素反转。也就是原来顺序的逆序
它的反转区间是左闭右开[i, j)

数组：
reverse(a,a+n) a是数组名
int s[]={0,1,2,3,4,5};
reverse(s,s+6);
输出结果是5,4,3,2,1,0
reverse(a+m,a+n) 从数组a[m]~a[n-1]反转
int s[]={0,1,2,3,4,5};
reverse(s+1,s+4);
输出结果是0,3,2,1,4,5

字符串：
string s=”abcde”;
reverse(s.begin(), s.end())
如果是区间也遵循左闭右开的原则。

向量：
vector<int> vec={1,2,3,4,5}
reverse(vec.begin(), vec.end())

3、查找(find)

4、遍历(for_each)

5、排列(permutation)

6、二分查找(binary_search, lower_bound, upper_bound)

头文件：#include <algorithm>

1、binary_search
查找指定值是否存在
a. 函数模板： binary_search(arr[],arr[]+size,indx)
b. 参数说明：
arr[] :数组首地址
size：数组元素的个数
indx：需要查找的值
c：函数功能：在数组中以二分法检索的方式查找，若在数组(要求数组元素非递减)中查找到indx元素则返回true，若查找不到则返回值为flase。；

2. lower_bound：
功能：查找第一个大于或等于某个元素的位置。
a.函数模板：lower_bound(arr[],arr[]+size , indx):
b.参数说明：
arr[]：数组首地址
size：数组元素个数
indx:需要查找的值
c.函数功能：函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置(注意是地址)。如果所有元素都小于val，则返回last的位置。
注意：函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置，且last的位置是越界的！

3.upper_bound：查找第一个大于某个元素的位置。
a.函数模板：upper_bound(arr[],arr[]+size , indx):
b.参数说明：
arr[]：数组首地址
size：数组元素个数
indx:需要查找的值
c.函数功能：函数upper_bound()返回的在前闭后开区间查找的关键字的上界，返回大于val的第一个元素位置。

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int a[100]= {4,10,11,30,69,70,96,100};
    int b=binary_search(a,a+9,11);//查找成功，返回1
    cout<<b<<endl;
    int c=binary_search(a,a+9,40);//查找失败，返回0
    cout<<c<<endl;
    int d=lower_bound(a,a+9,10)-a;
    cout<<d<<endl;
    int e=lower_bound(a,a+9,69)-a;
    cout<<e<<endl;
    int f=upper_bound(a,a+9,10)-a;
    cout<<f<<endl;
    int g=upper_bound(a,a+9,69)-a;
    cout<<g<<endl;
}

Previous Topic

Back to Lesson

Next Topic

C++程序设计

算法（Algorithms）