你知道如何自定義sort函數(shù)中的比較函數(shù)
如何自定義sort函數(shù)中的比較函數(shù)
在做劍指offer時(shí)，有一道題：
題目描述
輸入一個(gè)正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來排成一個(gè)數(shù)，打印能拼接出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{3，32，321}，則打印出這三個(gè)數(shù)字能排成的最小數(shù)字為321323。
思路
自定義比較器，若a+b>b+a則a>b，即”3”+”23”>”23”+”3”則3>23，并且我們希望在排序的時(shí)候?qū)?3排在3的前面，也就是升序排列。
class Solution {
public:
static bool compare(const string& s1, const string& s2)
{
string ab = s1 + s2;
string ba = s2 + s1;
return ab < ba; //升序排列。如改為ab > ba, 則為降序排列
}
string PrintMinNumber(vector<int> numbers)
{
string result;
if(numbers.size() <= 0) return result;
vector<string> num2str;
for(int i = 0; i < numbers.size(); i++)
{
stringstream ss;
ss << numbers[i];
string s = ss.str();
num2str.push_back(s);
}
sort(num2str.begin(), num2str.end(), compare);
for(int i = 0; i < num2str.size(); i++)
{
result.append(num2str[i]);
}
return result;
}
};
這道題的解法中用到了自定義比較器。也就是自定義了campare函數(shù)。
但是為什么當(dāng)ab<ba的時(shí)候就是升序排列了呢？十分不解，在網(wǎng)上搜了好多資料，最后看到了c++的技術(shù)文檔，醍醐灌頂?。?！強(qiáng)烈推薦直接看技術(shù)文檔，比在網(wǎng)上查來查去明白的更快！
http://www.cplusplus.com/reference/algorithm/sort/
// sort algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::sort
#include <vector> // std::vector
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;
}
可以看到comp的定義：comp函數(shù)返回一個(gè)bool類型的值，這個(gè)值表示了在嚴(yán)格弱排序中（可以理解為升序排序）第一參數(shù)是否位于第二個(gè)參數(shù)之前。
也就是說如果comp返回true，則第一個(gè)參數(shù)小于第二個(gè)參數(shù)，sort根據(jù)compare的返回值將第一個(gè)參數(shù)排在第二個(gè)參數(shù)之前。
如果comp返回false，則第一個(gè)參數(shù)大于第二個(gè)參數(shù)，sort根據(jù)compare的返回值將第一個(gè)參數(shù)排在第二個(gè)參數(shù)之后。
- 傳入A,B，定義bool myfunction (int i,int j) { return (i<j); },作為comp函數(shù)，則排列AB。
- 傳入BA，則排列AB。
可以看出是升序排列的。（sort函數(shù)默認(rèn)的comp函數(shù)也是默認(rèn)升序的）
而如果我們定義bool myfunction (int i,int j) { return (i>j); },作為comp函數(shù)，
- 傳入AB，返回false，則排列為BA，
- 傳入BA，返回true，排列為BA。
是降序排列的。
回到最初的問題中
static bool compare(const string& s1, const string& s2)
{
string ab = s1 + s2;
string ba = s2 + s1;
return ab < ba; //升序排列。如改為ab > ba, 則為降序排列
}
我們可以看出 如果s1=”3”， s2=”23”
ab = “323”;
ba = “233”;
事實(shí)上ab>ba，所以comp會(huì)返回false，sort根據(jù)compare返回的false將s2排列在s1之前，也就是排列成”23”,”3”這也就是我們想要的結(jié)果。
總結(jié)起來就是
sort函數(shù)根據(jù)comp函數(shù)的返回值，對(duì)comp函數(shù)的兩個(gè)參數(shù)排序。
如果comp返回true，排序?yàn)椤皡?shù)1”“參數(shù)2”，否則排序?yàn)椤皡?shù)2”“參數(shù)1”。
- 想要升序排列，則return parameter1<parameter2
- 想要降序排列，則return parameter1>parameter2
sort()基本用法
做ACM題的時(shí)候，排序是一種經(jīng)常要用到的操作。如果每次都自己寫個(gè)冒泡之類的O(n^2)排序，不但程序容易超時(shí)，而且浪費(fèi)寶貴的比賽時(shí)間，還很有可能寫錯(cuò)。STL里面有個(gè)sort函數(shù)，可以直接對(duì)數(shù)組排序，復(fù)雜度為n*log2(n)。使用這個(gè)函數(shù)，需要包含頭文件。
這個(gè)函數(shù)可以傳兩個(gè)參數(shù)或三個(gè)參數(shù)。第一個(gè)參數(shù)是要排序的區(qū)間首地址，第二個(gè)參數(shù)是區(qū)間尾地址的下一地址。也就是說，排序的區(qū)間是[a,b)。簡(jiǎn)單來說，有一個(gè)數(shù)組int a[100]，要對(duì)從a[0]到a[99]的元素進(jìn)行排序，只要寫sort(a,a+100)就行了，默認(rèn)的排序方式是升序。
拿我出的“AC的策略”這題來說，需要對(duì)數(shù)組t的第0到len-1的元素排序，就寫sort(t,t+len);
對(duì)向量v排序也差不多，sort(v.begin(),v.end());
排序的數(shù)據(jù)類型不局限于整數(shù)，只要是定義了小于運(yùn)算的類型都可以，比如字符串類string。
如果是沒有定義小于運(yùn)算的數(shù)據(jù)類型，或者想改變排序的順序，就要用到第三參數(shù)——比較函數(shù)。比較函數(shù)是一個(gè)自己定義的函數(shù)，返回值是bool型，它規(guī)定了什么樣的關(guān)系才是“小于”。想把剛才的整數(shù)數(shù)組按降序排列，可以先定義一個(gè)比較函數(shù)cmp
bool cmp(int a,int b)
{
return a>b;
}
排序的時(shí)候就寫sort(a,a+100,cmp);
假設(shè)自己定義了一個(gè)結(jié)構(gòu)體node
struct node{
int a;
int b;
double c;
}
有一個(gè)node類型的數(shù)組node arr[100]，想對(duì)它進(jìn)行排序：先按a值升序排列，如果a值相同，再按b值降序排列，如果b還相同，就按c降序排列。就可以寫這樣一個(gè)比較函數(shù)：
以下是代碼片段：
bool cmp(node x,node y)
{
if(x.a!=y.a) return x.a
if(x.b!=y.b) return x.b>y.b;
return return x.c>y.c;
}
排序時(shí)寫sort(arr,a+100,cmp);
qsort(s[0],n,sizeof(s[0]),cmp);
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
對(duì)int類型數(shù)組排序
int num[100];
Sample:
int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
}
qsort(num,100,sizeof(num[0]),cmp);
對(duì)char類型數(shù)組排序（同int類型）
char word[100];
Sample:
int cmp( const void *a , const void *b )
{
return *(char *)a - *(int *)b;
}
qsort(word,100,sizeof(word[0]),cmp);
對(duì)double類型數(shù)組排序（特別要注意）
double in[100];
int cmp( const void *a , const void *b )
{
return *(double *)a > *(double *)b ? 1 : -1;
}
qsort(in,100,sizeof(in[0]),cmp)；
對(duì)結(jié)構(gòu)體一級(jí)排序
struct In
{
double data;
int other;
}s[100]
//按照data的值從小到大將結(jié)構(gòu)體排序,關(guān)于結(jié)構(gòu)體內(nèi)的排序關(guān)鍵數(shù)據(jù)data的類型可以很多種，參考上面的例子寫
int cmp( const void *a ,const void *b)
{
return ((In *)a)->data - ((In *)b)->data ;
}
qsort(s,100,sizeof(s[0]),cmp);
對(duì)結(jié)構(gòu)體
struct In
{
int x;
int y;
}s[100];
//按照x從小到大排序，當(dāng)x相等時(shí)按照y從大到小排序
int cmp( const void *a , const void *b )
{
struct In *c = (In *)a;
struct In *d = (In *)b;
if(c->x != d->x) return c->x - d->x;
else return d->y - c->y;
}
qsort(s,100,sizeof(s[0]),cmp);
對(duì)字符串進(jìn)行排序
struct In
{
int data;
char str[100];
}s[100];
//按照結(jié)構(gòu)體中字符串str的字典順序排序
int cmp ( const void *a , const void *b )
{
return strcmp( ((In *)a)->str , ((In *)b)->str );
}
qsort(s,100,sizeof(s[0]),cmp);
計(jì)算幾何中求凸包的cmp
int cmp(const void *a,const void *b) //重點(diǎn)cmp函數(shù)，把除了1點(diǎn)外的所有點(diǎn)，旋轉(zhuǎn)角度排序
{
struct point *c=(point *)a;
struct point *d=(point *)b;
if( calc(*c,*d,p[1]) < 0) return 1;
else if( !calc(*c,*d,p[1]) && dis(c->x,c->y,p[1].x,p[1].y) < dis(d->x,d->y,p[1].x,p[1].y)) //如果在一條直線上，則把遠(yuǎn)的放在前面
return 1;
else return -1;
}
以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
C++?JSON庫?nlohmann::basic_json::array?的用法示例詳解
nlohmann::json是一個(gè)C++的JSON庫，它提供了一種容易和直觀的方法來處理JSON數(shù)據(jù)，nlohmann::json::array()是用來創(chuàng)建一個(gè)JSON數(shù)組的方法，這篇文章主要介紹了C++ JSON庫nlohmann::basic_json::array的用法,需要的朋友可以參考下2023-06-06
回溯在迷宮搜索中使用很常見，就是這條路走不通，然后返回前一個(gè)路口，繼續(xù)下一條路?；厮菟惴ㄕf白了就是窮舉法，下面讓我們一起來看看回溯算法中深度優(yōu)先搜索吧2023-01-01
這篇文章主要介紹了C++大小字母的轉(zhuǎn)換方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08
這篇文章主要為大家介紹了C語言 scanf的工作原理，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
這篇文章主要介紹了C語言變量類型的深入分析的相關(guān)資料,需要的朋友可以參考下2017-07-07
C++實(shí)現(xiàn)Dijkstra(迪杰斯特拉)算法
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)Dijkstra(迪杰斯特拉)算法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-05-05
這篇文章主要介紹了C++實(shí)現(xiàn)raw_input的方法,通過C++來實(shí)現(xiàn)Python中發(fā)raw_input的方法,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2014-10-10
輪廓圖也叫行政區(qū)劃，這里的輪廓圖是指百度地圖的區(qū)域輪廓圖。本文將為大家介紹QT如何實(shí)現(xiàn)在線輪廓圖的編寫，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2021-12-12
這篇文章主要給大家介紹了關(guān)于C語言中可變參數(shù)的使用方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
線段樹在一些acm題目中經(jīng)常見到,這種數(shù)據(jù)結(jié)構(gòu)主要應(yīng)用在計(jì)算幾何和地理信息系統(tǒng)中,這篇文章主要給大家介紹了關(guān)于線段樹以及C++實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下2021-07-07