First  qsort

基本快速排序的方法，每次把數(shù)組分成兩分和中間的一個(gè)劃分值，而對(duì)于有多個(gè)重復(fù)值的數(shù)組來(lái)說(shuō)，基本排序的效率較低。集成在C語(yǔ)言庫(kù)函數(shù)里面的的qsort函數(shù)，使用 三 路劃分的方法解決這個(gè)問(wèn)題。所謂三路劃分，是指把數(shù)組劃分成小于劃分值，等于劃分值和大于劃分值的三個(gè)部分。

函數(shù)對(duì)buf 指向的數(shù)據(jù)按升序排序。

使用方法：

void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )

int compare (const void *elem1, const void *elem2 ) );

qsort（quicksort）主要根據(jù)你給的比較條件給一個(gè)快速排序，主要是通過(guò)指針移動(dòng)實(shí)現(xiàn)排序功能。排序之后的結(jié)果仍然放在原來(lái)數(shù)組中。

參數(shù)意義如下:

base:需要排序的目標(biāo)數(shù)組開(kāi)始地址

num:目標(biāo)數(shù)組元素個(gè)數(shù)

width:目標(biāo)數(shù)組中每一個(gè)元素長(zhǎng)度

compare:函數(shù)指針，指向比較函數(shù)

一、對(duì)int類(lèi)型數(shù)組排序

int num[100];

int cmp ( const void *a , const void *b )

{

return *(int *)a - *(int *)b;

可見(jiàn)：參數(shù)列表是兩個(gè)空指針，現(xiàn)在他要去指向你的數(shù)組元素。所以轉(zhuǎn)型為你當(dāng)前的類(lèi)型，然后取值。升序排列。

因?yàn)槭前凑誥cs碼的值進(jìn)行的，所以在前面的字符的值一定小于后面的字符。

那么，對(duì)于a b，如果a的值>b的值，就說(shuō)明在字母表中a在b的后面，返回值為1表示ture，執(zhí)行交換。

}

qsort(num,100,sizeof(num[0]),cmp);

二、對(duì)char類(lèi)型數(shù)組排序（同int類(lèi)型）

char Word[100];

int cmp( const void *a , const void *b )

{

return *(char *)a - *(int *)b;

}

qsort(word,100,sizeof(word[0]),cmp);

三、對(duì)double類(lèi)型數(shù)組排序（特別要注意）

double in[100];

int cmp( const void *a , const void *b )

{

return *(double *)a > *(double *)b ? 1 : -1;

返回值的問(wèn)題，顯然cmp返回的是一個(gè)整型，所以避免double返回小數(shù)而被丟失。 

來(lái)一個(gè)判斷。 

}

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的類(lèi)型可以很多種，參考上面的例子寫(xiě)

int cmp( const void *a ,const void *b)

{

return (*(In *)a).data > (*(In *)b).data ? 1 : -1;

}

qsort(s,100,sizeof(s[0]),cmp);

五、對(duì)結(jié)構(gòu)體二級(jí)排序

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)行排序

char str[100][100];

int cmp(const void* a,const void* b )

{

           return strcmp((char *)a,(char*)b);

}

qsort(str,n,sizeof(str[0]),cmp);

值得注意的是，上面的n，很有可能你會(huì)誤認(rèn)為是100，這里實(shí)際應(yīng)該是你要排序的個(gè)數(shù)，比如說(shuō)你實(shí)際上只有str[0],str[1],str[2]這三個(gè)字符串要排序，那么n就應(yīng)該是3，而不是100；

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

注意！qsort 中的  cmp 得自己寫(xiě) 。

Second sort

sort 使用時(shí)得注明：using namespace std;   或直接打 std::sort()  還得加上  #include <algorithm>

例：

#include<iostream>

#include<algorithm>

using namespace std;

int main(){

      int a[20];

      for(int i=0;i<20;++i)

           cin>>a[i];

sort(a,a+20);          //范圍，很明顯這里是a+20 注意，這是必要的，如果是a+19

for(i=0;i<20;i++)        //最后一個(gè)值a[19]就不會(huì)參與排序。

           cout<<a[i]<<endl;

      return 0;

}

std::sort是一個(gè)改進(jìn)版的qsort. std::sort函數(shù)優(yōu)于qsort的一些特點(diǎn)：對(duì)大數(shù)組采取9項(xiàng)取樣，更完全的三路劃分算法，更細(xì)致的對(duì)不同數(shù)組大小采用不同方法排序。

Third  區(qū)別：

sort是qsort的升級(jí)版，如果能用sort盡量用sort，使用也比較簡(jiǎn)單，不像qsort還得自己去寫(xiě) cmp 函數(shù)，只要注明  使用的庫(kù)函數(shù)就可以使用，參數(shù)只有兩個(gè)（如果是普通用法）頭指針和尾指針；

默認(rèn)sort排序后是升序，如果想讓他降序排列，可以使用自己編的cmp函數(shù)

bool compare(int a,int b)

{

  return a>b; //降序排列，如果改為return a<b，則為升序

}

sort(*a,*b,cmp);