qsort速排c言語とc++応用
12181 ワード
C言語でのqsort()によるクイックソート
C言語ではソートのアルゴリズムが多く,システムは関数qsort()を提供し,高速ソートを実現できる.プロトタイプは次のとおりです.
それはcompが指す関数が提供する順序に基づいてbaseが指す配列をソートし、nmemはソートに参加する要素の個数であり、sizeは各要素が占めるバイト数である.たとえば、要素を昇順に並べ替える場合、compが指す関数は、最初のパラメータが2番目のパラメータより小さい場合、0未満の値を返し、逆に0より大きい値を返し、等しい場合は0を返します.
例:
実行結果は次のとおりです.
0 1 2 6 8 9
上記のセクションは次のとおりです.http://blog.chinaunix.net/u/22520/showart_232703.htmlqsort機能:高速ソートルーチンを用いたソート用法:void*base,int nelem,int width,int(*fcmp);各パラメータ:1ソート対象配列ヘッダアドレス2配列中のソート対象要素数3各要素の占有空間サイズ4は関数のポインタを指し、ソートの順序を決定するためのプログラム例:#include using namespace std; #include #include int compare( const void *a, const void *b); char * list[5]= {"cat","car","cab","cap","can"}; int main()pascalルーチンprogram quicksort; const max = 100000; max = 1000; type tlist = array[1..max] of longint; var data : tlist; i : longint; procedure qsort(var a : tlist); procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=a[(l+r) div 2]; repeat while a while x if i<=j then begin y:=a;a:=a[j];a[j]:=y; inc(i);dec(x); end; until i>j; if l if i end; begin sort(1,max); end; begin write('Creating ',Max,' random numbers between 1 and 500000'); randomize; for i:=1 to max do data:=random(500000); writeln; writeln('Sorting...'); qsort(data); writeln; for i:=1 to max do begin write(data:7); if (i mod 10)=0 then writeln; end; end. c/c++c関数qsort()とbsearch()の使い方qsort()を使用してソートし、bsearch()で検索するのは比較的一般的な組み合わせであり、使い勝手が速い。qsortの関数の原型はvoid__cdeclqsort(void*base,size_t num,size_t width,int(_cdecl*comp)(const void*,const void*))baseはソートされた集合配列であり、numはこの配列要素の個数であり、widthは要素の大きさであり、compは比較関数である。例えば、長さ1000の配列をソートする場合、int a[1000];ではbaseはa、numは1000、widthはsizeof(int)で、comp関数は自分の名前に従います。 qsort(a,1000,sizeof(int ),comp);ここでcomp関数は、int comp(const void*a,const void*b){return*(int*)a-*(int*)b;}は、2次元配列をソートするint a[1000][2];ここで、a[0]のサイズに従って全体的なソートが行われ、a[1]はa[0]とともに移動して交換しなければならない。 qsort(a,1000,sizeof(int)*2,comp);int comp(const void*a,const void*b){return((int*)a)[0]-((int*)b)[0];}文字列をソートする:char a[1000][20]; qsort(a,1000,sizeof(char)*20,comp);int comp(const void*a,const void*b{return strcmp((char*)a,(char*)b);}一つの構造体を並べ替える:typedef struct str{char str 1[11];char str 2[11];}str,*stri; str strin[100001]=; int compare(const void *a,const void *b) { return strcmp( ((str*)a)->str2 , ((str*)b)->str2 ); } qsort(strin,total,sizeof(str),compare); プログラム例:#include#include#include#define N 8 int compare(const void*a,const void*b); void main() { char s[8][10]={"January","February","March","April","May","June","July","September"}; int i; qsort(s,8,sizeof(char)*10,compare); for(i=0;i cout<}int compare(const void*a,const void*b){if(strlen((char*)a)!=strlen((char*)b))return strlen((char*)a)-strlen((char*)b);return(strcmp((char*)a、(char*)b);}//vc++6.0//VS 2008コンパイルにより、代表的な例#include#include#include#include int compare(const void*arg 1,const void*arg 2); int main(int argc,char **argv) { int i; argv++; argc--; qsort((void *)argv,(size_t)argc,sizeof(char *),compare); for(i=0;i { printf("%s ",argv); printf(""); } } int compare(const void *arg1,const void *arg2) { return _stricmp(*(char **)arg1,*(char **)arg2); }入力cmdを実行する、qsort.exeパラメータ1パラメータ2がソートされます Source: http://baike.baidu.com/view/982231.htm上記のセクションは次のとおりです.http://blog.csdn.net/maray/archive/2009/03/27/4030123.aspxqsort関数応用大全(回転)
7種類のqsortソート方法
一、intタイプ配列の並べ替え
int num[100];
Sample:
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];
Sample:
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;
}
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);
六、文字列を並べ替える
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);
七、計算幾何学の中で凸包を求めるcmp
int cmp(const void*a,const void*b)//重点cmp関数は、1点を除くすべての点を回転角度で並べ替える
{
struct point *c=(point *)a;
struct point *d=(point *)b;
if( calc(*c,*d,p[1]) < 0) return 1;
else if(!calc(*c,*d,p[1])&&dis(c->x,c->y,p[1].x,p[1].y)x,d->y,p[1].x,p[1].y)//一直線上であれば、遠くを前に置く
return 1;
else return -1;
}
PS:
その中のqsort関数は含むヘッダファイルの中でstrcmpは含むヘッダファイルの中で
最後の部分は次のとおりです.http://www.cppblog.com/qywyh/articles/3405.html
C言語ではソートのアルゴリズムが多く,システムは関数qsort()を提供し,高速ソートを実現できる.プロトタイプは次のとおりです.
void qsort(void *base, size_t nmem, size_t size, int (*comp)(const void *, const void *)); それはcompが指す関数が提供する順序に基づいてbaseが指す配列をソートし、nmemはソートに参加する要素の個数であり、sizeは各要素が占めるバイト数である.たとえば、要素を昇順に並べ替える場合、compが指す関数は、最初のパラメータが2番目のパラメータより小さい場合、0未満の値を返し、逆に0より大きい値を返し、等しい場合は0を返します.
例:
#include <stdio.h>
#include <stdlib.h>
int comp(const void *, const void *);
int main(int argc, char *argv[])
{
int i;
int array[] = {6, 8, 2, 9, 1, 0};
qsort(array, 6, sizeof(int), comp);
for (i = 0; i < 6; i ++) {
printf("%d\t", array[i]);
}
printf("
");
return 0;
}
int comp(const void *p, const void *q)
{
return (*(int *)p - *(int *)q);
} 実行結果は次のとおりです.
0 1 2 6 8 9
上記のセクションは次のとおりです.http://blog.chinaunix.net/u/22520/showart_232703.htmlqsort機能:高速ソートルーチンを用いたソート用法:void*base,int nelem,int width,int(*fcmp);各パラメータ:1ソート対象配列ヘッダアドレス2配列中のソート対象要素数3各要素の占有空間サイズ4は関数のポインタを指し、ソートの順序を決定するためのプログラム例:#include using namespace std; #include #include int compare( const void *a, const void *b); char * list[5]= {"cat","car","cab","cap","can"}; int main()pascalルーチンprogram quicksort; const max = 100000; max = 1000; type tlist = array[1..max] of longint; var data : tlist; i : longint; procedure qsort(var a : tlist); procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=a[(l+r) div 2]; repeat while a while x if i<=j then begin y:=a;a:=a[j];a[j]:=y; inc(i);dec(x); end; until i>j; if l if i end; begin sort(1,max); end; begin write('Creating ',Max,' random numbers between 1 and 500000'); randomize; for i:=1 to max do data:=random(500000); writeln; writeln('Sorting...'); qsort(data); writeln; for i:=1 to max do begin write(data:7); if (i mod 10)=0 then writeln; end; end. c/c++c関数qsort()とbsearch()の使い方qsort()を使用してソートし、bsearch()で検索するのは比較的一般的な組み合わせであり、使い勝手が速い。qsortの関数の原型はvoid__cdeclqsort(void*base,size_t num,size_t width,int(_cdecl*comp)(const void*,const void*))baseはソートされた集合配列であり、numはこの配列要素の個数であり、widthは要素の大きさであり、compは比較関数である。例えば、長さ1000の配列をソートする場合、int a[1000];ではbaseはa、numは1000、widthはsizeof(int)で、comp関数は自分の名前に従います。 qsort(a,1000,sizeof(int ),comp);ここでcomp関数は、int comp(const void*a,const void*b){return*(int*)a-*(int*)b;}は、2次元配列をソートするint a[1000][2];ここで、a[0]のサイズに従って全体的なソートが行われ、a[1]はa[0]とともに移動して交換しなければならない。 qsort(a,1000,sizeof(int)*2,comp);int comp(const void*a,const void*b){return((int*)a)[0]-((int*)b)[0];}文字列をソートする:char a[1000][20]; qsort(a,1000,sizeof(char)*20,comp);int comp(const void*a,const void*b{return strcmp((char*)a,(char*)b);}一つの構造体を並べ替える:typedef struct str{char str 1[11];char str 2[11];}str,*stri; str strin[100001]=; int compare(const void *a,const void *b) { return strcmp( ((str*)a)->str2 , ((str*)b)->str2 ); } qsort(strin,total,sizeof(str),compare); プログラム例:#include#include#include#define N 8 int compare(const void*a,const void*b); void main() { char s[8][10]={"January","February","March","April","May","June","July","September"}; int i; qsort(s,8,sizeof(char)*10,compare); for(i=0;i cout<}int compare(const void*a,const void*b){if(strlen((char*)a)!=strlen((char*)b))return strlen((char*)a)-strlen((char*)b);return(strcmp((char*)a、(char*)b);}//vc++6.0//VS 2008コンパイルにより、代表的な例#include#include#include#include int compare(const void*arg 1,const void*arg 2); int main(int argc,char **argv) { int i; argv++; argc--; qsort((void *)argv,(size_t)argc,sizeof(char *),compare); for(i=0;i { printf("%s ",argv); printf(""); } } int compare(const void *arg1,const void *arg2) { return _stricmp(*(char **)arg1,*(char **)arg2); }入力cmdを実行する、qsort.exeパラメータ1パラメータ2がソートされます Source: http://baike.baidu.com/view/982231.htm上記のセクションは次のとおりです.http://blog.csdn.net/maray/archive/2009/03/27/4030123.aspxqsort関数応用大全(回転)
7種類のqsortソート方法
一、intタイプ配列の並べ替え
int num[100];
Sample:
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];
Sample:
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;
}
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);
六、文字列を並べ替える
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);
七、計算幾何学の中で凸包を求めるcmp
int cmp(const void*a,const void*b)//重点cmp関数は、1点を除くすべての点を回転角度で並べ替える
{
struct point *c=(point *)a;
struct point *d=(point *)b;
if( calc(*c,*d,p[1]) < 0) return 1;
else if(!calc(*c,*d,p[1])&&dis(c->x,c->y,p[1].x,p[1].y)
return 1;
else return -1;
}
PS:
その中のqsort関数は含むヘッダファイルの中でstrcmpは含むヘッダファイルの中で
最後の部分は次のとおりです.http://www.cppblog.com/qywyh/articles/3405.html