你知道如何自定義sort函數(shù)中的比較函數(shù)
如何自定義sort函數(shù)中的比較函數(shù)
在做劍指offer時，有一道題：
題目描述
輸入一個正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來排成一個數(shù)，打印能拼接出的所有數(shù)字中最小的一個。例如輸入數(shù)組{3，32，321}，則打印出這三個數(shù)字能排成的最小數(shù)字為321323。
思路
自定義比較器，若a+b>b+a則a>b，即”3”+”23”>”23”+”3”則3>23，并且我們希望在排序的時候?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的時候就是升序排列了呢？十分不解，在網(wǎng)上搜了好多資料，最后看到了c++的技術(shù)文檔，醍醐灌頂！??！強烈推薦直接看技術(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ù)返回一個bool類型的值，這個值表示了在嚴(yán)格弱排序中（可以理解為升序排序）第一參數(shù)是否位于第二個參數(shù)之前。
也就是說如果comp返回true，則第一個參數(shù)小于第二個參數(shù)，sort根據(jù)compare的返回值將第一個參數(shù)排在第二個參數(shù)之前。
如果comp返回false，則第一個參數(shù)大于第二個參數(shù)，sort根據(jù)compare的返回值將第一個參數(shù)排在第二個參數(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”;
事實上ab>ba，所以comp會返回false，sort根據(jù)compare返回的false將s2排列在s1之前，也就是排列成”23”,”3”這也就是我們想要的結(jié)果。
總結(jié)起來就是
sort函數(shù)根據(jù)comp函數(shù)的返回值，對comp函數(shù)的兩個參數(shù)排序。
如果comp返回true，排序為“參數(shù)1”“參數(shù)2”，否則排序為“參數(shù)2”“參數(shù)1”。
- 想要升序排列，則return parameter1<parameter2
- 想要降序排列，則return parameter1>parameter2
sort()基本用法
做ACM題的時候，排序是一種經(jīng)常要用到的操作。如果每次都自己寫個冒泡之類的O(n^2)排序，不但程序容易超時，而且浪費寶貴的比賽時間，還很有可能寫錯。STL里面有個sort函數(shù)，可以直接對數(shù)組排序，復(fù)雜度為n*log2(n)。使用這個函數(shù)，需要包含頭文件。
這個函數(shù)可以傳兩個參數(shù)或三個參數(shù)。第一個參數(shù)是要排序的區(qū)間首地址，第二個參數(shù)是區(qū)間尾地址的下一地址。也就是說，排序的區(qū)間是[a,b)。簡單來說，有一個數(shù)組int a[100]，要對從a[0]到a[99]的元素進行排序，只要寫sort(a,a+100)就行了，默認(rèn)的排序方式是升序。
拿我出的“AC的策略”這題來說，需要對數(shù)組t的第0到len-1的元素排序，就寫sort(t,t+len);
對向量v排序也差不多，sort(v.begin(),v.end());
排序的數(shù)據(jù)類型不局限于整數(shù)，只要是定義了小于運算的類型都可以，比如字符串類string。
如果是沒有定義小于運算的數(shù)據(jù)類型，或者想改變排序的順序，就要用到第三參數(shù)——比較函數(shù)。比較函數(shù)是一個自己定義的函數(shù)，返回值是bool型，它規(guī)定了什么樣的關(guān)系才是“小于”。想把剛才的整數(shù)數(shù)組按降序排列，可以先定義一個比較函數(shù)cmp
bool cmp(int a,int b)
{
return a>b;
}
排序的時候就寫sort(a,a+100,cmp);
假設(shè)自己定義了一個結(jié)構(gòu)體node
struct node{
int a;
int b;
double c;
}
有一個node類型的數(shù)組node arr[100]，想對它進行排序：先按a值升序排列，如果a值相同，再按b值降序排列，如果b還相同，就按c降序排列。就可以寫這樣一個比較函數(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;
}
排序時寫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;
}
對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);
對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);
對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)；
對結(jié)構(gòu)體一級排序
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);
對結(jié)構(gòu)體
struct In
{
int x;
int y;
}s[100];
//按照x從小到大排序，當(dāng)x相等時按照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);
對字符串進行排序
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);
計算幾何中求凸包的cmp
int cmp(const void *a,const void *b) //重點cmp函數(shù)，把除了1點外的所有點，旋轉(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;
}
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
通過點擊程序界面上不同的布局按鈕,使主工作區(qū)呈現(xiàn)出不同的頁面布局,多個布局之間可以通過點擊不同布局按鈕切換,支持的最多的窗口為9個,不同布局下窗口數(shù)隨之變化,這篇文章主要介紹了Qt實現(xiàn)手動切換多種布局的完美方案,需要的朋友可以參考下2024-07-07
QDockWidget類提供了一個小部件,可以停靠在QMainWindow中,也可以作為桌面上的頂級窗口浮動,本文主要介紹了QT中QDockWidget控件的使用小結(jié),感興趣的可以了解一下2024-01-01
這篇文章主要為大家詳細(xì)介紹了用C語言程序?qū)崿F(xiàn)黎曼和求定積分，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
在C語言中自定義類型主要有結(jié)構(gòu)體類型、位段、枚舉類型、聯(lián)合體類型，自定義類型是面試常會碰到的內(nèi)容，今天我們來詳細(xì)了解一下它2022-02-02
Lambda函數(shù)的代碼部分在代碼段中，被捕獲的變量存儲在Lambda函數(shù)對象的內(nèi)部，這些變量的存儲位置取決于Lambda函數(shù)對象的存儲位置,這篇文章主要介紹了C/C++函數(shù)的存儲位置和占用空間,需要的朋友可以參考下2023-06-06
這篇文章主要介紹了C語言的空類型指針,空指針,野指針的詳解及用法示例，介紹了其相關(guān)概念，然后分享了幾種用法，具有一定參考價值。需要的朋友可以了解下。2021-09-09
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)三子棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-01-01
在我們?nèi)粘５纳钪忻總€人都或多或少存在一個"外號"，例如《西游記》中孫悟空就有諸多外號：美猴王，孫行者，齊天大圣等等。那么在C++中，也可以給一個已經(jīng)存在的變量取別名，這就是引用。那么接下來深入來探討一下引用2022-05-05
下面小編就為大家?guī)硪黄狢# 使用反射來實現(xiàn)對象的深度復(fù)制方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
C++使用WideCharToMultiByte函數(shù)生成UTF-8編碼文件的方法
用來映射Unicode字符串的WideCharToMultiByte函數(shù)經(jīng)常被用來進行UTF-8編碼的轉(zhuǎn)換,以下我們將看到C++使用WideCharToMultiByte函數(shù)生成UTF-8編碼文件的方法,首先先來對WideCharToMultiByte作一個詳細(xì)的了解:2016-06-06