快速排序的庫函數qsort與sort的使用方法

qsort

功 能: 使用快速排序例程進行排序 　　 

用 法: void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *)); 　　 

參數：1、待排序數組首位址； 2、數組中待排序元素數量； 3、各元素的占用空間大小； 4、指向函數的指針，用于确定排序的順序 

比如：對一個長為1000的數組進行排序時，int a[1000]; 那麼base應為a，num應為 1000，width應為 sizeof(int)，cmp函數随自己的命名。 

使用方法： 

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

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

qsort（quicksort）主要根據你給的比較條件給一個快速排序，主要是通過指針移動實作排序功能。排序之後的結果仍然放在原來數組中。 

參數意義如下: 

base:需要排序的目标數組開始位址 

num:目标數組元素個數 

width:目标數組中每一個元素長度 

compare:函數指針，指向比較函數 

一、對int類型數組排序 

int num[100]; 

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

{ 

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

}

可見：參數清單是兩個空指針，現在他要去指向你的數組元素。是以轉型為你目前的類型，然後取值。升序排列。 

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

二、對char類型數組排序（同int類型） 

char word[100]; 

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

{ 

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

} 

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

三、對double類型數組排序（特别要注意） 

double in[100]; 

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

{ 

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

}

傳回值的問題，顯然cmp傳回的是一個整型，是以避免double傳回小數而被丢失。   

qsort(in,100,sizeof(in[0]),cmp)； 

四、對結構體一級排序 

struct In 

{ 

double data; 

int other; 

}s[100] 

//按照data的值從小到大将結構體排序,關于結構體内的排序關鍵資料data的類型可以很多種，參考上面的例子寫 

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

{ 

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

} 

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

五、對結構體二級排序 

struct In 

{ 

int x; 

int y; 

}s[100]; 

//按照x從小到大排序，當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); 

六、對字元串進行排序 

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

struct In 

{ 

int data;

char str[100]; 

}s[100]; 

//按照結構體中字元串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 得自己寫 。 

sort：

 sort函數，可以直接對數組排序，複雜度為n*log2(n)。sort()定義在在頭檔案<algorithm>中。sort函數是标準模闆庫的函數，已知開始和結束的位址即可進行排序，可以用于比較任何容器（必須滿足随機疊代器），任何元素，任何條件，執行速度一般比qsort要快。另外，sort()是類屬函數，可以用于比較任何容器，任何元素，任何條件。 

注意：預設是升序排序。 

sort 使用時得注明：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++) //最後一個值a[19]就不會參與排序。 

cout<<a[i]<<endl; 

return 0; 

} 

std::sort是一個改進版的qsort. std::sort函數優于qsort的一些特點：對大數組采取9項取樣，更完全的三路劃分算法，更細緻的對不同數組大小采用不同方法排序。 

Third 差別： 

sort是qsort的更新版，如果能用sort盡量用sort，使用也比較簡單，不像qsort還得自己去寫 cmp 函數，隻要注明 使用的庫函數就可以使用，參數隻有兩個（如果是普通用法）頭指針和尾指針； 

預設sort排序後是升序，如果想讓他降序排列，可以使用自己編的cmp函數 

bool compare(int a,int b) 

{ 

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

} 

sort(*a,*b,cmp); 

例子：

#include<iostream>

#include<algorithm>

using namespace std;

bool cmp (const int a, const int b)

{

    return a > b;

}

int main()

{

    int data[5];

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

        cin >> data[i];

    sort(data, data + 5, cmp);

    return 0;

}

sort函數可以傳兩個參數或三個參數。第一個參數是要排序的區間首位址，第二個參數是區間尾位址的下一位址。也就是說，排序的區間是[a,b)。簡單來說，有一個數組int a[100]，要對從a[0]到a[99]的元素進行排序，隻要寫sort(a,a+100)就行了，預設的排序方式是升序。 排序的資料類型不局限于整數，隻要是定義了小于運算的類型都可以，比如字元串類string。如果是沒有定義小于運算的資料類型，或者想改變排序的順序，就要用到第三參數——比較函數。比較函數是一個自己定義的函數，傳回值是bool型，它規定了什麼樣的關系才是“小于”。想把剛才的整數數組按降序排列，可以先定義一個比較函數cmp: 

bool cmp(int a,int b)

{

    return a>b;

} 

排序的時候就寫sort(a,a+100,cmp); 

假設自己定義了一個結構體node: 

struct node{

    int a;

    int b;

    double c;

}; 

有一個node類型的數組node arr[100]，想對它進行排序：先按a值升序排列，如果a值相同，再按b值降序排列，如果b還相同，就按c降序排列。就可以寫這樣一個比較函數： 

以下是代碼片段： 

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