C語言標(biāo)準(zhǔn)庫函數(shù)qsort那點小事

2019-11-08 19:56:18

字體：大中小

供稿：網(wǎng)友

qsort包含在stdlib.h頭文件中，此函數(shù)根據(jù)你給的比較條件進(jìn)行快速排序，通過指針移動實現(xiàn)排序。排序之后的結(jié)果仍然放在原數(shù)組中。使用qsort函數(shù)必須自己寫一個比較函數(shù)。

函數(shù)原型：

void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

函數(shù)一共四個參數(shù)，沒返回值。一個典型的qsort的寫法如下:

void qsort(s,n,sizeof(s[0]),cmp);

其中第一個參數(shù)是參與排序的數(shù)組名（或者也可以理解成開始排序的地址，因為可以寫&s[i]，這個問題下面有說明）；第二個參數(shù)是參與排序的元素個數(shù)；第三個參數(shù)是單個元素的大?。ㄍ扑]使用sizeof(s[0])這樣的表達(dá)式，下面也有說明）；第四個參數(shù)就是很多人覺得非常困惑的比較函數(shù)，關(guān)于這個函數(shù),還要說的比較麻煩…

下面來討論cmp這個比較函數(shù)（寫成cmp是我的個人喜好,你可以隨便寫成什么，比如qcmp什么的）。典型的cmp的定義是:

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

返回值必須是int，兩個參數(shù)的類型必須都是const void *，那個a,b是我隨便寫的兩個參數(shù)。假設(shè)是對int排序的話，如果是升序，那么就是如果a比b大返回一個正值，小則負(fù)值，相等返回0，后面有例子來說明對不同的類型如何進(jìn)行排序。

在函數(shù)體內(nèi)要對a，b進(jìn)行強(qiáng)制類型轉(zhuǎn)換后才能得到正確的返回值，不同的類型有不同的處理方法。具體情況請參考后面的例子。

**** 關(guān)于快排的一些小問題 ****

1、快排是不穩(wěn)定的，這個不穩(wěn)定一個表現(xiàn)在其使用的時間是不確定的，最好情況(O(n))和最壞情況(O(n^2))差距太大，我們一般說的O(nlog(n))都是指的是其平均時間。

2、快排是不穩(wěn)定的，這個不穩(wěn)定表現(xiàn)在如果相同的比較元素，可能順序不一樣，假設(shè)我們有這樣一個序列,3,3,3,但是這三個3是有區(qū)別的，我們標(biāo)記為3a,3b,3c,快排后的結(jié)果不一定就是3a,3b,3c這樣的排列，所以在某些特定場合我們要用結(jié)構(gòu)體來使其穩(wěn)定（No.6的例子就是說明這個問題的）。

3、快排的比較函數(shù)的兩個參數(shù)必須都是const void *的,這個要特別注意，寫a和b只是我的個人喜好，寫成cmp也只是我的個人喜好。推薦在cmp里面重新定義兩個指針來強(qiáng)制類型轉(zhuǎn)換，特別是在對結(jié)構(gòu)體進(jìn)行排序的時候。

4、快排qsort的第三個參數(shù)，那個sizeof，推薦是使用sizeof(s[0])這樣，特別是對結(jié)構(gòu)體，往往自己定義2*sizeof(int)這樣的會出問題，用sizeof(s[0)既方便又保險。

5、如果要對數(shù)組進(jìn)行部分排序，比如對一個s[n]的數(shù)組排列其從s[i]開始的m個元素，只需要在第一個和第二個參數(shù)上進(jìn)行一些修改:

void qsort(&s[i],m,sizeof(s[i]),cmp);

*** 標(biāo)程，舉例說明 ***

No.1、手工實現(xiàn)QuickSort:

基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。

#include<stdio.h>#include<stdlib.h>void QuickSort(int *A,int left,int right){ if(left>=right) return; int x=A[(left+right)>>1],low=left,high=right; while(low<high) { while(A[low]<x) low++; while(A[high]>x) high--; if(low<=high) { int Temp=A[low]; A[low]=A[high]; A[high]=Temp; low++; high--; } } QuickSort(A,left,high); QuickSort(A,low,right);}int main(){ int length,i,r[10000]; scanf("%d",&length); for(i=1;i<=length;i++) scanf("%d",&r[i]); QuickSort(r,1,length); for(i=1;i<=length;i++) 或者：

#include<stdio.h>#include<stdlib.h>int QKPass(int r[],int left,int right){ int low,high,x; x=r[left];//選擇基準(zhǔn)記錄 low=left; high=right; while(low<high) { while(low<high&&r[high]>=x)//從右到左找到小于x的記錄 high--; if(low<high) { r[low]=r[high];//找到后進(jìn)行替換 low++; } while(low<high&&r[low]<x) { low++; } if(low<high) { r[high]=r[low]; high--; } r[low]=x;//將基準(zhǔn)記錄保存在low=high的位置 return low;//返回基準(zhǔn)記錄的位置 }}int QKSort(int r[],int low,int high){ int pos; if(low<high) { pos=QKPass(r,low,high); QKSort(r,low,pos-1); QKSort(r,pos+1,high); }}int main(){ int length,i,r[10000]; scanf("%d",&length); for(i=1;i<=length;i++) scanf("%d",&r[i]); QKSort(r,1,length); for(i=1;i<=length;i++) printf("%-3d",r[i]); printf("/n"); system("pause"); return 0;}

No.2、最常見的，對int數(shù)組排序 :

#include<stdio.h> #include<stdlib.h>int s[10000],n,i;int cmp(const void *a, const void *b) { return(*(int *)a-*(int *)b); //升序 //return(*(int *)b-*(int *)a); //降序 }int main() { scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&s[i]); qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%d ",s[i]); printf("/n"); system("pause"); return 0; }

No.3、對double型數(shù)組排序，原理同int：

這里做個注釋，本來是因為要判斷如果a==b返回0的，但是嚴(yán)格來說，兩個double數(shù)是不可能相等的，只能說fabs(a-b)<1e-20之類的這樣來判斷，所以這里只返回了1和-1

#include<stdio.h> #include<stdlib.h>double s[1000]; int i,n;int cmp(const void * a, const void * b) { return((*(double*)a-*(double*)b>0)?1:-1); }int main() { scanf("%d",&n); for(i=0;i<n;i++) scanf("%lf",&s[i]); qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%.2lf ",s[i]); printf("/n"); system("pause"); return(0); }

No.4、對一個字符數(shù)組排序.原理同int:

#include<stdio.h> #include<string.h> #include<stdlib.h>char s[10000],i,n;int cmp(const void *a,const void *b) { return(*(char *)a-*(char *)b); }int main() { scanf("%s",s); n=strlen(s); qsort(s,n,sizeof(s[0]),cmp); printf("%s",s); printf("/n"); system("pause"); return 0; }

No.5、對結(jié)構(gòu)體排序（一級排序）:

很多時候我們都會對結(jié)構(gòu)體排序，比如2010年校賽的那個根據(jù)幾個參數(shù)排序，一般這個時候都在cmp函數(shù)里面先強(qiáng)制轉(zhuǎn)換了類型，不要在return里面轉(zhuǎn)換，我也說不清為什么，但是這樣程序會更清晰，并且絕對是沒錯的。這里同樣請注意double返回0的問題:

#include<stdio.h> #include<stdlib.h>struct node { double data; int no; } s[100];int i,n;int cmp(const void *a,const void *b) { struct node *aa=(node *)a; struct node *bb=(node *)b; return(((aa->data)>(bb->data))?1:-1); }int main() { scanf("%d",&n); for(i=0;i<n;i++) { s[i].no=i+1; scanf("%lf",&s[i].data); } qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%d %lf/n",s[i].no,s[i].data); system("pause"); return 0; }

No.6、對結(jié)構(gòu)體排序（二級排序）。加入no來使其穩(wěn)定（即data值相等的情況下按原來的順序排）:

#include<stdio.h> #include<stdlib.h>struct node { double data; int no; } s[100];int i,n;int cmp(const void *a,const void *b) { struct node *aa=(node *)a; struct node *bb=(node *)b; if(aa->data!=bb->data) return(((aa->data)>(bb->data))?1:-1); else return((aa->no)-(bb->no)); }int main() { scanf("%d",&n); for(i=0;i<n;i++) { s[i].no=i+1; scanf("%lf",&s[i].data); } qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%d %lf/n",s[i].no,s[i].data); printf("/n"); system("pause"); return 0; }

如果有字符串的話，就這樣寫：

int cmp(const void *a,const void *b) { struct node *aa=(node *)a; struct node *bb=(node *)b; if(aa->data!=bb->data) return(((aa->data)>(bb->data))?1:-1); else return((aa->no)-(bb->no)); else return strcmp(aa.str,bb.str); //return strcmp(aa->str,bb->str); //按照結(jié)構(gòu)體中字符串str的字典順序排序}

No.7、對字符串?dāng)?shù)組的排序（char s[][]型）:

#include<stdio.h> #include<string.h> #include<stdlib.h>char s[100][100]; int i,n;int cmp(const void *a,const void *b) { return(strcmp((char*)a,(char*)b)); }int main() { scanf("%d",&n); for(i=0;i<n;i++) scanf("%s",s[i]); qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%s/n",s[i]); printf("/n"); system("pause"); return 0; }

No.8、對字符串?dāng)?shù)組排序（char *s[]型）:

#include<stdio.h> #include<string.h> #include<stdlib.h>char *s[100]; int i,n;int cmp(const void *a,const void *b){ return(strcmp(*(char**)a,*(char**)b)); }int main() { scanf("%d",&n); for(i=0;i<n;i++) { s[i]=(char*)malloc(sizeof(char*)); scanf("%s",s[i]); } qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%s/n",s[i]); printf("/n"); system("pause"); return 0; }

原文轉(zhuǎn)自：http://www.cnblogs.com/sooner/archive/2012/04/18/2455011.html