C/C++プログラマー:ソートアルゴリズムの標準C言語qsort関数の簡単な使い方紹介
2870 ワード
標準ライブラリ関数qsort
void qsort (
void*base,//任意のタイプの配列のヘッダアドレス
size_t nmemb,//配列要素個数
size_t size,//配列要素バイト数
int(*compar)(const void*,const void*)//比較関数ポインタ
);
comparパラメータは次のような形を指します.
int xxx (const void* a, const void* b);
で行ないます.この関数は、以下の判断を完了するように独自に定義されます.
if(aの目標>bの目標)
return正数;
if(aの目標return負数;
if(aの目標==bの目標)
return 0;
void qsort (
void*base,//任意のタイプの配列のヘッダアドレス
size_t nmemb,//配列要素個数
size_t size,//配列要素バイト数
int(*compar)(const void*,const void*)//比較関数ポインタ
);
comparパラメータは次のような形を指します.
int xxx (const void* a, const void* b);
で行ないます.この関数は、以下の判断を完了するように独自に定義されます.
if(aの目標>bの目標)
return正数;
if(aの目標
if(aの目標==bの目標)
return 0;
#include
#include
#include
void _myqsort (void* base, size_t left,
size_t right, size_t size,
int (*compar) (const void*, const void*)) {
size_t p = (left + right) / 2;
void* pivot = malloc (size);
memcpy (pivot, base + p * size, size);
size_t i = left, j = right;
while (i < j) {
for (; ! (i >= p || compar (pivot,
base + i * size) < 0); ++i);
if (i < p) {
memcpy (base + p * size,
base + i * size, size);
p = i;
}
for (; ! (j <= p || compar (base + j * size,
pivot) < 0); --j);
if (j > p) {
memcpy (base + p * size,
base + j * size, size);
p = j;
}
}
memcpy (base + p * size, pivot, size);
free (pivot);
if (p - left > 1)
_myqsort (base, left, p - 1, size, compar);
if (right - p > 1)
_myqsort (base, p + 1, right, size, compar);
}
void myqsort (void* base, size_t nmemb,
size_t size,
int (*compar) (const void*, const void*)) {
_myqsort (base, 0, nmemb - 1, size, compar);
}
int int_cmp (const void* a, const void* b) {
return *(const int*)b - *(const int*)a;
}
int str_cmp (const void* a, const void* b) {
return strcmp (*(const char* const*)a,
*(const char* const*)b);
}
typedef struct Student {
char name[256];
int age;
} STUDENT;
int stu_cmp (const void* a, const void* b) {
const STUDENT* pa = (const STUDENT*)a;
const STUDENT* pb = (const STUDENT*)b;
int res = strcmp (pa->name, pb->name);
if (! res)
return pa->age - pb->age;
return -res;
}
int main (void) {
int na[] = {23, 45, 12, 27, 36, 88, 19, 55};
size_t size = sizeof (na[0]);
size_t nmemb = sizeof (na) / size;
myqsort (na, nmemb, size, int_cmp);
size_t i;
for (i = 0; i < nmemb; ++i)
printf ("%d ", na[i]);
printf ("
");
const char* sa[] = {"beijing", "tianjin",
"shanghai", "chongqing"};
size = sizeof (sa[0]);
nmemb = sizeof (sa) / size;
myqsort (sa, nmemb, size, str_cmp);
for (i = 0; i < nmemb; ++i)
printf ("%s ", sa[i]);
printf ("
");
STUDENT ta[] = {
{"zgfei", 25},
{"zun", 22},
{"zhafei", 20},
{"zhan", 23},
{"guyu", 50}};
size = sizeof (ta[0]);
nmemb = sizeof (ta) / size;
myqsort (ta, nmemb, size, stu_cmp);
for (i = 0; i < nmemb; ++i)
printf ("%s/%d ", ta[i].name, ta[i].age);
printf ("
");
return 0;
}