algorithm_algorithms - CSDN
精华内容
参与话题
  • algorithm头文件常用函数

    千次阅读 多人点赞 2019-01-10 19:45:35
    algorithm意为"算法",是C++的标准模版库(STL)中最重要的头文件之一,提供了大量基于迭代器的非成员模板函数。 类 别 C++标准库 头文件 #include <algorithm> 命名...

    algorithm意为"算法",是C++的标准模版库(STL)中最重要的头文件之一,提供了大量基于迭代器的非成员模板函数。

    • 类 别 C++标准库
    • 头文件 #include <algorithm>
    • 命名空间 using namespace std

    其中包括以下部分函数:

    1. max()、min()和abs()
    2. swap()
    3. reverse()
    4. next_permutation()
    5. fill()
    6. sort()
    7. lower_bound()和upper_bound()
    • 最大最小操作
    max 返回两个元素中值最大的元素
    min 返回两个元素中值最小的元素
    abs() 返回元素绝对值
    next_permutation 返回给定范围中的元素组成的下一个按字典序的排列
    • 修改内容操作
    swap 交换两个对象的值
    reverse 反转排序指定范围中的元素
    fill 将一个范围的元素赋值为给定值
    • 排序操作
    sort 排序
    • 查找操作
    lower_bound 返回指向范围中第一个值大于或等于给定值的元素的迭代器
    upper_bound 返回指向范围中第一个值大于给定值的元素的迭代器
    • max()

    作 用:返回一个最大数值
    语 法:MAX(number1,number2,…)
    参 数: Number1,number2,

    注意: 如果参数不包含数字,函数 MAX 返回 0。

    示例
    示例1:如果 A1:A5 包含数字 10、7、9、27 和 2,则:
    MAX(A1:A5) 等于 27
    MAX(A1:A5,30) 等于 30

    示例2:如果A1=71、A2=83、A3=76、A4=49、A5=92、A6=88、A7=96。
    则公式“=MAX(A1:A7)”返回96。

    #include <iostream>    
    #include <algorithm>    
    using namespace std;
    int main () {
      cout << "max(1,2)==" << std::max(1,2) << '\n';
      cout << "max(2,1)==" << std::max(2,1) << '\n';
      cout << "max('a','z')==" << std::max('a','z') << '\n';
      cout << "max(3.14,2.73)==" << std::max(3.14,2.73) << '\n';
      return 0;
    }
    

    在这里插入图片描述

    • min()

    min(x,y)分别返回x和y中的最小值,且参数必须是两个。

    示例1:如果 A1:A5 中依次包含数值 10,7,3,27 和 2,那么
    MIN(A1:A5) 等于 2
    MIN(A1:A5, 0) 等于 0

    例:

    #include <iostream>     
    #include <algorithm>    
    using namespace std;
    int main () {
      cout << "min(1,2)==" << min(1,2) << '\n';
      cout << "min(2,1)==" << min(2,1) << '\n';
      cout << "min('a','z')==" << min('a','z') << '\n';
      cout << "min(3.14,2.72)==" << min(3.14,2.72) << '\n';
      return 0;
    }
    

    在这里插入图片描述

    • abs()

    abs(x) 返回x的绝对值。x必须为整数,浮点型的绝对值要用math头文件下的fabs

    //#include<algorithm>
    #include<cstdio>
    #include<cmath>
    #include<iostream>
    using namespace std;
    int main()
    {
        int x,f;
     
    	printf("请输入一个整数:\n");
    	scanf("%d",&x);
    	printf("绝对值为%d\n",abs(x));
    
    //	printf("请输入一个浮点数:\n");
    //	scanf("%lf",&f);
    //	printf("绝对值为%lf\n",fabs(f));
    	return 0;
    }
    
    

    如果没有头文件,绝对值返回0
    在这里插入图片描述

    • swap()
      交换两个对象的值,即交换a和b的值。

    通用的函数交换模板
    template<class T> void swap(T &a,T &b) { T c(a); a=b; b=c; }
    针对int类型的优化

    void swap(int &a,int &b)
     {
         a^=b;
         b^=a;       //相当于b=a
        a^=b;       //相当于a=b
     }
    

    自定义swap时,注意事项
    1.无法实现交换目的

    void swap(int a,int b)//这里只是交换了a和b实参的副本,而它们本身没有交换。
     {
         int temp=a;
        a=b;
       b=temp;
     }
    

    2.能够达到交换目的

    #include <iostream>    
    #include <algorithm>   
     
    using namespace std;
    void swap(int *a,int *b)
    {
        int temp;
        temp=*a;
        *a=*b;
        *b=temp;
    }
    
    //使用
    int main()
    {
        int a=1,b=2;
        swap(&a,&b);
      cout<<a<<endl;
      cout<<=<<endl;
        return 0;
    }
    

    在这里插入图片描述

    • reverse()

    1.会将区间内的元素全部逆序。常用于数组,字符串,容器等,其本身的函数参数也不复杂。
    2.容器类型的要用begin()和end()来指定反转的区域,数组类型的直接用int类型即可。
    3.reverse函数用于反转在[first,last)范围内的顺序(包括first指向的元素,不包括last指向的元素),reverse函数没有返回值

    此函数模板的行为等效于(通过调用iter_swap来交换元素位置):

    template <class BidirectionalIterator>
      void reverse (BidirectionalIterator first, BidirectionalIterator last)
    {
      while ((first!=last)&&(first!=--last)) {
        std::iter_swap (first,last);
        ++first;
      }
    }
    
    • 交换vector容器中元素的顺序
    vector<int> v = {5,4,3,2,1};
    reverse(v.begin(),v.end());//v的值为1,2,3,4,5
    
    • string类的字符串
    string str="www.mathor.top";
    reverse(str.begin(),str.end());//str结果为pot.rohtam.wwww
    

    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int main()
    {
    	int a[50];
    	int b[50]; 
    	for(int i=0;i<10;i++)
    	{
    		a[i]=i;
    		if(i!=9)
    		cout<<a[i]<<" ";
    		else
    		cout<<a[i]<<endl;
    	}
    	reverse(a,a+10);         //第二个参数是数组最后一个元素的下一个地址 
    	for(int i=0;i<10;i++)
    	{
    		if(i!=9)
    		cout<<a[i]<<" ";
    		else
    		cout<<a[i]<<endl;
    	}
    }
    
    

    在这里插入图片描述

    • next_permutation()

    返回给定范围中的元素组成的下一个按字典序的排列,next_permutation(start,end)和prev_permutation(start,end)。这两个函数作用是一样的,区别就在于前者求的是当前排列的下一个排列,后一个求的是当前排列的上一个排列。

    next_permutation函数,其函数原型为:

       #include <algorithm>
    
         bool next_permutation(iterator start,iterator end)//当当前序列不存在下一个排列时,函数返回false,否则返回true
    
    • 当把while(next_permutation(num,num+3))中的3改为2时,输出就变为了:只对1,2进行全排,可以知道next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列,同时并改变num数组的值。
      在这里插入图片描述
    • 还有next_permutation()在使用前需要对欲排列数组按升序排序,否则只能找出该序列之后的全排列数。比如,如果数组num初始化为2,3,1,那么输出就变为了:
      在这里插入图片描述
    • 此外,next_permutation(node,node+n,cmp)可以对结构体num按照自定义的排序方式cmp进行排序。也可以对字符next_permutation 自定义比较函数

    • 若排列本米就是最大的了没有后继,则next permotation执行后,会对
      排列进行字典开序排序相当于循环
    int list[31={3.,2.1};
    next permutation(list,list+3);
    conut<<list[0]<<" "<list[U<<" "<listl2k<<endl;//输出:1 2 3
    
    
    • List item

    char类型的next permutation

    //
    该语句对输入的数组进行字典升序排序如输入9874563102 cout<<ch;
    将输出 0123456789这样就能输出全排列了
    
    int mainO
    char ch[2051;cin>> ch;
    sort(ch, ch+ strlen(ch));
    
    //这样就不必事先知道ch的大小了,是把整个ch字符串全都进行排序
    //若采用while(nextpermutation(ch,ch+5);如果只输入1562,就会产
    生错误,因为ch中第五个元素指向未知
    //若要整个字符中进行排序,参数5指的是数组的长度,不含结束符
    
    char *frstE ch;
    char *last ch+ strlen(ch);
    do{
    cout<<ch<< endl;
    }while(next permutation(first,lastD);return0;
    
    • string类型的nextpermutation
    int main()
    {
    	string line;
    	while(cin>>line&&line!="#"')
    	{
    		if(nexL permutation(line.beginQline.end0)当前输入位置开始
    		cout<line<<endl;
    		elsecout<< "Nosuccesor\";
    	}
    }
    
    int main()
    {
    	string line;
    	while(cin> >line&line!= "#")
    	{
    		sort(line.begin(),line.end0);/排列cout< dline<<endl;
    	}
    }
    
    
    

        #include <iostream>  
        #include <algorithm>  
        using namespace std;  
        int main()  
        {  
            int num[3]={1,2,3};  
            do  
            {  
                cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;  
            }
            while(next_permutation(num,num+3));  
            return 0;  
        }  
    

    在这里插入图片描述

    • fill()

    1.按照单元赋值,将一个区间的元素都赋同一个值
    2.fill(arr, arr + n, 要填入的内容);
    fill(vector.begin(), vector.end(), val);
    3.

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int main() {
        int arr[10];
        fill(arr, arr + 10, 2);
        return 0;
    }
    

    4.vector容器

    #include <algorithm>
     #include <vector> 
     #include <iostream> 
     using namespace std; 
     int main()
     { 
    	 vector<int>  v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    	  fill(v.begin(), v.end(), -1);
    	   return 0; 
       } 
    
    

    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    int main () {
    	vector<int> myvector (8);// myvector: 0 0 0 0 0 0 0 0
    	fill (myvector.begin(),myvector.begin()+4,5);
    	// myvector: 5 5 5 5 0 0 0 0
    	fill (myvector.begin()+3,myvector.end()-2,8);
    	// myvector: 5 5 5 8 8 8 0 0
    	
    	cout << "myvector contains:";
    	for (vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    	cout << " " << *it;
    	
    	cout << endl;
    	return 0;
    }
    

    在这里插入图片描述

    • sort()

    1.Sort函数有三个参数:
    (1)第一个是要排序的数组的起始地址。
    (2)第二个是结束的地址(最后一位要排序的地址的下一地址)
    (3)第三个参数是排序的方法,可以是从大到小也可是从小到大,还可以不写第三个参数,此时默认的排序方法是从小到大排序。
    2.Sort函数使用模板:Sort(start,end,排序方法)

    //例一:sort函数没有第三个参数,实现的是从小到大
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int main()
    {
    int a[10]={9,6,3,8,5,2,7,4,1,0};
    	for(int i=0;i<10;i++)
    	cout<<a[i]<<endl;
    	sort(a,a+10);
    	for(int i=0;i<10;i++)
    	cout<<a[i]<<endl;
    	return 0;
    }
    
    //例2需要在sort()函数里的第三个参数里,从大到小排序!
    //加入一个比较函数compare(),
    #include<iostream>
    #include<algorithm>
    using namespace std;
    bool compare(int a,int b)
    {
    return a>b;
    }
    int main()
    {
    int a[10]={9,6,3,8,5,2,7,4,1,0};
    for(int i=0;i<10;i++)
    cout<<a[i]<<endl;
    sort(a,a+10,compare);//在这里就不需要对compare函数传入参数了,
    //这是规则
    for(int i=0;i<10;i++)
    cout<<a[i]<<endl;
    return 0;
    }
    
    
    • lower_bound()和upper_bound( )

    lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

    、lower_bound()

    • lower_bound()返回值是一个迭代器,返回指向比key大的第一个值的位置
      对象:有序数组或容器
    • lower_bound(起始地址,结束地址,要查找的数值) 返回的是数值 第一个 出现的位置。
    • 功能:函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。如果所有元素都小于val,则返回last的位置.

    注意:如果所有元素都小于val,则返回last的位置,且last的位置是越界的!!

    二、upper_bound()

    • upper_bound(起始地址,结束地址,要查找的数值) 返回的是数值 最后一个 出现的位置。
    • 功能:函数upper_bound()返回的在前闭后开区间查找的关键字的上界,返回大于val的第一个元素位置

    注意:返回查找元素的最后一个可安插位置,也就是“元素值>查找值”的第一个元素的位置。同样,如果val大于数组中全部元素,返回的是last。(注意:数组下标越界)

     #include <iostream>  
        #include <algorithm>  
        #include<vector>
        using namespace std; 
    int main()
    {
        vector<int> t;
        t.push_back(1);
        t.push_back(2);
        t.push_back(3);
        t.push_back(4);
        t.push_back(6);
        t.push_back(7);
        t.push_back(8);
    
        
        int low=lower_bound(t.begin(),t.end(),5)-t.begin();
        int upp=upper_bound(t.begin(),t.end(),5)-t.begin();
        cout<<low<<endl;
        cout<<upp<<endl;
    
        
        
        return 0;
    }
    

    在这里插入图片描述

    展开全文
  • algorithm用法详解

    千次阅读 2019-05-21 16:35:02
    algorithm>定义了一系列特别设计用于元素范围的函数。 范围是可以通过迭代器或指针访问的任何对象序列,例如数组或某些STL 容器的实例。但请注意,算法直接通过迭代器对值进行操作,不会以任何方式影响任何可能...

    标准库模板: Algorithms

    头文件<algorithm>定义了一系列特别设计用于元素范围的函数。

    范围是可以通过迭代器或指针访问的任何对象序列,例如数组或某些STL 容器的实例。但请注意,算法直接通过迭代器对值进行操作,不会以任何方式影响任何可能容器的结构(它永远不会影响容器的大小或存储分配)。


    在开始之前,首先介绍下一些模板的知识,本文在介绍具体函数之前,先把函数总览列了出来,如果读者不想看全部内容,可以检索定位到自己喜欢的函数,直接查看。在查看本文章之前需要读者具备一定的 vector 知识。本文作者只写了algorithm 中常用的一些函数,如果读者有其他需要,可以在博客中留言,博主会为读者添加

    vector 参考链接: https://blog.csdn.net/qq_41291253/article/details/89840185 

    函数模板与类模板

    模板是实现代码重用机制的一种工具,它可以实现类型参数化,即把类型定义为参数,从而实现了代码的重用。所谓函数模板,实际上就是建立一个通用函数,其函数返回类型形参类型不具体制定,用一个虚拟的类型来代表。

    函数模板声明格式如下:

    template <typename/class 类型参数>
       返回类型 函数名(模板形参表)
    {
        函数体
    }
    
    //求最大值函数 max()定义成函数模板
    template <typename T>
       T max(T x, T y)
    {   return(x > y) ? x : y;  }
    
    //使用方式,直接函数名调用
    int x1, y1;
    double x2, y2;
    max(x1, y1);
    max(x2, y2);

    类模板

    template <class 类型参数>
    class 类名
    {
        类成员声明
    };
    
    //求三个数之和
    template <class T>
       class Three
    {
        public::
            Three(T a, T b, T c)
            { x = a; y = b; z = c;}
            T sum()
            { return x + y + z;}
        private:
            T x, y, z;
    };
    
    //使用方式,
    类模板名<实际类型名>对象名;
    类模板名<实际对象名>对象名(实参表列);
    Three<int> sum3(3, 5, 7);
    

    函数总览:

    一、非修改序列函数

    1.for_each

    将函数fn应用于[first,last)范围中的每个元素

    2.find

    [first,last)范围内比较元素值是否等于val并返回第一个等于 val元素的迭代器

    3.find_if

    返回在[first,last]范围中的元素传入pred函数中返回true的第一个元素的迭代器

    4.search

    搜索[first1,last1)定义的范围中第一次出现[first2,last2)序列,并将迭代器返回到其第一个元素

    5.find_end

    搜索[first1,last1)定义的范围中最后一次出现[first2,last2)序列,并将迭代器返回到其第一个元素

    6.count

    计算[first, last)范围内等于 val 值的元素数

    7.count_if

    在[first1,last1)范围内返回满足 pred函数条件的元素总数

    8.search_n

    在[first, last)范围内搜索最小连续元素(count)都等于val值的第一个元素的迭代器

    二、修改序列函数

    1.copy 复制范围内的元素
    2.swap 交换两个对象的值

    3.swap_rangs

    交换两个范围的元素
    4.reverse  反向范围
    5.replace 替换范围中的元素
    6.replace_if 根据条件替换范围中的元素
    7.remove 从范围中删除元素
    8.remove_if 根据条件从范围中删除元素
    9.unique 删除范围内的连续重复项

    三、分区

    四、排序

    1.sort 排序范围内的元素
    2.stable_sort 将范围中的元素[first,last)按升序排序,如sort,但stable_sort保留值相等的元素的相对顺序

    五、二进制搜索

    六、合并

    七、堆

    八、最大/最小

    1.max 返回两个值中的最大值(功能模板:int i , j ;  max(i , j);)
    2.min 返回两个值中的最小值

    3.max_element

    返回范围内的最大值
    4.min_element 返回范围内的最小值

    九、其他


    为方便读者检索,可以点击需要查看的函数直接定位

     

    目录

    一、非修改序列函数

    1.for_each:--> 2.find:--> 3.find_if:--> 4.search(-find_end):--> 5.find_end:--> 6.count:--> 7.count_if:--> 8.search_n:

    二、修改序列函数

    1.copy:--> 2.swap:--> 3.swap_rangs--> 4.reverse:--> 5.replace--> 6.replace_if--> 7.remove--> 8.remove_if

    四、排序

    1.sort:--> 2.stable_sort:

    八、最大/最小

    1.max_element / min_element


    函数详解:

    一、非修改序列函数

    1.for_each:

    将函数fn应用于[first,last)范围中的每个元素。

    /*==================================================
    注:fn为一元函数,该函数接受范围内的元素作为参数
        InputIterator Function是参数类型,可变(数组指针,迭代器)
        Function是返回类型,可变。
        for_each 是函数名,不可变
        使用时直接采用函数名+变量的形式进行实例化调用
    ==================================================*/
    template <class InputIterator, class Function>   
       Function for_each (InputIterator first, InputIterator last, Function fn)   
    {
      while (first != last) 
        {
            fn (*first);
            ++first;
        }
      return fn;      // or, since C++11: return move(fn);
    }

    函数用例

    /*==================================================================
     函数操作:for_each()
     函数形参:将迭代器输入到序列中的初始位置和最终位置。使用的范围是[first,last).
             fn-函数指针或move constructible函数对象
     函数返回:返回 fn
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    void myfunction(int i){
        cout << ' ' << i;
    }
    
    struct myclass{
        void operator()(int i){
            cout << ' ' << i;
        }
    }myobject;
    
    int main()
    {
        vector<int> myvector;
        myvector.push_back(10);
        myvector.push_back(20);
        myvector.push_back(30);
        
        cout << "myvector contains: ";
        for_each(myvector.begin(), myvector.end(), myfunction);  //函数名既是该函数的入口指针
        cout << endl;
        
        cout << "myvector contains: ";
        for_each(myvector.begin(), myvector.end(), myobject);
        cout << endl;
        return 0;
    }
    /*=======================================
     函数输出:myvector contains:  10 20 30
             myvector contains:  10 20 30
     =======================================*/

    2.find:

    [first,last)范围内比较元素值是否等于val并返回第一个等于 val元素的迭代器。如果找不到这样的元素,则该函数返回last。

    template<class InputIterator, class T>
      InputIterator find (InputIterator first, InputIterator last, const T& val)
    {
      while (first != last) {
        if (*first == val) return first;
        ++first;
      }
      return last;
    }

    函数用例

    /*==================================================================
     函数操作:find()
     函数形参:将迭代器输入到序列中的初始位置和最终位置。使用的范围是[first,last).
             val-要在范围内搜索的值
     函数返回:比较等于 val 的范围中第一个元素的 iterator(指针类型/地址),如果没有元素匹配,则函数返回 last.
     注:1.返回查找元素对应角标方法:cout << p - myints.begin();
         因为find 返回值为指针类型,数组为连续存储,所以相减即可返回角标
         2.find 对象为 string 类型。则返回值为 vector<char>::iterator it;类型
            string str = "asfdasfs";     
            vector<char>::iterator it ;
            it = find(helper1.begin(), helper1.end(), str[i]);
            cout << helper2[it - helper1.begin()];
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        //using find with array and pointer
        int myints[] = {10, 20, 30, 40};
        int *p;             //迭代器
        
        p = find(myints, myints + 4, 30);
        if(p != myints + 4)
            cout << "Element found in myints: " << *p << endl;
        else
            cout << "Element not found in myints" << endl;
        
        
        //using find eith vector and iterator
        vector<int> myvector(myints, myints + 4);
        vector<int>::iterator it;
        
        it = find(myvector.begin(), myvector.end(), 50);
        if(it != myvector.end())
            cout << "Element found in myints: " << *it << endl;
        else
            cout << "Element not found in myints" << endl;
        return 0;
    }
    /*=======================================
     函数输出:Element found in myints: 30
             Element not found in myints
     =======================================*/

    3.find_if:

    返回在[first,last]范围中的元素传入pred函数中返回true的第一个元素的迭代器。如果没有找到这样的元素,函数返回last。

    template<class InputIterator, class UnaryPredicate>
      InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred)
    {
      while (first != last) {
        if (pred(*first)) return first;  //pred 一元函数指针
        ++first;
      }
      return last;
    }

    函数用例

    /*==================================================================
     函数操作:find_if()
     函数形参:将迭代器输入到序列中的初始位置和最终位置。使用的范围是[first,last).
             pred-一元函数,它接受范围内的一个元素作为参数,并返回一个可转换到bool的值。返回的值指示该元素在此函数的上下文中是否被视为匹配。
             函数不能修改它的参数。
             它可以是函数指针,也可以是函数对象。
     函数返回:pred不返回false的范围内的第一个元素的迭代器。
             如果pred对所有元素都为false,则函数返回last。
     注:一元谓词(unary predicate)接受一个参数的谓词。谓词是一个可调用的表达式,其返回结果是一个能用作条件的值。
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    bool Isodd(int i){
        return ((i % 2) == 1);    //判断是否是奇数
    }
    
    int main()
    {
        //using find with array and pointer
        int myints[] = {10, 25, 30, 45};
        int *p;             //迭代器
        
        p = find_if(myints, myints + 4, Isodd);
        if(p != myints + 4)
            cout << "The first odd value is: " << *p << endl;
        else
            cout << "Element not found in myints" << endl;
        
        //using find eith vector and iterator
        vector<int> myvector;
        myvector.push_back(10);
        myvector.push_back(20);
        vector<int>::iterator it;
        
        it = find_if(myvector.begin(), myvector.end(), Isodd);
        if(it != myvector.end())
            cout << "The fist odd value is: " << *it << endl;
        else
            cout << "Element not found in vector" << endl;
        return 0;
    }
    /*=======================================
     函数输出:The first odd value is: 25
             Element not found in vector
     =======================================*/

    4.search(-find_end):

    搜索[first1,last1)定义的范围中第一次出现[first2,last2)序列,并将迭代器返回到其第一个元素,如果没有找到,则返回last1。

    equality (1)
    template <class ForwardIterator1, class ForwardIterator2>
       ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
                                ForwardIterator2 first2, ForwardIterator2 last2);
    
    predicate (2)
    template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
       ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
                                ForwardIterator2 first2, ForwardIterator2 last2,
                                BinaryPredicate pred);
    template<class ForwardIterator1, class ForwardIterator2>
      ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
                                ForwardIterator2 first2, ForwardIterator2 last2)
    {
      if (first2 == last2) return first1;  // specified in C++11
      
      while (first1 != last1)
      {
        ForwardIterator1 it1 = first1;
        ForwardIterator2 it2 = first2;
        while (*it1 == *it2) {    // or: while (pred(*it1,*it2)) for version 2
            if (it2 == last2) return first1;
            if (it1 == last1) return last1;
            ++it1; ++it2;
        }
        ++first1;
      }
      return last1;
    }

    函数用例

    /*==================================================================
     函数操作:search()
     函数形参:将迭代器输入到序列中的初始位置和最终位置。使用的范围是[first1,last1).
             将迭代器转发到要搜索的序列的初始和最终位置。使用的范围是[first2,last2).
             pred-二进制函数,接受两个元素作为参数(两个序列中的每一个,按相同的顺序),并返回一个可转换为的值bool。返回值指示在此函数的上下文中是否认为元素匹配。
             该函数不得修改其任何参数。
             这可以是函数指针或函数对象。
     函数返回:一个迭代器,在[first1,last1)的范围内第一次出现[first2,last2)序列的第一个元素。
             如果未找到序列,则函数返回last1。
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    bool mypredicate(int i, int j) { return (i == j); }
    
    int main()
    {
        vector<int> haystack;
        
        //set values:  haystack:10 20 30 40 50 60 70 80 90
        for(int i = 1; i < 10; i++) haystack.push_back(i * 10);
        
        //using default comparrision:
        int needle1[] = {40, 50, 60, 70};
        vector<int>::iterator it;
        it = search(haystack.begin(), haystack.end(), needle1, needle1 + 4);
        
        if(it != haystack.end())
            cout << "needle1 found at position " << it - haystack.begin() << endl;
        else
            cout << "needle1 not dound" << endl;
        
        //using predicate comparison:
        int needle2[] = {20, 30, 50};
        it = search(haystack.begin(), haystack.end(), needle2, needle2 + 3, mypredicate);
        if(it != haystack.end())
            cout << "needle1 found at position " << it - haystack.begin() << endl;
        else
            cout << "needle1 not dound" << endl;
        return 0;
    }
    /*=======================================
     函数输出:needle1 found at position 3
             needle1 not dound
     =======================================*/

    5.find_end:

    搜索[first1,last1)定义的范围中最后一次出现[first2,last2)序列,并将迭代器返回到其第一个元素,如果没有找到,则返回last1。

    equality (1)
    template <class ForwardIterator1, class ForwardIterator2>
       ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,
                                  ForwardIterator2 first2, ForwardIterator2 last2);
    predicate (2)
    template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
       ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,
                                  ForwardIterator2 first2, ForwardIterator2 last2,
                                  BinaryPredicate pred);
    
    //注:forwarditerator 前向迭代器
    template<class ForwardIterator1, class ForwardIterator2>
      ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,
                                 ForwardIterator2 first2, ForwardIterator2 last2)
    {
      if (first2 == last2) return last1;  // specified in C++11
    
      ForwardIterator1 ret = last1;
    
      while (first1 != last1)
      {
        ForwardIterator1 it1 = first1;
        ForwardIterator2 it2 = first2;
        while (*it1 == *it2) {    // or: while (pred(*it1, *it2)) for version (2)
            ++it1; ++it2;
            if (it2 == last2) { ret = first1; break; }
            if (it1 == last1) return ret;
        }
        ++first1;
      }
      return ret;
    }

    函数用例

    /*==================================================================
     函数操作:find_end()
     函数形参:将迭代器输入到序列中的初始位置和最终位置。使用的范围是[first1,last1).
             [first2, last2)-待匹配序列
             pred-二元函数,接受两个元素作为参数(两个序列中的每一个,按相同的顺序),并返回一个可转换为的值bool。返回值指示在此函数的上下文中是否认为元素匹配。
             函数不能修改它的参数。
             它可以是函数指针,也可以是函数对象。
     函数返回:一个迭代器,在[first1,last1)中最后出现[first2,last2)序列的第一个元素。
             如果未找到序列,则函数返回last1。
     注:二元谓词(Binary Predicate)接受两个参数的谓词。谓词是一个可调用的表达式,其返回结果是一个能用作条件的值。
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    bool myfunction(int i, int j){
        return (i == j);
    }
    
    int main()
    {
        int myints[] = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};
        vector<int> haystack(myints, myints + 10);
        
        int needle1[] = {1, 2, 3};
        
        vector<int>::iterator it;
        it = find_end(haystack.begin(), haystack.end(), needle1, needle1 + 3);
        
        if(it != haystack.end())
            cout << "needle1 last found at position: " << it - haystack.begin() << endl;
        
        int needle2[] = {4, 5, 1};
        it = find_end(haystack.begin(), haystack.end(), needle2, needle2 + 3, myfunction);
        
        if(it != haystack.end())
            cout << "needle1 last found at position: " << it - haystack.begin() << endl;
        
        return 0;
    }
    /*=======================================
     函数输出:needle1 last found at position: 5
             needle1 last found at position: 3
     =======================================*/
    

    6.count:

    计算[first, last)范围内等于 val 值的元素数。

    template <class InputIterator, class T>
      typename iterator_traits<InputIterator>::difference_type
        count (InputIterator first, InputIterator last, const T& val)
    {
      typename iterator_traits<InputIterator>::difference_type ret = 0;
      while (first != last) {
        if (*first == val) ++ret;
        ++first;
      }
      return ret;
    }

    函数用例

    /*==================================================================
     函数操作:count()
     函数形参:将迭代器输入到序列中的初始位置和最终位置。使用的范围是[first1,last1).
             val-需要匹配的值
     函数返回:在[first1,last1)范围内等于 val 的元素数
             返回类型(iterator_traits <InputIterator> :: difference_type)是有符号整数类型。
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    bool myfunction(int i, int j){
        return (i == j);
    }
    
    int main()
    {
        int myints[] = {10, 20, 30, 30, 20, 10, 10, 20};
        long mycount = count(myints, myints + 8, 10);
        cout << "10 appears " << mycount << "times." << endl;
        
        vector<int> myvector(myints, myints + 8);
        mycount = count(myvector.begin(), myvector.end(), 20);
        cout << "20 appears " << mycount << "times." << endl;
        return 0;
    }
    /*=======================================
     函数输出:10 appears 3times.
             20 appears 3times.
     =======================================*/

    7.count_if:

    在[first1,last1)范围内返回满足 pred函数条件的元素数

    template <class InputIterator, class UnaryPredicate>
      typename iterator_traits<InputIterator>::difference_type
        count_if (InputIterator first, InputIterator last, UnaryPredicate pred)
    {
      typename iterator_traits<InputIterator>::difference_type ret = 0;
      while (first != last) {
        if (pred(*first)) ++ret;
        ++first;
      }
      return ret;
    }

    函数用例

    /*==================================================================
     函数操作:count_if()
     函数形参:将迭代器输入到序列中的初始位置和最终位置。使用的范围是[first1,last1).
             pred-一元函数接受范围内的元素作为参数,并返回可转换为bool的值。若返回值为真则此元素参与计数,否则舍弃。
     函数返回:在[first1,last1)范围内pred 不返回 FALSE的元素数
             返回类型(iterator_traits <InputIterator> :: difference_type)是有符号整数类型。
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    bool Isodd(int i) { return ((i % 2) == 1); }
    
    int main()
    {
        vector<int> myvetor;
        for(int i = 1; i < 10; i++) myvetor.push_back(i);
        
        long mycount = count_if(myvetor.begin(), myvetor.end(), Isodd);
        cout << "myvector contatins " << mycount << " odd value." <<endl;
        return 0;
    }
    /*=======================================
     函数输出:myvector contatins 5 odd value.
     =======================================*/

    8.search_n:

    在[first, last)范围内搜索最小连续元素(count)都等于val值的第一个元素的迭代器。

    equality (1)

    (-count)

    template <class ForwardIterator, class Size, class T>
       ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
                                 Size count, const T& val);
    

    predicate (2)

    (-cont_if)

    template <class ForwardIterator, class Size, class T, class BinaryPredicate>
       ForwardIterator search_n ( ForwardIterator first, ForwardIterator last,
                                  Size count, const T& val, BinaryPredicate pred );
    template<class ForwardIterator, class Size, class T>
      ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
                                Size count, const T& val)
    {
      ForwardIterator it, limit;
      Size i;
    
      limit=first; std::advance(limit,std::distance(first,last)-count);
    
      while (first!=limit)
      {
        it = first; i=0;
        while (*it==val)       // or: while (pred(*it,val)) for the pred version
          { ++it; if (++i==count) return first; }
        ++first;
      }
      return last;
    }

    函数用例

    /*==================================================================
     函数操作:search_n()
     函数形参:将迭代器输入到序列中的初始位置和最终位置。使用的范围是[first1,last1).
             将迭代器转发到要搜索的序列的初始和最终位置。使用的范围是[first2,last2).
             count-要匹配的最小连续元素数(int 类型)
             val-要比较的单个值,或作为 pred的参数
             pred-二进制函数,接受两个元素作为参数(序列中的一个元素作为一个,val 作为第二个),并返回一个可转换为的值bool。返回值指示在此函数的上下文中是否认为元素匹配。
             该函数不得修改其任何参数。
             这可以是函数指针或函数对象。
     函数返回:一个迭代器,匹配序列的第一个元素
             如果没有找到这样的序列,则返回 last
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    bool mypredicate(int i, int j) { return (i == j); }
    
    int main()
    {
        int myints[] = {10, 20, 30, 30, 20, 10, 10, 20};
        vector<int> myvector(myints, myints + 8);
        
        vector<int>::iterator it;
        
        //using default comparrision:
        it = search_n(myvector.begin(), myvector.end(), 2, 30);
        
        if(it != myvector.end())
            cout << "two 30s found at position " << it - myvector.begin() << endl;
        else
            cout << "match not dound" << endl;
        
        //using predicate comparison:
        it = search_n(myvector.begin(), myvector.end(), 2, 10, mypredicate);
        if(it != myvector.end())
            cout << "two 10s found at position " << it - myvector.begin() << endl;
        else
            cout << "match not dound" << endl;
        return 0;
    }
    /*=======================================
     函数输出:two 30s found at position 2
             two 10s found at position 5
     =======================================*/

    二、修改序列函数

    1.copy:

    [first,last)范围中的元素复制到从result开始的范围内。

    /*===================================================
    注:InputIterator/OutputIterator分别是输入迭代器和输出
        迭代器,可以理解为一个指针类型。
    ===================================================*/
    
    template<class InputIterator, class OutputIterator>
      OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
    {
      while (first!=last) {
        *result = *first;
        ++result; ++first;
      }
      return result;
    }

    函数用例

    /*==================================================================
     函数操作:copy()
     函数形参:将迭代器输入到序列中的初始位置和最终位置。使用的范围是[first1,last1).
             将迭代器输出到目标序列中的初始位置,但不应该是[first1,last1)范围内的任意元素
     函数返回:到目标范围末尾的迭代器(指向复制的最后一个元素之后的元素),其中元素已被复制。
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        int myints[] = {10, 20, 30, 30, 20, 10, 10, 20};
        vector<int> myvector(7);   //输出容器大小应能存储全部复制数据
        
        copy(myints, myints + 7, myvector.begin());
        
        cout << "myvector contains: ";
        for(int i = 0; i < myvector.size(); i++)
            cout << myvector[i] << ' ';
        cout << endl;
        return 0;
    }
    /*=======================================
     函数输出:myvector contains: 10 20 30 30 20 10 10
     =======================================*/
    

    2.swap:

    交换两个对象的值

    template <class T> void swap ( T& a, T& b )
    {
      T c(a); a=b; b=c;
    }
    template <class T, size_t N> void swap (T (&a)[N], T (&b)[N]) 
    {
      for (size_t i = 0; i<N; ++i) swap (a[i],b[i]);
    }

    函数用例:

    /*==================================================================
     函数操作:swap()
     函数形参:两个对象,其内容被交换
     函数返回:无
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    bool mypredicate(int i, int j) { return (i == j); }
    
    int main()
    {
        int x = 10, y = 20;
        swap(x, y);
        
        vector<int> foo(4, x), bar(6, y);
        swap(foo, bar);
        
        cout << "foo contains: ";
        for(vector<int>::iterator it = foo.begin(); it < foo.end(); it++)
            cout << *it << ' ';
        cout << endl;
        return 0;
    }
    /*=======================================
     函数输出:foo contains: 10 10 10 10 10 10
     =======================================*/
    

    3.swap_rangs

    [first1,last1)范围中每个元素的值,与从first2开始的相同范围的对应位置的各个元素值进行交换。

    template<class ForwardIterator1, class ForwardIterator2>
      ForwardIterator2 swap_ranges (ForwardIterator1 first1, ForwardIterator1 last1,
                                    ForwardIterator2 first2)
    {
      while (first1!=last1) {
        swap (*first1, *first2);
        ++first1; ++first2;
      }
      return first2;
    }

    函数用例

    /*==================================================================
     函数操作:swap_ranges()
     函数形参:将前向迭代器转发到要交换的序列之一的初始位置和最终位置。使用的范围是[first1,last1]
             first2-将迭代器转发到要交换的其他序列中的初始位置。使用的范围包括与范围[first1,last1]相同数量的元素。
             两个范围不得重叠
     函数返回:在第二个序列中参与交换的最后一个元素的下一个元素的迭代器
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        vector<int> myvector1;
        for(int i = 1; i <= 5; i++)
            myvector1.push_back(i);
        vector<int> myvector2;
        for(int i = 6; i <= 10; i++)
            myvector2.push_back(i);
        
        vector<int>::iterator it;
        it = swap_ranges(myvector1.begin() + 1, myvector1.end() - 1, myvector2.begin());
        cout << *it << endl;
        
        // print out results of swap:
        cout << "myvector1 contains:";
        for (it = myvector1.begin(); it != myvector1.end(); ++it)
            cout << *it << ' ';
        cout << endl;
        
        cout << "myvector2 contains:";
        for (it = myvector2.begin(); it != myvector2.end(); ++it)
            cout << *it << ' ';
        cout << endl;
        return 0;
    }
    /*=======================================
     函数输出:myvector1 contains:1 6 7 8 5
             myvector2 contains:2 3 4 9 10
     =======================================*/
    

    4.reverse:

    反转[first,last)范围中元素的顺序。

    template <class BidirectionalIterator>
      void reverse (BidirectionalIterator first, BidirectionalIterator last)
    {
      while ((first!=last)&&(first!=--last)) {
        std::iter_swap (first,last);
        ++first;
      }
    }

    函数用例

    /*==================================================================
     函数操作:reverse()
     函数形参:将前向迭代器转发到要交换的序列之一的初始位置和最终位置。使用的范围是[first1,last1]
             BidirectionalIterator 指向交换类型是否正确定义
     函数返回:无
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        vector<int> myvector1;
        for(int i = 1; i <= 5; i++)
            myvector1.push_back(i);
        vector<int> myvector2;
        for(int i = 6; i <= 10; i++)
            myvector2.push_back(i);
        
        reverse(myvector1.begin(), myvector1.end());
        reverse(myvector2.begin() + 1, myvector2.end() - 1);
        
        // print out results of swap:
        vector<int>::iterator it;
        cout << "myvector1 contains:";
        for (it = myvector1.begin(); it != myvector1.end(); ++it)
            cout << *it << ' ';
        cout << endl;
        
        cout << "myvector2 contains:";
        for (it = myvector2.begin(); it != myvector2.end(); ++it)
            cout << *it << ' ';
        cout << endl;
        return 0;
    }
    /*=======================================
     函数输出:myvector1 contains:5 4 3 2 1
             myvector2 contains:6 9 8 7 10
     =======================================*/
    

    5.replace

    用new_value替换范围内[first,last)所有等于old_value的元素。

    template <class ForwardIterator, class T>
      void replace (ForwardIterator first, ForwardIterator last,
                    const T& old_value, const T& new_value)
    {
      while (first != last) {
        if (*first == old_value) *first = new_value;
        ++first;
      }
    }

    函数用例

    /*==================================================================
     函数操作:replace()
     函数形参:将前向迭代器转发到要交换的序列之一的初始位置和最终位置。使用的范围是[first1,last1]
             old_value 要替换的值
             new_valye 替换的值
     函数返回:无
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        int myints[] = {10 ,20 ,30 ,30, 20, 10, 10, 20};
        vector<int> myvector(myints, myints + 7);
        
        replace(myvector.begin(), myvector.end(), 20, 99);
        
        cout << "myvector contains: ";
        for(vector<int>::iterator it = myvector.begin(); it < myvector.end(); it++)
            cout << *it << ' ';
        cout << endl;
        return 0;
    }
    /*=======================================
     函数输出:myvector contains: 10 99 30 30 99 10 10
     =======================================*/
    

    6.replace_if

    在[first,last)范围内的元素,通过 pred函数后返回值为 TRUE的元素,用 value 来替换。

    template < class ForwardIterator, class UnaryPredicate, class T >
      void replace_if (ForwardIterator first, ForwardIterator last,
                       UnaryPredicate pred, const T& new_value)
    {
      while (first!=last) {
        if (pred(*first)) *first=new_value;
        ++first;
      }
    }

    函数用例:

    /*==================================================================
     函数操作:replace_if()
     函数形参:将前向迭代器转发到要交换的序列之一的初始位置和最终位置。使用的范围是[first1,last1]
             pred-一元函数接受范围内的元素作为参数,并返回可转换为的值bool。返回的值表示是否要替换元素(如果true替换它)。
             该函数不得修改其参数。
             这可以是函数指针或函数对象。
             value-要替换的值
     函数返回:无
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    //using namespace std;
    
    bool IsOdd (int i) { return ((i % 2) == 1); }
    
    int main () {
        std::vector<int> myvector;
        
        // set some values:
        for (int i = 1; i < 10; i++) myvector.push_back(i);               // 1 2 3 4 5 6 7 8 9
        
        std::replace_if (myvector.begin(), myvector.end(), IsOdd, 0);      // 0 2 0 4 0 6 0 8 0
        
        std::cout << "myvector contains: ";
        for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); it++)
            std::cout << *it << ' ';
        std::cout << std::endl;
        
        return 0;
    }
    /*=======================================
     函数输出:myvector contains: 0 2 0 4 0 6 0 8 0
     =======================================*/
    

    7.remove

    [first,last)范围中所有等于val的元素移除,并将迭代器返回到该范围的新结尾。

    该函数不能改变包含元素范围的对象的属性(即,它不能改变数组或容器的大小):删除是通过将下一个与 val不匹配的元素 前移来替换 val元素来完成的。

    保留了未删除元素的相对顺序,而返回迭代器和last之间的元素保持有效但未指定的状态。

    template <class ForwardIterator, class T>
      ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val)
    {
      ForwardIterator result = first;
      while (first!=last) {
        if (!(*first == val)) {
          *result = *first;
          ++result;
        }
        ++first;
      }
      return result;
    }

    函数用例

    /*==================================================================
     函数操作:remove()
     函数形参:将前向迭代器转发到要交换的序列之一的初始位置和最终位置。使用的范围是[first1,last1]
             value-要删除的值
     函数返回:未删除的最后一个元素后面的元素的迭代器。
             first和this迭代器之间的范围包括序列中不比较等于val的所有元素。
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main ()
    {
        int myints[] = {10, 20, 30, 30, 20, 10, 10, 20};
        
        //bounds of rang:
        int* pbegin = myints;
        int* pend = myints + sizeof(myints) / sizeof(int);
        
        pend = remove(pbegin, pend, 20);
        
        cout << "rang contains: ";
        for(int* p = pbegin; p != pend; p++)
            cout << *p << ' ';
        cout << endl;
        return 0;
    }
    /*=======================================
     函数输出:rang contains: 10 30 30 10 10
     =======================================*/
    

    8.remove_if

    [first,last)范围中所有pred 返回 TRUE的元素移除,并将迭代器返回到该范围的新结尾

    该函数不能改变包含元素范围的对象的属性(即,它不能改变数组或容器的大小):删除是通过用下一个元素替换pred返回true的元素来完成的。

    template <class ForwardIterator, class UnaryPredicate>
      ForwardIterator remove_if (ForwardIterator first, ForwardIterator last,
                                 UnaryPredicate pred)
    {
      ForwardIterator result = first;
      while (first!=last) {
        if (!pred(*first)) {
          *result = *first;
          ++result;
        }
        ++first;
      }
      return result;
    }

    函数用例

    /*==================================================================
     函数操作:remove_if()
     函数形参:将前向迭代器转发到要交换的序列之一的初始位置和最终位置。使用的范围是[first1,last1]
             pred-一元函数接受范围内的元素作为参数,并返回可转换为的值bool。返回的值指示是否要删除元素(如果要删除true它)。
             该函数不得修改其参数。
             这可以是函数指针或函数对象。
     函数返回:未删除的最后一个元素后面的元素的迭代器。
             first和this迭代器之间的范围包括序列中不比较等于val的所有元素。
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    bool IsOdd (int i) { return ((i % 2) == 1); }
    
    int main ()
    {
        int myints[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        
        //bounds of rang:
        int* pbegin = myints;
        int* pend = myints + sizeof(myints) / sizeof(int);
        
        pend = remove_if(pbegin, pend, IsOdd);
        
        cout << "rang contains: ";
        for(int* p = pbegin; p != pend; p++)
            cout << *p << ' ';
        cout << endl;
        return 0;
    }
    /*=======================================
     函数输出:rang contains: 2 4 6 8
     =======================================*/
    

    9.unique:

    删除范围内的连续重复项
    从[first,last)范围中的每个连续的等效元素组中删除除第一个元素之外的所有元素。

    该函数不能改变包含元素范围的对象的属性(即,它不能改变数组或容器的大小):通过用下一个不重复的元素替换重复元素来完成删除,并且通过将迭代器返回到应该被视为其新的past-the-end元素来发信号通知缩短范围的新大小,即删除重复元素后最后一个元素的下一个元素位置。

    保留未删除元素的相对顺序,而返回的迭代器和last之间的元素保留在有效但未指定的状态。

    equality (1)
    template <class ForwardIterator>
      ForwardIterator unique (ForwardIterator first, ForwardIterator last);
    
    predicate (2)
    template <class ForwardIterator, class BinaryPredicate>
      ForwardIterator unique (ForwardIterator first, ForwardIterator last,
                              BinaryPredicate pred);
    template <class ForwardIterator>
      ForwardIterator unique (ForwardIterator first, ForwardIterator last)
    {
      if (first==last) return last;
    
      ForwardIterator result = first;
      while (++first != last)
      {
        if (!(*result == *first))  // or: if (!pred(*result,*first)) for version (2)
          *(++result)=*first;
      }
      return ++result;
    }

    函数用例

    // unique algorithm example
    #include <iostream>     // std::cout
    #include <algorithm>    // std::unique, std::distance
    #include <vector>       // std::vector
    
    bool myfunction (int i, int j) {
      return (i==j);
    }
    
    int main () {
      int myints[] = {10,20,20,20,30,30,20,20,10};           // 10 20 20 20 30 30 20 20 10
      std::vector<int> myvector (myints,myints+9);
    
      // using default comparison:
      std::vector<int>::iterator it;
      it = std::unique (myvector.begin(), myvector.end());   // 10 20 30 20 10 ?  ?  ?  ?
                                                             //                ^
    
      myvector.resize( std::distance(myvector.begin(),it) ); // 10 20 30 20 10
    
      // using predicate comparison:
      std::unique (myvector.begin(), myvector.end(), myfunction);   // (no changes)
    
      // print out content:
      std::cout << "myvector contains:";
      for (it=myvector.begin(); it!=myvector.end(); ++it)
        std::cout << ' ' << *it;
      std::cout << '\n';
    
      return 0;
    }

     


    四、排序

    1.sort:

    [first,last) 范围中的元素按升序排列

    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);

    函数用例

    /*==================================================================
     函数操作:remove_if()
     函数形参:将前向迭代器转发到要交换的序列之一的初始位置和最终位置。使用的范围是[first1,last1]
             RandomAccessIterator 是能在常数时间内移动到指向任何元素的位置
             comp-二进制函数,接受范围中的两个元素作为参数,并返回可转换为的值bool。返回的值表示作为第一个参数传递的元素是否被认为是在它定义的特定严格弱顺序中的第二个参数之前。
             该函数不得修改其任何参数。
             这可以是函数指针或函数对象。
     函数返回:无
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    //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};
        std::vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33
        
        // using default comparison (operator <):
        std::sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33
        
        // using function as comp
        std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)
        
        // using object as comp
        std::sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)
        
        // print out content:
        std::cout << "myvector contains:";
        for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
            std::cout << ' ' << *it;
        std::cout << '\n';
        
        return 0;
    }
    /*=======================================
     函数输出:myvector contains: 12 26 32 33 45 53 71 80
     =======================================*/

    2.stable_sort:

    将范围中的元素[first,last)按升序排序,如sort,但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()
     函数形参:将前向迭代器转发到要交换的序列之一的初始位置和最终位置。使用的范围是[first1,last1]
             RandomAccessIterator 是能在常数时间内移动到指向任何元素的位置
             comp-二进制函数,接受范围中的两个元素作为参数,并返回可转换为的值bool。返回的值表示作为第一个参数传递的元素是否被认为是在它定义的特定严格弱顺序中的第二个参数之前。
             该函数不得修改其任何参数。
             这可以是函数指针或函数对象。
     函数返回:void
     =================================================================*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    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;
        
        myvector.assign(mydoubles, mydoubles+8);
        
        cout << "using default comparison:";
        stable_sort (myvector.begin(), myvector.end());
        for (vector<double>::iterator it = myvector.begin(); it != myvector.end(); it++)
            cout << ' ' << *it;
        cout << endl;
        
        myvector.assign(mydoubles, mydoubles+8);   //第一次排序后再次赋值
        
        cout << "using 'compare_as_ints' :";
        stable_sort (myvector.begin(), myvector.end(), compare_as_ints);
        for (vector<double>::iterator it = myvector.begin(); it != myvector.end(); it++)
            cout << ' ' << *it;
        cout << '\n';
        
        return 0;
    }
    /*=======================================
     函数输出:using default comparison: 1.32 1.41 1.62 1.73 2.58 2.72 3.14 4.67
             using 'compare_as_ints' : 1.41 1.73 1.32 1.62 2.72 2.58 3.14 4.67
     =======================================*/
    

     


    八、最大/最小

    1.max_element / min_element

    返回指向范围[first,last)中具有最大值的元素的迭代器。

    default (1)
    template <class ForwardIterator>
      ForwardIterator max_element (ForwardIterator first, ForwardIterator last);
    
    custom (2)
    template <class ForwardIterator, class Compare>
      ForwardIterator max_element (ForwardIterator first, ForwardIterator last,
                                   Compare comp);
    template <class ForwardIterator>
      ForwardIterator max_element ( ForwardIterator first, ForwardIterator last )
    {
      if (first==last) return last;
      ForwardIterator largest = first;
    
      while (++first!=last)
        if (*largest<*first)    // or: if (comp(*largest,*first)) for version (2)
          largest=first;
      return largest;
    }

    函数用例

    /*==================================================================
     函数操作:max_element()
     函数形参:将前向迭代器转发到要交换的序列之一的初始位置和最终位置。使用的范围是[first1,last1]
             RandomAccessIterator 是能在常数时间内移动到指向任何元素的位置
             comp-二进制函数,接受范围中的两个元素作为参数,并返回可转换为的值bool。返回的值表示作为第一个参数传递的元素是否被认为是在它定义的特定严格弱顺序中的第二个参数之前。
             该函数不得修改其任何参数。
             这可以是函数指针或函数对象。
     函数返回:范围中最大值的迭代器,如果范围为空,则返回 last
     =================================================================*/
    #include <iostream>
    //#include <vector>
    #include <algorithm>
    //using namespace std;
    
    bool myfn(int i, int j) { return i<j; }
    
    struct myclass {
        bool operator() (int i,int j) { return i<j; }
    } myobj;
    
    int main () {
        int myints[] = {3,7,2,5,6,4,9};
        
        // using default comparison:
        std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << '\n';
        std::cout << "The largest element is "  << *std::max_element(myints,myints+7) << '\n';
        
        // using function myfn as comp:
        std::cout << "The smallest element is " << *std::min_element(myints,myints+7,myfn) << '\n';
        std::cout << "The largest element is "  << *std::max_element(myints,myints+7,myfn) << '\n';
        
        // using object myobj as comp:
        std::cout << "The smallest element is " << *std::min_element(myints,myints+7,myobj) << '\n';
        std::cout << "The largest element is "  << *std::max_element(myints,myints+7,myobj) << '\n';
        
        return 0;
    }
    /*=======================================
     函数输出:The smallest element is 2
             The largest element is 9
             The smallest element is 2
             The largest element is 9
             The smallest element is 2
             The largest element is 9
     =======================================*/
    

     

    展开全文
  • Algorithm(算法)

    千次阅读 2018-08-03 10:56:51
    1、泛型算法通则 所有算法的前两个参数都是一对iterators:[frist,last),用来指出容器内一个范围内的元素 每个算法的声明中,都表现出它所需要的最低层次的iterator类型。 大部分算法都可以用functioin object...

    1、泛型算法通则

    • 所有算法的前两个参数都是一对iterators:[frist,last),用来指出容器内一个范围内的元素
    • 每个算法的声明中,都表现出它所需要的最低层次的iterator类型。

    • 大部分算法都可以用functioin object 来更改准则。function object又称functor

     

    展开全文
  • 相关文章Algorithm:【Algorithm算法进阶之路】之数据结构二十多种算法演示Algorithm:【Algorithm算法进阶之路】之十大经典排序算法Algorithm:【Algorithm算法进阶之路】之数据结构基础知识Algorithm:【Algorithm...

    Algorithm:【Algorithm算法进阶之路】之十大经典排序算法

     

    相关文章
    Algorithm:【Algorithm算法进阶之路】之数据结构二十多种算法演示
    Algorithm:【Algorithm算法进阶之路】之十大经典排序算法
    Algorithm:【Algorithm算法进阶之路】之数据结构基础知识
    Algorithm:【Algorithm算法进阶之路】之数据结构相关习题(数组、字符串、链表、栈、队列、树、图、哈希)
    Algorithm:【Algorithm算法进阶之路】之算法中的数学编程(时间速度、进制转换、排列组合、条件概率、斐波那契数列)相关习题
    Algorithm:【Algorithm算法进阶之路】之算法(查找、排序、递归、复杂度、高级算法)相关习题
    Algorithm:【Algorithm算法进阶之路】之机器学习相关习题
    Algorithm:【Algorithm算法进阶之路】之Python语言相关习题

     

    目录

    如何理解P和NP问题

    十大经典排序算法

    一、排序算法基础知识

    1、排序定义

    2、排序术语

    二、十大排序算法

    0、十大算法复杂度、稳定性比较

    1、简单插入排序(Insertion Sort)

    2、希尔排序(Shell Sort)——简单插入排序的高效版——分治法

    3、选择排序(Selection Sort)

    4、堆排序(Heap Sort)——分治法

    5、冒泡排序(Bubble Sort)

    6、快速排序(Quick Sort)——分治法

    7、归并排序(Merge Sort)——分治法

    8、计数排序(Counting Sort)——非比较的排序算法

    9、桶排序(Bucket Sort)——计数排序的升级版

    10、基数排序(Radix Sort)——非比较的排序算法

    API

    Temp文件(Local Computer)

    版权声明


     

     

     

     

    相关文章
    Algorithm:Algorithm算法进阶之路之数据结构二十多种算法演示
    Algorithm:Algorithm算法进阶之路之十大经典排序算法

     

     

    如何理解P和NP问题

    T1、最简单的解释(来自知乎怎么理解 P 问题和 NP 问题?)
    P:算起来很快的问题
    NP:算起来不一定快,但对于任何答案我们都可以快速的验证这个答案对不对
    NP-hard:比所有的NP问题都难的问题
    NP-complete:满足两点,首先属于是NP hard的问题,也属于NP问题
    T2、P就是能在多项式时间内解决的问题,NP就是能在多项式时间验证答案正确与否的问题。
        用大白话讲大概就是这样。所以P是否等于NP实质上就是在问,如果对于一个问题我能在多项式时间内验证其答案的正确性,那么我是否能在多项式时间内解决它?这个表述不太严谨,但通俗来讲就是如此。

     

    十大经典排序算法

    一、排序算法基础知识

    1、排序定义

    对一序列对象根据某个关键字进行排序。

    2、排序术语

    时间复杂度: 一个算法执行所耗费的时间。
    空间复杂度:运行完一个程序所需内存的大小。

     算法复杂度分为时间复杂度空间复杂度。其作用: 时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间

    1、意义

    • 一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量
    • 对于一个算法,其时间复杂度空间复杂度往往是相互影响的。

    1、时间复杂度

            时间复杂度是同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况
    注:当n趋于∞时,O()看的是最大的那一级,比如O(n-1)即O(n)、
    O(\frac{n(n-1)}{2})O(n^{2})

     

    (1)、按数量级递增排列,常见的时间复杂度有:下边随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

    2、空间复杂度

            空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序时间复杂度是O(n^{2}),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。

     

     

    二、十大排序算法

    思维导图https://www.processon.com/mindmap/5d764121e4b04a19501b9f1d

    0、十大算法复杂度、稳定性比较

    冒泡排序、选择排序、插入排序等,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²)
    非比较排序(计数、桶、基数),只要确定每个元素之前的已有的元素个数即可,所有一次遍历即可解决算法时间复杂度O(n)
    经验总结
    (1)、对任意数列进行排序时,平均排序时间最短的排序算法为:快速排序

     

    排序方法 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 辅助空间复杂度 稳定性 复杂性

    直接

    插入排序

    O(n^{2}) O(n^{2}) O(n) O(1) 稳定 简单
    希尔插入排序 O(n log_{_{2}}n) O(n log_{_{2}}n) O(n log_{_{2}}n) O(1) 不稳定 较复杂

    直接

    选择排序

    O(n^{2}) O(n^{2}) O(n^{2}) O(1) 不稳定 简单
    堆排序 O(n log_{_{2}}n) O(n log_{_{2}}n) O(n log_{_{2}}n) O(1) 不稳定 较复杂
    冒泡排序 O(n^{2}) O(n^{2}) O(n) O(1) 稳定 简单
    快速排序 O(n log_{_{2}}n) O(n2) O(n log_{_{2}}n) O(n log_{_{2}}n) 不稳定 较复杂
    归并排序 O(n log_{_{2}}n) O(n log_{_{2}}n) O(n log_{_{2}}n) O(n) 稳定 较复杂
    计数排序         稳定  
    桶排序         稳定  
    基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(n+r) 稳定 较复杂

    注:
    1、稳定排序:指排序前后两个相等的数,相对位置不变,则算法稳定。
    理解:如果a=b,且a原本在b前面,排序之后a仍然在b的前面,则是稳定算法。,但是排序之后,a可能会出现在b的后面,则为不稳定算法。前六大排序算法中,只有直接插入排序冒泡排序稳定!
    (1)、事实上,任何一个非稳定的排序,如果能够将元素值value与元素所在位置index共同排序,即可得到稳定的排序。
    2、内排序,指所有排序操作都在内存中完成。外排序排序方式需要额外内存,指由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行。

    1、简单插入排序(Insertion Sort)

           插入排序,是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间

    算法描述

    一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

    • 从第一个元素开始,该元素可以认为已经被排序;
    • 取出下一个元素,在已经排序的元素序列中,从后向前扫描;
    • 如果该元素(已排序)大于新元素,将该元素移到下一位置;
    • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
    • 将新元素插入到该位置后;
    • 重复步骤2~5。
      (1)、最坏情况:当待排序列完全逆序时,每个元素需要进行n-1次数据搬移和插入操作,因为有n个元素,即时间复杂度为O(n^{2})
    动画演示

    算法分析

    最佳情况:T(n) = O(n)   最坏情况:T(n) = O(n^{2})   平均情况:T(n) = O(n^{2})
    /**
     * 插入排序
     * @param array
     * @return
     */
    public static int[] insertionSort(int[] array) {
    	if (array.length == 0)
    		return array;
    	int current;
    	for (int i = 0; i < array.length - 1; i++) {
    		current = array[i + 1];
    		int preIndex = i;
    		while (preIndex >= 0 && current < array[preIndex]) {
    			array[preIndex + 1] = array[preIndex];
    			preIndex--;
    		}
    		array[preIndex + 1] = current;
    	}
    	return array;
    }
    
    def Insertion_Sort(lists):
        #外for循环是依次取出第i个元素,插入到内嵌for循环中(插入到当前合适的位置) 
        for i in range(1,len(lists)): #默认第一个元素(索引0)已经在有序序列中,从后面元素开始插入   
            #内嵌for循环,把第i内所有元素升序排好
            for j in range(i,0,-1):         #逆向遍历比较,交换位置实现插入 
                if lists[j-1] > lists[j]:   #当前边的数>后边的数时,才交换位置,即小的靠前插入
                    lists[j],lists[j-1]=lists[j-1],lists[j]
        return lists
    
    list01=[5, 2, 4, 3, 1]
    print('Insertion_Sort:',Insertion_Sort(list01))
    
    
    import random
    max_num = 100
    length = 5
    list = random.sample(range(max_num),length)    #在指定序列中随机获取指定长度片段
     
    list01=[5, 2, 4, 3, 1]
    print('自定义:',list01)
    Insertion_Sort(list01)

     

     

    2、希尔排序(Shell Sort)——简单插入排序的高效版——分治法

           希尔排序,是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。它与插入排序的不同之处在于,它会优先比较距离较远的元素
          希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
          希尔排序是基于插入排序的以下两点性质而提出改进方法的:
    (1)、插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。
    (2)、但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位
           希尔排序又叫缩小增量排序。希尔排序是把记录按下表的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

    算法特点 希尔的不稳定:由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以,Shell排序是不稳定的。
    排序越来越快:每组含有的整数越来越多,但由于这些数也越来越有序,所以排序速度也很快。
    算法描述

          希尔排序的基本步骤,在此我们选择增量gap=length/2,缩小增量继续以gap = gap/2的方式,这种增量选择我们可以用一个序列来表示,{n/2,(n/2)/2...1},称为增量序列。希尔排序的增量序列的选择与证明是个数学难题,我们选择的这个增量序列是比较常用的,也是希尔建议的增量,称为希尔增量,但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。先将整个待排序的记录序列,分割成为若干子序列分别进行直接插入排序,具体算法描述:

    • 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
    • 按增量序列个数k,对序列进行k趟排序;
    • 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。如果仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
    动画演示

    案例一理解
         注:增量的选择 gap = 10/2 ,缩小增量继续以 gap = gap/2 的方式

    第一步:
    整体分组:初始增量为 gap = 10/2 = 5,整个数组分成了 5 组。按颜色划分为【 8 , 3 】,【 9 , 5 】,【 1 , 4 】,【 7 , 6 】,【 2 , 0 】。
    组内采用插入排序:对分开的这 5 组分别使用简单插入排序。结果可以发现,这五组中的相对小元素都被调到前面了
    第二步:
    整体分组:缩小增量 gap = 5/2 = 2,整个数组分成了 2 组。【 3 , 1 , 0 , 9 , 7  】,【 5 , 6 , 8 , 4 , 2  】。
    组内采用插入排序:对这分开的 2 组分别使用上节所讲的插入排序。此时整个数组的有序性是很明显的。
    第三步:
    整体分组:再缩小增量 gap = 2/2 = 1,整个数组分成了 1 组,【 0, 2 , 1 , 4 , 3 , 5 , 7 , 6 , 9 , 0  】。
    组内采用插入排序:此时,只需要对以上数列进行简单的微调(移动的步幅比较小),不需要大量的移动操作即可完成整个数组的排序。

    参考文章:https://cloud.tencent.com/developer/article/1377652

    案例二理解

    算法分析

    最佳情况:T(n) = O(n log_{_{2}}n)  最坏情况:T(n) = O(n log_{_{2}}n)  平均情况:T(n) =O(n log_{_{2}}n) 
    /**
     * 希尔排序
     *
     * @param array
     * @return
     */
    public static int[] ShellSort(int[] array) {
    	int len = array.length;
    	int temp, gap = len / 2;
    	while (gap > 0) {
    		for (int i = gap; i < len; i++) {
    			temp = array[i];
    			int preIndex = i - gap;
    			while (preIndex >= 0 && array[preIndex] > temp) {
    				array[preIndex + gap] = array[preIndex];
    				preIndex -= gap;
    			}
    			array[preIndex + gap] = temp;
    		}
    		gap /= 2;
    	}
    	return array;
    }
    
    def Shell_Sort(lists):
        step = len(lists)//2        #定义增量的选择gap
        while step > 0:
            for i in range(step,len(lists)):            #在[step,len(lists)],比较lists[i]和lists[i-step]的大小
                while(i >= step and lists[i-step] > lists[i]):      #前半>后半,即后边的小→要向前移,实现降序
                    lists[i],lists[i-step] = lists[i-step],lists[i]      #位置变化
                    i -= step                                            #对应的索引位置也要变化
            step //= 2 #外while内,分一半继续循环
        return lists
    list01=[5, 2, 4, 3, 1]
    print('Shell_Sort:',Shell_Sort(list01))

     

     

    3、选择排序(Selection Sort)

              选择排序,是一种简单直观的排序算法。它的工作原理:首先在未排序的序列中,找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中,继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 
    理解:第一次n个数全走一遍,选择最小的放到前边第一位置;第二次,在n-1个数列内再走一遍,选择次小的放到第二位置……

    算法特点
    • 够稳定:表现最稳定的排序算法之一,因为无论什么数据进去都是O(n^{2})的时间复杂度,所以用到它的时候,数据规模越小越好
    • 不占额外内存:唯一的好处可能就是不占用额外的内存空间了吧。
    • 最常见:理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
    算法描述

    n个记录的直接选择排序,可经过n-1趟直接选择排序,得到有序结果。具体算法步骤如下:

    • 初始状态:无序区为R[1..n],有序区为空;
    • 第i趟排序(i=1,2,3…n-1)开始时,当前有序区无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区
    • n-1趟结束,数组有序化了。
    动画演示

    算法分析

    最佳情况:T(n) = O(n^{2})  最差情况:T(n) = O(n^{2})  平均情况:T(n) = O(n^{2})
    /**
     * 选择排序
     * @param array
     * @return
     */
    public static int[] selectionSort(int[] array) {
    	if (array.length == 0)
    		return array;
    	for (int i = 0; i < array.length; i++) {
    		int minIndex = i;
    		for (int j = i; j < array.length; j++) {
    			if (array[j] < array[minIndex]) //找到最小的数
    				minIndex = j; //将最小数的索引保存
    		}
    		int temp = array[minIndex];
    		array[minIndex] = array[i];
    		array[i] = temp;
    	}
    	return array;
    }
    
    def Selection_Sort(lists):
        for i in range(0, len(lists)-1):     #循环到最后,前边已是递增排列,故最后一个元素一定最大,不会被比较
            min_ = i
            for j in range(i+1, len(lists)): #for一次循环,找到后边中的最小索引:因为第i个基标准,所以比较从第i+1个开始
                if lists[min_] > lists[j]:   #与后边的元素挨个比较,找到最小元素的索引,去更新索引min_
                    min_ = j       
                    
            #再利用最小元素作为标准即赋值给lists[i],进入下一个循环
            lists[i], lists[min_] = lists[min_], lists[i]  #理解:因为min_、i要进行交换,所以双向交换    
        return lists
    
    list01=[5, 2, 4, 3, 1]
    print('Selection_Sort:',Selection_Sort(list01))

     

     

     

    4、堆排序(Heap Sort)——分治法

             堆排序,是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序是利用 进行排序的。  

    算法特点

    1、是一种完全二叉树
    2、有两种类型: 大根堆小根堆。

    • 每个结点的值(非叶子节点的关键字)都大于或等于其左右孩子结点的值,称为大顶堆;即大顶堆的堆顶元素是最大的。
    • 或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。

    3、可用数组存储:完全二叉树可以用数组完美存储,对于长度为n的数组a[0,…,n-1],若" 0≤i≤n-1,a[i]≤a[2i+1]且a[i]≤a[2i+2],那么,a表示一个小顶堆。

    4、代码编程中,父子节点可相互索引

    • k的孩子结点:如果存在分别是2k+ 1,2k+2。
    • k的父结点:若k为左孩子:则k的父结点为k/2;若k为右孩子:则k的父结点为k/2-1。
    • 发现:二者公式不一样,十分不便。 若k为左孩子,则k为奇数,则((k+1)/2)-1与k/2相等;若k为右孩子,则k为偶数,则((k+1)/2)-1与k/2-1相等。
    • 结论:若待考查结点为k,记k+1为K,则k的父结点为K/2-1

    5、堆排序的时间复杂度O(N*log2N)初始化堆的过程O(N)、调整堆的过程O(log2N)。

    算法描述

    1、堆排序的三步思路

    ①初始化操作:将a[0…n-1]构造为堆(如大顶堆);左至右,从下至上进行调整。

    ②第i(n > i ≥ 1)趟排序:将堆顶记录a[0]和a[n-i]交换,即将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;。然后将a[0…n-i-1]调整为堆(即:重建大顶堆);

    ③进行n-1趟,完成排序。

    2、堆排序的四个过程

    • 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
    • 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
    • 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)
    • 不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。
    算法改进

    堆排序中的改进思考

           得到一个堆后,堆排序仅输出堆顶元素,便又重新组织新堆了,没有利用完全堆的全部信息。根据堆的逻辑结构和特征,堆顶结点的左右孩子之一必有一个是数据中的第二大(小)者,通过加入比较,完全可以随着堆顶一起文换到末尾。然后,分别对次顶堆和顶堆调整即可。

    动画演示

    两个案例理解

    动画演示https://bajdcc.github.io/html/heap.html

    算法分析

    最佳情况:T(n) = O(nlogn) 最差情况:T(n) = O(nlogn) 平均情况:T(n) = O(nlogn)
    //声明全局变量,用于记录数组array的长度;
    static int len;
    /**
     * 堆排序算法
     *
     * @param array
     * @return
     */
    public static int[] HeapSort(int[] array) {
    	len = array.length;
    	if (len < 1) return array;
    	//1.构建一个最大堆
    	buildMaxHeap(array);
    	//2.循环将堆首位(最大值)与末位交换,然后在重新调整最大堆
    	while (len > 0) {
    		swap(array, 0, len - 1);
    		len--;
    		adjustHeap(array, 0);
    	}
    	return array;
    }
    /**
     * 建立最大堆
     *
     * @param array
     */
    public static void buildMaxHeap(int[] array) {
    	//从最后一个非叶子节点开始向上构造最大堆
    	for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒,此处应该为 i = (len/2 - 1) 
    		adjustHeap(array, i);
    	}
    }
    /**
     * 调整使之成为最大堆
     *
     * @param array
     * @param i
     */
    public static void adjustHeap(int[] array, int i) {
    	int maxIndex = i;
    	//如果有左子树,且左子树大于父节点,则将最大指针指向左子树
    	if (i * 2 < len && array[i * 2] > array[maxIndex])
    		maxIndex = i * 2;
    	//如果有右子树,且右子树大于父节点,则将最大指针指向右子树
    	if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
    		maxIndex = i * 2 + 1;
    	//如果父节点不是最大值,则将父节点与最大值交换,并且递归调整与父节点交换的位置。
    	if (maxIndex != i) {
    		swap(array, maxIndex, i);
    		adjustHeap(array, maxIndex);
    	}
    }
    

    python代码实现及理解

    def big_endian(lists,start,end):      #该函数实现,每调用一次函数都是调整小三角(使顶角值最大)
        root=start      #定义小三角的根节点
        child=root*2+1  #定义左孩子    
        while child<=end:    #理解记忆:end理解为小三角中的左索引,孩子的索引必须在小三角形内
            
            #依次兄弟对比、父哥对比,若都不满足则要break
            if child+1<=end and lists[child]<lists[child+1]:    #兄弟对比,找出哥哥,目的保证child为哥哥的索引         
                child=child+1                                         #child+=1            
            if lists[root]<lists[child]:  #父哥对比,大的作父      #父节点小于子节点直接交换位置,同时交换索引并更新child
                lists[root],lists[child]=lists[child],lists[root]                
                root=child                
                child=root*2+1   
            else:
                break
        print('big_endian函数:',lists)
     
    def Heap_Sort(lists):  #无序区大根堆排序    
        first=len(lists)//2 - 1    #当前堆的最后一个父结点
        
        #第一个for循环,实现对初始数列构建大顶堆
        for start in range(first,-1,-1):   #每一个start都是父节点,比如start∈索引[3,2,1,0]
            big_endian(lists,start,len(lists)-1)   #每调用一次函数都是调整小三角(使顶角值最大),从下向顶调整
        print('第一个for循环,构建大顶堆结束!')
        
        #第二个for循环,堆尾换到堆顶,但交换后新堆可能违反大顶堆的性质,每交换一次,均需新一轮的调整新堆
        for end in range(len(lists)-1,0,-1):        
            lists[0],lists[end]=lists[end],lists[0] #顶部尾部互换位置        
            big_endian(lists,0,end-1)         #重新调整子节点的顺序,从顶向下调整    
        return lists
     
    list01=[3,1,4,6,7,5,8,2]  #实现小顶堆
    print(Heap_Sort(list01))

     

     

     

    5、冒泡排序(Bubble Sort)

            冒泡排序,是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复进行,直到没有再需要交换,也就是说该数列已经排序完成。冒泡名字源自,越小的元素会经由交换慢慢“浮”到数列的顶端。 

    • 每进行一轮,会将当前轮最大值交换到最末尾
    算法描述
    • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
    • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数
    • 针对所有的元素重复以上的步骤,除了最后一个
    • 重复步骤1~3,直到排序完成。
      (1)、平均情况:第一个需要n次比较,共n个,故O(n^{2})。
      (2)、最好情况:如果是排好序的数列,只需要第一个n次即可,故 O(n)。
    动画演示

    算法分析

    最佳情况:T(n) = O(n)   最差情况:T(n) = O(n^{2})   平均情况:T(n) = O(n^{2})

    /**
     * 冒泡排序
     *
     * @param array
     * @return
     */
    public static int[] bubbleSort(int[] array) {
    	if (array.length == 0)
    		return array;
    	for (int i = 0; i < array.length; i++)
    		for (int j = 0; j < array.length - 1 - i; j++)
    			if (array[j + 1] < array[j]) {
    				int temp = array[j + 1];
    				array[j + 1] = array[j];
    				array[j] = temp;
    			}
    	return array;
    }
    
    def Bubble_Sort(lists):
        for i in range(len(lists)-1):  #外for循环,向右全比较的次数,需循环比较共计i次,-1是因为最后一个元素不必再比较,可通过前边的第i-1个元素,得出最大
            for j in range(len(lists)-i-1):  #内for循环取出第j个元素,-i因后边i个元素已经排好序,排好序的元素不必再去比较
                if lists[j] > lists[j+1]:       #如果左边的大则交换位置→保证右边大,以极大值为基准一直向右比较,直至找到该次循环的最大值放到最后边
                    lists[j], lists[j+1] = lists[j+1], lists[j]
        return lists
     
    list01=[3,1,4,6,7,5,8,2]  
    print(Bubble_Sort(list01))

     

     

     

    6、快速排序(Quick Sort)——分治法

            快速排序的。其基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字,均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序

    算法描述

       

    快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

    • 从数列中挑出一个元素,称为 “基准”(pivot);
    • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
    • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
    动画演示
    其他案例理解:http://www.webhek.com/post/comparison-sort.html

    算法分析

    最佳情况:T(n) = O(nlogn)   最差情况:T(n) = O(n2)   平均情况:T(n) = O(nlogn) 
    /**
     * 快速排序方法
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int[] QuickSort(int[] array, int start, int end) {
    	if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;
    	int smallIndex = partition(array, start, end);
    	if (smallIndex > start)
    		QuickSort(array, start, smallIndex - 1);
    	if (smallIndex < end)
    		QuickSort(array, smallIndex + 1, end);
    	return array;
    }
    /**
     * 快速排序算法——partition
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int partition(int[] array, int start, int end) {
    	int pivot = (int) (start + Math.random() * (end - start + 1));
    	int smallIndex = start - 1;
    	swap(array, pivot, end);
    	for (int i = start; i <= end; i++)
    		if (array[i] <= array[end]) {
    			smallIndex++;
    			if (i > smallIndex)
    				swap(array, i, smallIndex);
    		}
    	return smallIndex;
    }
     
    /**
     * 交换数组内两个元素
     * @param array
     * @param i
     * @param j
     */
    public static void swap(int[] array, int i, int j) {
    	int temp = array[i];
    	array[i] = array[j];
    	array[j] = temp;
    }
    
    def Quick_Sort(lists):    
        if len(lists) <= 1:
            return lists
        
        mid = lists[len(lists)//2] # 选取基准值,也可以选取第一个或最后一个元素        
        left, right = [], []       # 定义基准值左右两侧的列表
        lists.remove(mid)          # 从原始数组中移除基准值        
        for num in lists:            
            if num >= mid:             # if判断,大的放右边
                right.append(num)            
            else:                
                left.append(num)        
        return Quick_Sort(left) + [mid] + Quick_Sort(right)    


     

    7、归并排序(Merge Sort)——分治法

            归并排序,和选择排序一样,它的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(n log n)的时间复杂度,代价是需要额外的内存空间
    1、归并排序的两点改进 
    (1)、在数组长度比较短的情况下,不进行递归,而是选择其他排序方案:如插入排序; 
    (2)、归并过程中,可以用记录数组下标的方式,代替申请新内存空间 间的频繁数据移动 ,从而避免A和辅助数组间的频繁数据移动。
    注:基于关键字比较的排序算法的平均时间复杂度的下界为O(nlogn)。

    算法特点
    • 分治:归并排序,是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用
    • 稳定:归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。 
    算法描述

            基本设计思想:将原始数组A(1:n)中的元素,分成两个子集合A1(1 :n/2)和A2(n/2+1:n)。 分别对这两个子集合单独排序, 然后将已排序的两个子序列归并成一个含有n个元素的序列。 

    • 把长度为n的输入序列,分成两个长度为n/2的子序列;
    • 对这两个子序列,分别采用归并排序
    • 将两个排序好的子序列,合并成一个最终的排序序列。
    动画演示

    算法分析

    最佳情况:T(n) = O(n)  最差情况:T(n) = O(nlogn)  平均情况:T(n) = O(nlogn)
    /**
     * 归并排序
     *
     * @param array
     * @return
     */
    public static int[] MergeSort(int[] array) {
    	if (array.length < 2) return array;
    	int mid = array.length / 2;
    	int[] left = Arrays.copyOfRange(array, 0, mid);
    	int[] right = Arrays.copyOfRange(array, mid, array.length);
    	return merge(MergeSort(left), MergeSort(right));
    }
    /**
     * 归并排序——将两段排序好的数组结合成一个排序数组
     *
     * @param left
     * @param right
     * @return
     */
    public static int[] merge(int[] left, int[] right) {
    	int[] result = new int[left.length + right.length];
    	for (int index = 0, i = 0, j = 0; index < result.length; index++) {
    		if (i >= left.length)
    			result[index] = right[j++];
    		else if (j >= right.length)
    			result[index] = left[i++];
    		else if (left[i] > right[j])
    			result[index] = right[j++];
    		else
    			result[index] = left[i++];
    	}
    	return result;
    }
    
    def Merge(left,right):
        R, L=0, 0
        result=[]
        while L<len(left) and R<len(right):
            if left[L] <= right[R]:     #if判断,小的左边L+1  
                result.append(left[L])      #归并左列表
                L += 1
            else:
                result.append(right[R])     #归并右列表
                R += 1
        result += list(left[L:])    #归并剩余左列表
        result += list(right[R:])   #归并剩余右列表
        return result
    
    def MergeSort(lists):
        if len(lists) <= 1:
            return lists
        mid = len(lists)//2
        left = MergeSort(lists[:mid])   #将中间以左的元素递归
        right = MergeSort(lists[mid:])  #将中间以右的元素递归
        return Merge(left, right)       
    list01=[3,1,4,6,7,5,8,2]  
    print('MergeSort:',MergeSort(list01))

     

     

    8、计数排序(Counting Sort)——非比较的排序算法

            计数排序,是一种稳定的排序算法。其核心在于将输入的数据值,转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数
            计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置,它只能对整数进行排序

    算法描述
    • 找出待排序的数组中最大和最小的元素;
    • 统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
    • 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
    • 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。
    动画演示

    算法分析

          当输入的元素是n 个0到k之间的整数时,它的运行时间是 O(n + k)。计数排序属于非比较排序,其排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。
    最佳情况:T(n) = O(n+k)  最差情况:T(n) = O(n+k)  平均情况:T(n) = O(n+k)
    /**
     * 计数排序
     *
     * @param array
     * @return
     */
    public static int[] CountingSort(int[] array) {
    	if (array.length == 0) return array;
    	int bias, min = array[0], max = array[0];
    	for (int i = 1; i < array.length; i++) {
    		if (array[i] > max)
    			max = array[i];
    		if (array[i] < min)
    			min = array[i];
    	}
    	bias = 0 - min;
    	int[] bucket = new int[max - min + 1];
    	Arrays.fill(bucket, 0);
    	for (int i = 0; i < array.length; i++) {
    		bucket[array[i] + bias]++;
    	}
    	int index = 0, i = 0;
    	while (index < array.length) {
    		if (bucket[i] != 0) {
    			array[index] = i - bias;
    			bucket[i]--;
    			index++;
    		} else
    			i++;
    	}
    	return array;
    }
    

     

    9、桶排序(Bucket Sort)——计数排序的升级版

            桶排序,是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。
           桶排序的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排。

    算法描述
    • 人为设置一个BucketSize,作为每个桶所能放置多少个不同数值(例如当BucketSize==5时,该桶可以存放{1,2,3,4,5}这几种数字,但是容量不限,即可以存放100个3);
    • 遍历输入数据,并且把数据一个一个放到对应的桶里去;
    • 对每个不是空的桶进行排序,可以使用其它排序方法,也可以递归使用桶排序;
    • 从不是空的桶里把排好序的数据拼接起来。 
      注意,如果递归使用桶排序为各个桶排序,则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量,否则会陷入死循环,导致内存溢出。
    动画演示

    算法分析

           桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。 
    最佳情况:T(n) = O(n+k)   最差情况:T(n) = O(n+k)   平均情况:T(n) = O(n2) 
    /**
     * 桶排序
     * 
     * @param array
     * @param bucketSize
     * @return
     */
    public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {
    	if (array == null || array.size() < 2)
    		return array;
    	int max = array.get(0), min = array.get(0);
    	// 找到最大值最小值
    	for (int i = 0; i < array.size(); i++) {
    		if (array.get(i) > max)
    			max = array.get(i);
    		if (array.get(i) < min)
    			min = array.get(i);
    	}
    	int bucketCount = (max - min) / bucketSize + 1;
    	ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
    	ArrayList<Integer> resultArr = new ArrayList<>();
    	for (int i = 0; i < bucketCount; i++) {
    		bucketArr.add(new ArrayList<Integer>());
    	}
    	for (int i = 0; i < array.size(); i++) {
    		bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
    	}
    	for (int i = 0; i < bucketCount; i++) {
    		if (bucketSize == 1) { // 如果带排序数组中有重复数字时  感谢 @见风任然是风 朋友指出错误
    			for (int j = 0; j < bucketArr.get(i).size(); j++)
    				resultArr.add(bucketArr.get(i).get(j));
    		} else {
    			if (bucketCount == 1)
    				bucketSize--;
    			ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
    			for (int j = 0; j < temp.size(); j++)
    				resultArr.add(temp.get(j));
    		}
    	}
    	return resultArr;
    }
    

     

    10、基数排序(Radix Sort)——非比较的排序算法

              基数排序,也是非比较的排序算法,对每一位进行排序,从最低位开始排序,复杂度为O(kn),为数组长度,k为数组中的数的最大的位数。
              基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的

    算法描述
    • 取得数组中的最大数,并取得位数;
    • arr为原始数组,从最低位开始取每个位组成radix数组;
    • 对radix进行计数排序(利用计数排序适用于小范围数的特点)
    动画演示

    算法分析

    最佳情况:T(n) = O(n * k)   最差情况:T(n) = O(n * k)   平均情况:T(n) = O(n * k)。
    基数排序有两种方法:MSD 从高位开始进行排序 LSD 从低位开始进行排序 。

    基数排序 vs
    计数排序 vs
    桶排序

    基数排序 vs 计数排序 vs 桶排序。这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:

    基数排序:根据键值的每位数字来分配桶
    计数排序:每个桶只存储单一键值
    桶排序:每个桶存储一定范围的数值

    /**
     * 基数排序
     * @param array
     * @return
     */
    public static int[] RadixSort(int[] array) {
    	if (array == null || array.length < 2)
    		return array;
    	// 1.先算出最大数的位数;
    	int max = array[0];
    	for (int i = 1; i < array.length; i++) {
    		max = Math.max(max, array[i]);
    	}
    	int maxDigit = 0;
    	while (max != 0) {
    		max /= 10;
    		maxDigit++;
    	}
    	int mod = 10, div = 1;
    	ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
    	for (int i = 0; i < 10; i++)
    		bucketList.add(new ArrayList<Integer>());
    	for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
    		for (int j = 0; j < array.length; j++) {
    			int num = (array[j] % mod) / div;
    			bucketList.get(num).add(array[j]);
    		}
    		int index = 0;
    		for (int j = 0; j < bucketList.size(); j++) {
    			for (int k = 0; k < bucketList.get(j).size(); k++)
    				array[index++] = bucketList.get(j).get(k);
    			bucketList.get(j).clear();
    		}
    	}
    	return array;
    }
    

     

    参考文章
    算法学习总结(2)——温故十大经典排序算法
    在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具
    用HTML5实现的各种排序算法的动画比较

     

     

     

    API

             (Application Programming Interface,应用程序编程接口)是一些预先定义的函数,目的是提供应用程序与开发人员基于某软件或硬件得以访问一组例程的能力,而又无需访问源码,或理解内部工作机制的细节。
    如何设计出一些优雅的API接口呢?—转自知乎
    1. 拼写要准确接口函数一旦发布就不能改了,要保持兼容性,拼写错误也不能改了,所以要仔细检查拼写,否则会被同行嘲笑很多年。著名悲剧:unix 的 creat
    2. 不仅是英文单词不要拼错,时态也不要错。比如:返回bool的判断函数,单数要用 is 复数要用are,这样你的命名就和文档中的描述保持了一致性。表示状态的变量或者函数要注意时态,比如 onXxxxChanged 表示xxx已经变化了,isConnecting表示正在连接。 正确的时态可以给使用者传递更丰富的信息。
    3. 函数最好是动宾结构动宾结构就是  doSomething,这样的函数命名含义明确比如: openFile, allocBuffer, setName如果这个函数的动词宾语就是这个对象本身,那么可以省略掉宾语
    4. 属性命名最好是定语+名词比如 fileName, maxSize, textColor
    5. 不要用生僻单词,这不是秀英语的地方,也不要用汉语拼音比如:rendezvous,估计大多数人要去查词典才知道什么意思,这个词源自法语,是约会的意思。Symbian OS里有个用它命名的函数,开发Symbian的是英国人,也许人家觉得很平常吧,反正我是查了词典才知道的。
    6. 不要自己发明缩写除非是约定俗成已经被广泛使用的缩写,否则老老实实用完整拼写。坏例子:  count->cnt, manager->mngr password->pw button->btn现代的IDE都有很好的自动完成功能,名字长一点没关系的,可读性更重要。
    7. 保持方法的对称性,有些方法一旦出现就应该是成对的,比如 有open就要有close,有alloc就要有free,有add就要有remove,这些单词基本是固定搭配的,使用者就很容易理解。如果 open对应clear就有点让人困惑了。

    8. 站在使用者的角度去思考,API设计也要讲究用户体验。好的API设计应该是符合直觉,能望文生义的,让使用者能用尽量简洁的代码完成调用。我最欣赏的API设计是 Qt 和 .Net Framework。

    Qt之API Design Principles

     

     

    Temp文件(Local Computer)

    Eric之Py:Eric20180524py_gui.py记录文件

    1、20180717文件查找:
    因为昨天晚上安装Js框架,需要python2依赖,查找C盘仲Python2软件路径,避免与Python3冲突。


    2、20180928,将该环境变量删除:G:\Program Files (x86)\Python27
    原因:怕影响TFOD API安装不成功!


     

    版权声明

    # -*- coding: utf-8 -*-
    """
    Copyright © 2018, Jason Niu. 
    All Rights Reserved.
    
    Author: Jason Niu
    Date:2018.06.26
    Natural Language: English
    
    Copyright Notice
    System copyrights this specification. 
    No part of this specification may be reproduced in any form or means, without the prior written consent of Jason Niu.
    
    Disclaimer
    This specification is preliminary and is subject to change at any time without notice. 
    Jason Niu assumes no responsibility for any errors contained herein.
    
    Release history
    Version 1.0
    
    """

     

     

    相关文章
    Python自带:python常用方法(自带的)、常见概念详细攻略
    Python实现读入、写出各自类型如txt、csv等文件之详细攻略
    Python:将常用的函数进行封装
    Python自带:python自带的以字母开头的函数或方法集合
    BlockChain:BTC、ETH钱包地址集合
    CUMCM:全国大学生数模竞赛历年考察知识点总结
    Personal preference

     

     

     

     

    展开全文
  • c++中的algorithm

    千次阅读 2018-08-18 22:36:58
    c++中的algorithm库,包含了所有vector、list、set、map操作能想到的一些函数,如查找,替换、排序、计数等常用的功能全部在里面,在这里虽然不像Java那样完全面向对象,方法全部在类里面,但是熟读algorithm库还是...
  • algorithm

    2020-10-17 09:50:17
    min max swap
  • Algorithm

    2018-05-19 23:14:19
    //模板函数的使用 template &amp;lt;typename T&amp;gt; T Add(T left,T right) { return left + right; } int main() { Add(1,2); Add(1.0,2.0); Add('1','1');... //模板函数不会...
  • 【C/C++】【Algorithm

    千次阅读 2019-06-26 11:46:53
    人民公园的门口有10级台阶,如果一次只能上一级或2级台阶,一共有多少种上法_作业帮 这数学题能不能用C语言解题-CSDN论坛
  • c++ algorithm 函数简介

    万次阅读 2016-05-17 20:57:28
    algorithm编辑 algorithm意为"演算法",是C++的标准模版库(STL)中最重要的头文件之一,提供了大量基于迭代器的非成员模版函数。 编程语言C++ 类 别C++标准库 头文件#include 命名空间using namespace std; ...
  • C++/C++11中头文件algorithm的使用

    万次阅读 2019-06-10 19:42:56
    algorithm>是C++标准程序库中的一个头文件,定义了C++ STL标准中的基础性的算法(均为函数模板)。<algorithm>定义了设计用于元素范围的函数集合。任何对象序列的范围可以通过迭代器或指针访问。 std::...
  • Hungarian algorithm(匈牙利算法)

    千次阅读 2018-01-28 08:42:32
    看到两个比较好的Hungarian algorithm教程: 1、The Hungarian algorithm: An example 2、Hungarian Maximum Matching Algorithm
  • No Algorithm found for: 这里是地址范围
  • No Algorithm found for: 08000000H - 08001557H  今天在用mdk编译stm32的usb程序时,碰到一个错误,请教高手材质如何解决。  就是没有选择芯片型号  言简意赅,上图大家一看便知 重新编译下载即可...
  • latex 算法,算法包 algorithmalgorithm2e

    万次阅读 多人点赞 2018-01-13 19:31:26
    发现 latex 还有专门排版 算法伪...发现 algorithm2e 工具包比较好用,调用时: \usepackage[ruled,linesnumbered]{algorithm2e} 该工具包的使用手册下载地址: http://mlg.ulb.ac.be/files/algorithm2e.pdf
  • latex algorithm 用法

    万次阅读 2014-05-20 19:06:30
    \begin{algorithm}[t] \caption{\small Solving problem (\ref{eq_genpro}) by IRNN} \textbf{Input:} $\mu>L(f)$ - A Lipschitz constant of $\nabla f({\X})$.\\ \textbf{Initialize:} $k=0$, ${\
  • Keil 5 for ARM, ST-Link v2, STM32F091RC 下载软件时...No Algorithm found for: 08000000H - 08001AF7H Erase skipped! Error: Flash Download failed - "Cortex-M0" 解决方法: Option for target 'P
  • 把自己的MDK开发环境有4.2升级到了4.
  • 首先进入linux服务器,ssh客户端连接不进去的时候可以先用别的客户端连进去,我就是暂时用的winscp连进去,进去后 在/etc/ssh/sshd_config文件中追加 Ciphers aes128-cbc,aes192-cbc,aes256-cbc,aes128-ctr,aes192-...
  • Latex之使用algorithm2e包来写算法

    千次阅读 2019-05-04 17:19:37
    algorithm2e是latex上用来写算法的包。 目前还有很多,比如algorithmc等。两者的语法不同。 使用时要先导入包: \usepackage[ruled,linesnumbered]{algorithm2e} 下面贴出一个示例: \begin{algorithm}[t] \...
  • Server responded "Algorithm negotiation failed"【SSH Secure链接服务器错误】
1 2 3 4 5 ... 20
收藏数 1,122,647
精华内容 449,058
关键字:

algorithm