c++ sort 类的一点区别

朴灿烈づ我的快乐病毒、 2022-06-09 08:22 130阅读 0赞

**STL的sort()算法，数据量大时采用Quick Sort，分段递归排序，一旦分段后的数据量小于某个门槛，为避免Quick Sort的递归调用带来过大的额外负荷，就改用Insertion Sort。如果递归层次过深，还会改用Heap Sort。STL sort算法(以上三种算法的综合) -- Introspective Sorting(内省式排序)。**

**I）Sort函数包含在头文件为\#include<algorithm>的c++标准库中！  
II）Sort函数有三个参数：  
（1）第一个是要排序的数组的起始地址。  
（2）第二个是结束的地址（最后一位要排序的地址）  
（3）第三个参数是排序的方法，可以是从大到小也可是从小到大，还可以不写第三个参数，此时默认的排序方法是从小到大排序。**

STL里面有个sort函数，可以直接对数组排序，复杂度为n\*log2(n)。

**使用第一个版本是对\[first,last)进行升序排序，默认操作符为"<"，第二个版本使用comp函数进行排序控制，comp包含两个在\[first,last)中对应的值，如果使用"<"则为升序排序，如果使用">"则为降序排序，分别对int、float、char以及结构体排序:**

**sort\_main函数**

#include "stdafx.h"
    #include
      
       
    #include
       
        
    #include
        
         
    #include 
         
          
    using namespace std;
    
    bool compare(const string &a, const string &b){
    	return a > b;
    }
    bool cmp(const int &a, const int &b){
    	return a > b;
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	vector
          
            res = { "ABC", "ACB", "BAC", "BCA", "CAB", "CBA"}; vector
           
             B = { 1, 2, 3, 4, 5 }; for (int i = 0; i < res.size(); i++){ cout << res[i] << " "; } cout << endl; for (int i = 0; i < B.size(); i++){ cout << B[i] << " "; } cout << endl; sort(B.begin(), B.end(), cmp); sort(res.begin(), res.end(), compare); for (int i = 0; i < res.size(); i++){ cout << res[i] << " "; } cout << endl; for (int i = 0; i < B.size(); i++){ cout << B[i] << " "; } cout << endl; system("pause"); return 0; }

输出：

ABC ACB BAC BCA CAB CBA  
1 2 3 4 5  
CBA CAB BCA BAC ACB ABC  
5 4 3 2 1

**sort\_class函数**

class Test{
    public:
    	static bool compare(const string &a, const string &b){
    		return a > b;
    	}
    	static bool cmp(const int &a, const int &b){
    		return a > b;
    	}
    	void test(){
    		vector
       
         res = { "ABC", "ACB", "BAC", "BCA", "CAB", "CBA" };
    		vector
        
          B = { 1, 2, 3, 4, 5 };
    		for (int i = 0; i < res.size(); i++){
    			cout << res[i] << " ";
    		}
    		cout << endl;
    		for (int i = 0; i < B.size(); i++){
    			cout << B[i] << " ";
    		}
    		cout << endl;
    		sort(B.begin(), B.end(), cmp);
    		sort(res.begin(), res.end(), compare);
    		for (int i = 0; i < res.size(); i++){
    			cout << res[i] << " ";
    		}
    		cout << endl;
    		for (int i = 0; i < B.size(); i++){
    			cout << B[i] << " ";
    		}
    		cout << endl;
    	}
    };
    int _tmain(int argc, _TCHAR* argv[])
    {
    	Test t;
    	t.test();
    	system("pause");
    	return 0;
    }

输出：

ABC ACB BAC BCA CAB CBA  
1 2 3 4 5  
CBA CAB BCA BAC ACB ABC  
5 4 3 2 1

这里sort\_main函数与sort\_class函数，有一点区别的是

sort\_main函数要申明为

bool compare(const string &a, const string &b)\{  
return a > b;  
\}

sort\_class函数要申明为

static bool compare(const string &a, const string &b)\{  
return a > b;  
\}

sort\_class函数没有申明static,会出错（没有深入研究，先记录下来）

错误4error C2780: “void std::sort(\_RanIt,\_RanIt)”: 应输入 2 个参数，却提供了 3 个

错误3error C3867: “Test::compare”:  函数调用缺少参数列表；请使用“&Test::compare”创建指向成员的指针

gcc下编译，sort\_class函数没有申明static,也会出错

In file included from a.cc:2:  
./solution.h:10:32: error: reference to non-static member function must be called  
sort(res.begin(), res.end(), compare);  
1 error generated.

gcc下编译，sort\_class函数申明static，但是参数没有申明为const 也会出错

static bool compare(string &a, string &b))\{  
return a > b;  
\}

In file included from a.cc:1:  
In file included from /home/web/newjudge/include/nc\_tools.h:5:  
In file included from /usr/bin/../lib/gcc/x86\_64-linux-gnu/4.8/../../../../include/c++/4.8/algorithm:62:  
/usr/bin/../lib/gcc/x86\_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/stl\_algo.h:2287:28: error: binding of reference to type 'basic\_string<\[3 \* ...\]>' to a value of type 'const basic\_string<\[3 \* ...\]>' drops qualifiers  
while (\_\_comp(\*\_\_first, \_\_pivot))~~~~~~  
/usr/bin/../lib/gcc/x86\_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/stl\_algo.h:2319:19: note: in instantiation of function template specialization 'std::\_\_unguarded\_partition<\_\_gnu\_cxx::\_\_normal\_iterator<std::basic\_string \*, std::vector<std::basic\_string, std::allocator<std::basic\_string > > >, std::basic\_string, bool (\*)(std::basic\_string &, std::basic\_string &)>' requested here  
return std::\_\_unguarded\_partition(\_\_first + 1, \_\_last, \*\_\_first, \_\_comp);  
/usr/bin/../lib/gcc/x86\_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/stl\_algo.h:2360:11: note: in instantiation of function template specialization 'std::\_\_unguarded\_partition\_pivot<\_\_gnu\_cxx::\_\_normal\_iterator<std::basic\_string \*, std::vector<std::basic\_string, std::allocator<std::basic\_string > > >, bool (\*)(std::basic\_string &, std::basic\_string &)>' requested here  
std::\_\_unguarded\_partition\_pivot(\_\_first, \_\_last, \_\_comp);  
/usr/bin/../lib/gcc/x86\_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/stl\_algo.h:5512:9: note: in instantiation of function template specialization 'std::\_\_introsort\_loop<\_\_gnu\_cxx::\_\_normal\_iterator<std::basic\_string \*, std::vector<std::basic\_string, std::allocator<std::basic\_string > > >, long, bool (\*)(std::basic\_string &, std::basic\_string &)>' requested here  
std::\_\_introsort\_loop(\_\_first, \_\_last,  
./solution.h:10:3: note: in instantiation of function template specialization 'std::sort<\_\_gnu\_cxx::\_\_normal\_iterator<std::basic\_string \*, std::vector<std::basic\_string, std::allocator<std::basic\_string > > >, bool (\*)(std::basic\_string &, std::basic\_string &)>' requested here  
sort(res.begin(), res.end(), compare);  
In file included from a.cc:1:  
In file included from /home/web/newjudge/include/nc\_tools.h:5:  
In file included from /usr/bin/../lib/gcc/x86\_64-linux-gnu/4.8/../../../../include/c++/4.8/algorithm:62:  
/usr/bin/../lib/gcc/x86\_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/stl\_algo.h:2290:18: error: binding of reference to type 'basic\_string<\[3 \* ...\]>' to a value of type 'const basic\_string<\[3 \* ...\]>' drops qualifiers  
while (\_\_comp(\_\_pivot, \*\_\_last))  
2 errors generated.