sort()函數是C++中的排序函數其頭檔案為:#include<algorithm>頭檔案;
qsort()是C中的排序函數,其頭檔案為:#include<stdlib.h>
qsort()----六類qsort排序方法
qsort函數很好用,但有時不太會用比如按結構體一級排序、二級排序、字元串排序等。
函數原型:
void qsort(void *base, size_t nelem, size_t width, int (*fcmp)(const void*,const void *))
輸入參數:
Base:待排序的數組
nelem:數組元數的個數(長度)
width:每一個元素所占存儲空間的大小
fcmp:用于對數組元素進行比較的函數的指針(該函數是要自己寫的),傳回值為1或-1(p1>p2則傳回-1,p1<p2則傳回1,p1==p2則傳回0),size_t是int
輸出參數:base 以升序排列
以下是其具體分類及用法(若無具體說明是以降序排列):
(1)對一維數組排序:
(Element_type 是一位數組中存放的資料類型,可以是char,int,float,double,ect)
int comp(const void *p1,const void *p2)
{
return *((Element_type*)p2)>*((Element_type*)p1)?1:-1;
}
int main()
Element_type list[MAX];
initial(list);//這是對數組list[max]初始化
qsort(list, sizeof(list),sizeof(Element_type),Comp);//調用函數qsort
return 0;
(2)對字元串排序:
int Comp(const void *p1,const void *p2)
return strcmp((char *)p2,(char *)p1);
char a[MAX1][MAX2];
initial(a);
qsort(a,lenth,sizeof(a[0]),Comp);
//lenth 為數組a的長度
(3)按結構體中某個關鍵字排序(對結構體一級排序):
typedef struct Node
double data;
int other;
}Node;
return (*(Node *)p2).data > (*(Node *)p1).data ? 1 : -1;
qsort(s,100,sizeof(s[0]),Comp);
(4)按結構體中多個關鍵字排序(對結構體多級排序)[以二級為例]:
struct Node
int x;
int y;
}s[100];
//按照x從小到大排序,當x相等時按y從大到小排序(這是3跟4的差別)
struct Node *c=(Node *)p1;
struct Node *d=(Node *)p2;
if(c->x!=d->x)
return c->x-d->x;
else
return d->y - c->y;
(5)對結構體中字元串進行排序:
int data;
char str[100];
//按照結構體中字元串str 的字典序排序
return strcmp((*(Node *)p1).str,(*(Node *)p2).str);
qsort(s,100,sizeof(s[0],Comp);
(6)計算幾何中求凸包的Comp
int Comp(const void *p1,const void *p2)//重點Comp函數,把除了1點外的所有的點旋轉角度排序
struct point *c=(point *)p1;
struct point *d=(point *)p2;
if( cacl(*c, *d,p[1])<0)
return 1;
elseif(!cacl(*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))
//如果在一條直線上,則把遠的放在前面
return -1;
}
sort()函數用法
sort 對給定區間所有元素進行排序
stable_sort 對給定區間所有元素進行穩定排序
partial_sort 對給定區間所有元素部分排序
partial_sort_copy 對給定區間複制并排序
nth_element 找出給定區間的某個位置對應的元素
is_sorted 判斷一個區間是否已經排好序
partition 使得符合某個條件的元素放在前面
stable_partition 相對穩定的使得符合某個條件的元素放在前面
文法描述為:
(1)sort(begin,end),表示一個範圍,例如:
int _tmain(int argc, _TCHAR* argv[])
int a[20]={2,4,1,23,5,76,0,43,24,65},i;
for(i=0;i<20;i++)
cout<<a[i]<<endl;
sort(a,a+20);
輸出結果将是把數組a按升序排序,說到這裡可能就有人會問怎麼樣用它降序排列呢?這就是下一個讨論的内容。
(2)sort(begin,end,compare)
一種是自己編寫一個比較函數來實作,接着調用三個參數的sort:sort(begin,end,compare)就成了。對于list容器,這個方法也适用,把compare作為sort的參數就可以了,即:sort(compare)。
1)自己編寫compare函數:
bool compare(int a,int b)
return a<b; //升序排列,如果改為return a>b,則為降序
sort(a,a+20,compare);
2)更進一步,讓這種操作更加能适應變化。也就是說,能給比較函數一個參數,用來訓示是按升序還是按降序排,這回輪到函數對象出場了。
為了描述友善,我先定義一個枚舉類型EnumComp用來表示升序和降序。很簡單:
enum Enumcomp{ASC,DESC};
然後開始用一個類來描述這個函數對象。它會根據它的參數來決定是采用“<”還是“>”。
class compare
private:
Enumcomp comp;
public:
compare(Enumcomp c):comp(c) {};
bool operator () (int num1,int num2)
switch(comp)
case ASC:
return num1<num2;
caseDESC:
return num1>num2;
};
接下來使用sort(begin,end,compare(ASC))實作升序,sort(begin,end,compare(DESC))實作降序。
主函數為:
sort(a,a+20,compare(DESC));
3)其實對于這麼簡單的任務(類型支援“<”、“>”等比較運算符),完全沒必要自己寫一個類出來。标準庫裡已經有現成的了,就在functional裡,include進來就行了。functional提供了一堆基于模闆的比較函數對象。它們是(看名字就知道意思了):equal_to<Type>、not_equal_to<Type>、greater<Type>、greater_equal<Type>、less<Type>、less_equal<Type>。對于這個問題來說,greater和less就足夠了,直接拿過來用:
升序:sort(begin,end,less<data-type>());
降序:sort(begin,end,greater<data-type>()).
sort(a,a+20,greater<int>());
4)既然有疊代器,如果是string 就可以使用反向疊代器來完成逆序排列,程式如下:
string str("cvicses");
string s(str.rbegin(),str.rend());
cout << s <<endl;