愛華網(wǎng)** 關(guān)于快排函數(shù)的一些說明 **
qsort,包含在stdlib.h頭文件里,函數(shù)一共四個參數(shù),沒返回值.一個典型的qsort的寫法如下
qsort(s,n,sizeof(s[0]),cmp);
其中第一個參數(shù)是參與排序的數(shù)組名(或者也可以理解成開始排序的地址,因為可以寫&s[i]
這樣的表達式,這個問題下面有說明); 第二個參數(shù)是參與排序的元素個數(shù);第三個三數(shù)是
單個元素的大小,推薦使用sizeof(s[0])這樣的表達式,下面也有說明 :);第四個參數(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è)是對int排序的話,如果是升序,那么就是如果a比b大返回一個正值,小則負值,相等返回
0,其他的依次類推,后面有例子來說明對不同的類型如何進行排序.
在函數(shù)體內(nèi)要對a,b進行強制類型轉(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里面重新定義兩個指針來強制類型轉(zhuǎn)換,
特別是在對結(jié)構(gòu)體進行排序的時候
4.快排qsort的第三個參數(shù),那個sizeof,推薦是使用sizeof(s[0])這樣,特別是對結(jié)構(gòu)體,
往往自己定義2*sizeof(int)這樣的會出問題,用sizeof(s[0)既方便又保險
5.如果要對數(shù)組進行部分排序,比如對一個s[n]的數(shù)組排列其從s[i]開始的m個元素,只需要
在第一個和第二個參數(shù)上進行一些修改:qsort(&s[i],m,sizeof(s[i]),cmp);
** 標(biāo)程,舉例說明 **
No.1.手工實現(xiàn)QuickSort
#include <stdio.h>
int a[100],n,temp;
void QuickSort(int h,int t)
{
if(h>=t) return;
int mid=(h+t)/2,i=h,j=t,x;
x=a[mid];
while(1)
{
while(a[i]<x) i++;
while(a[j]>x) j--;
if(i>=j) break;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
a[mid]=a[j];
a[j]=x;
QuickSort(h,j-1);
QuickSort(j+1,t);
return;
}
int main()
{
int i;
scanf("%d",&n);
for(i=0;i<n;i++) scanf("%d",&a[i]);
QuickSort(0,n-1);
for(i=0;i<n;i++) printf("%d ",a[i]);
return(0);
}
No.2.最常見的,對int數(shù)組排序
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int s[10000],n,i;
int cmp(const void *a, const void *b)
{
return(*(int *)a-*(int *)b);
}
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]);
return(0);
}
No.3.對double型數(shù)組排序,原理同int
這里做個注釋,本來是因為要判斷如果a==b返回0的,但是嚴格來說,兩個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("%lf ",s[i]);
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)
{0
return(*(char *)a-*(char *)b);
}
int main()
{
scanf("%s",s);
n=strlen(s);
qsort(s,n,sizeof(s[0]),cmp);
printf("%s",s);
return(0);
}
No.5.對結(jié)構(gòu)體排序
注釋一下.很多時候我們都會對結(jié)構(gòu)體排序,比如校賽預(yù)選賽的那個櫻花,一般這個時候都在
cmp函數(shù)里面先強制轉(zhuǎn)換了類型,不要在return里面轉(zhuǎn),我也說不清為什么,但是這樣程序會
更清晰,并且絕對是沒錯的. 這里同樣請注意double返回0的問題
#include <stdio.h>
#include <stdlib.h>
struct node
{
double date1;
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->date1)>(bb->date1))?1:-1);
}
int main()
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
s[i].no=i+1;
scanf("%lf",&s[i].date1);
}
qsort(s,n,sizeof(s[0]),cmp);
for(i=0;i<n;i++) printf("%d%lfn",s[i].no,s[i].date1);
return(0);
}
No.6.對結(jié)構(gòu)體排序.加入no來使其穩(wěn)定(即data值相等的情況下按原來的順序排)
#include <stdio.h>
#include <stdlib.h>
struct node
{
double date1;
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->date1!=bb->date1)
return(((aa->date1)>(bb->date1))?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].date1);
}
qsort(s,n,sizeof(s[0]),cmp);
for(i=0;i<n;i++) printf("%d%lfn",s[i].no,s[i].date1);
return(0);
}
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("%sn",s[i]);
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("%sn",s[i]);
return(0);
}
