c语言的qsort函数理解与使用

发布于:2024-11-29 ⋅ 阅读:(29) ⋅ 点赞:(0)

介绍:qsort 函数是 C 标准库中用于排序的快速排序算法函数。它的用法非常灵活,可以对任意类型的元素进行排序,只要提供了比较函数即可。

qsort 函数原型及参数解释:

void qsort (

     void* base,         //指向要排序的数组的首元素的指针

     size_t num,         //待排序数组中元素的个数

     size_t size,        //待排序数组中每个元素的大小(以字节为单位)

     int (*compare)(const void*,const void*)  //比较函数的指针,用于确定元素之间的排序

);

注意: 

使用qsort函数时,需要根据实际情况编写一个合适的比较函数来确定排序规则。

比较函数可以根据元素的类型和排序需求进行自定义。

比较函数的原型如下:

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

比较函数需要返回一个整数值,表示两个元素之间的关系:

如果返回值小于0,则表示a应该排在b之前。

如果返回值等于0,则表示a和b相等,它们的相对顺序不变。

如果返回值大于0,则表示a应该排在b之后。

对于一个数组或是任意需要进行排序的内容进行排序时可以理解如下:

// qsort中自定义比较函数compare返回值 > 0表示对需要排序的内容进行升序排序(小->大)

// qsort中自定义比较函数compare返回值 < 0表示对需要排序的内容进行降序排序(大->小)

实例:

// qsort排序举例:升序排序(小->大)
// 自定义比较函数返回值 > 0表示对需要排序的内容进行升序排序

// qsort 函数是 C 标准库中用于排序的快速排序算法函数。
// 它的用法非常灵活,可以对任意类型的元素进行排序,只要提供了比较函数即可。

#include <stdio.h>
#include <stdlib.h>

// 比较函数的形式为:
// int cmp(const void *a, const void *b);
// 其中,cmp 函数用于比较 a 和 b 两个指针所指向的元素的大小关系,
// 如果 a 指向的元素小于 b 指向的元素,则返回负数;
// 如果 a 指向的元素大于 b 指向的元素,则返回正数;
// 如果 a 指向的元素等于 b 指向的元素,则返回 0。
// 下面我们来看一个最简单的实例代码,用于对整数数组进行排序:
int compare(const void *a, const void *b)
{
    printf("%d - %d = %d,  ", *(int *)a, *(int *)b, (*(int *)a - *(int *)b));
    return (*(int*)a - *(int*)b);
}

int main()
{
    int arr0[] = {2, 1};
    int len = sizeof(arr0) / sizeof(int);

    // 这段代码的核心部分就是使用 qsort 函数对整数数组进行排序,排序时需要传递一个比较函数 cmp。
    // cmp 函数的实现非常简单,就是计算 a 和 b 之间的差值。最后,我们依次输出排序后的整数数组。
    // 需要注意的是,在使用 qsort 函数时,我们需要传递以下参数:
    // 1. 待排序的数组的首地址。
    // 2. 数组中元素的个数。
    // 3. 每个元素的大小(以字节为单位)。
    // 4. 比较函数的地址(即函数指针)。
    // 这里我们传递的数组是 int 类型的数组,每个元素占据 4 个字节;
    // 比较函数 cmp 的地址可以直接传递函数名,也可以使用 & 运算符取地址。
    // 这就是 qsort 函数的基本用法。
    // 需要注意的是,cmp 函数要保证正确性和稳定性才能得到正确的排序结果,同时在实际使用时,也需要根据具体情况进行参数传递和处理。
    printf("arr0 升序排序过程:\n");
    // compare 返回值 > 0表示对数组arr1进行降序排序
    qsort(arr0, len, sizeof(int), compare);

    printf("\narr0 after sort:\n");
    for (int i = 0; i < len; i++) {
        printf("%d ", arr0[i]);
    }
    printf("\n");

    int arr1[] = {3, 2, 1, 5, -2, 9};
    int len1 = sizeof(arr1) / sizeof(int);
    printf("\narr1 升序排序过程:\n");
    // compare 返回值 > 0表示对数组arr1进行降序排序
    qsort(arr1, len1, sizeof(int), compare);

    printf("\narr1 after sort:\n");
    for (int i = 0; i < len1; i++) {
        printf("%d ", arr1[i]);
    }
    printf("\n");

    return 0;
}

// qsort排序举例:降序排序(大->小)
#include <stdio.h>
#include <stdlib.h>

int cmp0(const void *a, const void *b)
{
    printf("%d - %d = %d,  ", *(int *)a, *(int *)b, (*(int *)a - *(int *)b));
    return -(*(int*)a - *(int*)b);
}

int cmp1(const void *a, const void *b)
{
    printf("%d - %d = %d,  ", *(int *)b, *(int *)a, (*(int *)b - *(int*)a));
    return (*(int *)b - *(int*)a);
}

int main()
{
    int arr[] = {5, 4, 2, 5, 3, 1};
    int len = sizeof(arr) / sizeof(int);

    printf("升序排序过程:\n");
    // cmp1返回值 < 0表示对数组arr1进行降序排序
    qsort(arr, len, sizeof(int), cmp0);

    printf("\nafter sort:\n");
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // cmp1返回值 < 0表示对数组arr1进行降序排序
    int arr1[] = {3, 2, 1, 5, -2, 9};
    printf("降序排序过程:\n");
    qsort(arr1, len, sizeof(int), cmp1);

    printf("\nafter sort:\n");
    for (int i = 0; i < len; i++) {
        printf("%d ", arr1[i]);
    }
    printf("\n");

    return 0;
}


// 对浮点数进行排序
#include <stdio.h>
#include <stdlib.h>

// 对浮点数进行升序排序
int cmpFloat2Ascending(const void *a, const void *b)
{
    return *(float *)a - *(float *)b;
}

// 对浮点数进行降序排序
int cmpFloat2Descending(const void *a, const void *b)
{
    return -(*(float *)a - *(float *)b);
}

int main()
{
    float arr0[] = { -0.52, 1.7, 20.5, 9.9, 10.22 };
    int num0 = sizeof(arr0) / sizeof(int);

    printf("升序排序过程:\n");
    // cmp1返回值 < 0表示对数组arr1进行降序排序
    qsort(arr0, num0, sizeof(float), cmpFloat2Ascending);

    printf("\nafter sort:\n");
    for (int i = 0; i < num0; i++) {
        printf("%.2f ", arr0[i]);
    }
    printf("\n");

    // cmp1返回值 < 0表示对数组arr1进行降序排序
    float arr1[] = {3.3, 5.2, 1.1, 0.5, -1.2, 9.9};
    int num1 = sizeof(arr0) / sizeof(float);
    printf("降序排序过程:\n");
    qsort(arr1, num1, sizeof(float), cmpFloat2Descending);

    printf("\nafter sort:\n");
    for (int i = 0; i < num1; i++) {
        printf("%.2f ", arr1[i]);
    }
    printf("\n");

    return 0;
}

// qsort 函数对结构体类型的数据进行升序和降序排序:
// 这个程序定义了一个 Student 结构体类型,包含了学生的姓名、年龄和考试成绩三个成员变量。
// 在比较函数中,我们先比较考试成绩的大小,如果不同则返回差值;
// 如果考试成绩相同,则比较年龄的大小,如果不同则返回差值;
// 如果年龄也相同,则比较姓名的大小,从而实现了升序和降序排序。
// 在 main 函数中,我们首先定义了一个 Student 类型的数组,用于测试排序结果。
// 然后先调用 qsort 函数实现升序排序,并输出排序后的结果;
// 接着再调用 qsort 函数实现降序排序,并输出排序后的结果。
// 需要注意的是,在实际使用 qsort 函数时,需要根据具体情况进行参数传递和处理,
// 特别是在程序中使用了自定义结构体类型时,需要编写相应的比较函数来实现排序。
// 同时,也需要特别注意比较函数的实现方式,确保能够正确地比较结构体类型的各个成员变量。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char name[20];
    int age;
    int score;
} Student;

// 升序
int cmpAsc(const void *a, const void *b)
{
    Student *sa = (Student *)a;
    Student *sb = (Student *)b;
    if (sa->score != sb->score) {
        return sa->score - sb->score;
    } else if (sa->age != sb->age) {
        return sa->age - sb->age;
    } else {
        return strcmp(sa->name, sb->name);
    }
}

// 降序
int cmpDesc(const void *a, const void *b)
{
    Student *sa = (Student *)a;
    Student *sb = (Student *)b;
    if (sa->score != sb->score) {
        return -(sa->score - sb->score);
    } else if (sa->age != sb->age) {
        return -(sa->age - sb->age);
    } else {
        return -strcmp(sa->name, sb->name);
    }
}

int main()
{
    Student students[] = {
        {"Alice", 18, 80},
        {"Bob", 20, 70},
        {"Charlie", 19, 90},
        {"David", 18, 80},
        {"Ella", 20, 85}
    };


    int n = sizeof(students) / sizeof(students[0]);

    // 升序
    qsort(students, n, sizeof(Student), cmpAsc);
    printf("Asc:\n");
    for (int i = 0; i < n; i++) {
        printf("Name: %s\t Age: %d\t Score: %d\n", students[i].name, students[i].age, students[i].score);
    }
    printf("\n");

    // 降序排序
    qsort(students, n, sizeof(Student), cmpDesc);

    printf("Desc:\n");
    for (int i = 0; i < n; i++) {
        printf("Name: %s\t Age: %d\t Score: %d\n", students[i].name, students[i].age, students[i].score);
    }

    return 0;
}

// 实现一个自定义的模拟qsort函数
// 在这个程序中,我们首先定义了一个 Person 结构体类型,包含名称和年龄两个成员变量。
// 在比较函数中,我们首先比较名称的大小,如果不同则返回名称的差值;
// 如果名称相同,则比较年龄的大小,从而实现了升序和降序排序。
// 在 bubble_sort 函数中,我们使用冒泡排序的逻辑来实现元素的排序,传入的对象是 void 指针,
// 因此我们需要将其强制转换为 char 指针,然后利用 memcpy 函数以元素的大小 width 为单位进行移动。
// 每次比较都使用传入的函数指针 cmp 来比较元素的大小,如果需要交换则使用 memcpy 函数来实现交换。
// 在 main 函数中,我们首先定义了一个 Person 类型的数组,包含了五个元素。
// 我们先对数组进行升序排序打印输出,然后再进行降序排序打印输出。
// 需要注意的是,在输出时使用了结构体的成员变量 name 和 age,分别代表了名称和年龄
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char name[20];
    int age;
} Person;

int cmp_asc(const void *a, const void *b)
{
    Person *pa = (Person *)a;
    Person *pb = (Person *)b;
    if (strcmp(pa->name, pb->name) != 0) {
        return strcmp(pa->name, pb->name);
    } else {
        return pa->age - pb->age;
    }
}

int cmp_desc(const void *a, const void *b)
{
    Person *pa = (Person *)a;
    Person *pb = (Person *)b;
    if (strcmp(pa->name, pb->name) != 0) {
        return strcmp(pb->name, pa->name);
    } else {
        return pb->age - pa->age;
    }
}

void bubble_sort0(void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *))
{
    char *array = (char *)base;
    for (int i = 0; i < nel - 1; i++) {
        for (int j = i + 1; j < nel; j++) {
            // > 0 表示升序
            if (cmp(array + i * width, array + j * width) > 0) {
                char tmp[width];
                memcpy(tmp, array + j * width, width);
                memcpy(array + j * width, array + i * width, width);
                memcpy(array + i * width, tmp, width);
            }
        }
    }
}

void bubble_sort1(void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *))
{
    char *array = (char *)base;
    for (int i = 0; i < nel - 1; i++) {
        for (int j = 0; j < nel - i - 1; j++) {
            // > 0 表示升序
            if (cmp(array + j * width, array + (j + 1) * width) > 0) {
                char tmp[width];
                memcpy(tmp, array + j * width, width);
                memcpy(array + j * width, array + (j + 1) * width, width);
                memcpy(array + (j + 1) * width, tmp, width);
            }
        }
    }
}


int main()
{
    Person people[] = {
        {"Alice", 18},
        {"Bob", 20},
        {"Charlie", 19},
        {"David", 18},
        {"Ella", 20}
    };
    int n = sizeof(people) / sizeof(Person);

    // 升序排序
    bubble_sort0(people, n, sizeof(Person), cmp_asc);

    printf("Asc:\n");
    for (int i = 0; i < n; i++) {
        printf("Name: %s\t Age: %d\n", people[i].name, people[i].age);
    }
    printf("\n");

    // 降序排序
    bubble_sort1(people, n, sizeof(Person), cmp_desc);

    printf("Desc:\n");
    for (int i = 0; i < n; i++) {
        printf("Name: %s\t Age: %d\n", people[i].name, people[i].age);
    }

    return 0;
}

// 实现一个自定义的模拟qsort函数
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char name[20];
    int age;
} Person;

int cmp_asc(const void *a, const void *b)
{
    Person *pa = (Person *)a;
    Person *pb = (Person *)b;
    if (strcmp(pa->name, pb->name) != 0) {
        return strcmp(pa->name, pb->name);
    } else {
        return pa->age - pb->age;
    }
}

int cmp_desc(const void *a, const void *b)
{
    Person *pa = (Person *)a;
    Person *pb = (Person *)b;
    if (strcmp(pa->name, pb->name) != 0) {
        return strcmp(pb->name, pa->name);
    } else {
        return pb->age - pa->age;
    }
}

//交换 --一个字节一个字节的交换,共交换width次
void Swap(char* buf1, char* buf2, size_t width)
{
	size_t i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}
void my_BubbleSort(void* base, size_t num,size_t width, int(*cmp)(const void* e1, const void* e2))
{
	//冒泡排序
	//若要排序n个元素,只需要进行n-1趟
	//每一趟可以少比较一个元素,每一趟可以使一个元素在确定的位置上
	//num:要排序元素的个数 类型是size_t 
    //num是无符号数 防止产生警告 所以i和j也定义为size_t
    // size_t == unsigned int 
	size_t i = 0;
	size_t j = 0;
 
	//共进行num-1趟
	for (i = 0; i < num; i++)
	{
		//每一趟
		for (j = 0; j < num - 1 - i; j++)
		{
			//比较
			//传地址   
			//相邻两个元素比较   width:宽度,每个元素所占字节
			//排成升序
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
				//交换两数
				Swap( (char*)base + j * width, (char*)base + (j + 1) * width, width );
			}
		}
	}
}


int main()
{
    Person people[] = {
        {"Alice", 18},
        {"Bob", 20},
        {"Charlie", 19},
        {"David", 18},
        {"Ella", 20}
    };
    int n = sizeof(people) / sizeof(Person);

    // 升序排序
    my_BubbleSort(people, n, sizeof(Person), cmp_asc);

    printf("Asc:\n");
    for (int i = 0; i < n; i++) {
        printf("Name: %s\t Age: %d\n", people[i].name, people[i].age);
    }
    printf("\n");

    // 降序排序
    my_BubbleSort(people, n, sizeof(Person), cmp_desc);

    printf("Desc:\n");
    for (int i = 0; i < n; i++) {
        printf("Name: %s\t Age: %d\n", people[i].name, people[i].age);
    }

    return 0;
}

使用qsort对字符串数组进行排序:

// 使用qsort函数来对字符串数组进行升序和降序排序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STR_NUM 10
#define MAX_STR_LEN 20

int cmpAsc(const void *a, const void *b)
{
    char **pa = (char **)a;
    char **pb = (char **)b;
    return strcmp(*pa, *pb);
}

int cmpDesc(const void *a, const void *b)
{
    char **pa = (char **)a;
    char **pb = (char **)b;
    return -strcmp(*pa, *pb);
    return strcmp(*pb, *pa);
}

int main()
{
    int n = 3;
    int i = 0;
    char **strs = (char **)malloc(n * sizeof(char *));
    char *str0 = (char *)malloc(100);
    for (i = 0; i < 3; ++i) {
        strs[i] = (char *)malloc(100);
    }
    snprintf(strs[0], 100, "ff str0\n");
    snprintf(strs[1], 100, "dd str1\n");
    snprintf(strs[2], 100, "aa str2\n");

    // 升序排序
    qsort(strs, n, sizeof(char *), cmpAsc);

    printf("\nAsc: \n");
    for(int i = 0; i < n; i++) {
        printf("%s", strs[i]);
    }
    printf("\n");

    // 降序排序
    qsort(strs, n, sizeof(char *), cmpDesc);

    printf("\nDesc: \n");
    for(int i = 0; i < n; i++) {
        printf("%s", strs[i]);
    }
    printf("\n");

    return 0;
}
// 使用qsort函数对字符串数组进行排序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


// 在实际使用时,比较函数的参数应该根据实际情况转换为正确的指针类型。
// 在字符串数组中,每个元素都是指向一个字符串的指针,
// 因此需要将`const void *`类型的指针转换为`char **`类型的指针,即指向指针的指针,然后才能解引用该指针,
// 即使用`*(char **)a`,获取指向的字符串。
// 如果使用`(char *)a`进行强制类型转换,`char *`类型的指针是单层指针,而不是指针的指针。
// 这将导致在解引用该指针时不能得到正确的字符串指针,从而产生错误的答案。
// 因此,在使用指针数组中的字符串进行排序时,
// 必须使用`char **`类型的指针进行指针转换,再解引用该指针获取到正确的字符串指针进行比较,才能保证排序的正确性。
// a和b的值是strs的元素的地址,也就是指针的指针,所以void其实是char*,void*就是char**
// strs的每个元素都是一个指针,每个元素的地址就应该用指针的指针来存储
// 所以a和b就是指针的指针,所以void*就是char**,void想当于char*
int cmp(const void *a, const void *b)
{
    printf("a : %p, b : %p\n", a, b);
    char *tmpa = (char *)a;
    char *tmpb = (char *)b;
    char **tmpaa = (char **)a;
    char **tmpbb = (char **)b;
    printf("*tmpa:  %s, **tmpaa:%s\n", tmpa, *tmpaa);
    printf("tmpa: %p, tmpb: %p, tmpaa: %p, tmpbb: %p\n",
             tmpa, tmpb, tmpaa, tmpbb);
    // 调试后发现:
    // a存放的是strs[0]的地址(char**类型)b存放的是strs[1]的地址(char**类型)        
    // strcmp()会将p地址对应的内容转化成字符串,也就是将strs[0~2]的地址转化成字符串,将得到一个乱码
    // 因为将(char **类型的数据转换成了char *类型的数据,这样解引用出来的字符串当然是错误的
    // 因此得先把a,b转化成char**,这样解引用以后才是一个char*的地址
    // return strcmp(tmpa, tmpb);
    // return strcmp(*tmpaa, *tmpbb);
    // 用指针的方式进行排序
    return strcmp(*(char **)a, *(char **)b);
    // 不能将二级指针直接解引用,这样借用用后的值为1个一级指针,而不是一个字符串,
    // 因此需要转换成char **类型后在进行解引用操作
    // return strcmp((char *)a, (char *)b);
}

int main()
{
    int n = 3;
    int i = 0;
    char **strs = (char **)malloc(n * sizeof(char *));
    char *str0 = (char *)malloc(100);
    for (i = 0; i < 3; ++i) {
        strs[i] = (char *)malloc(100);
    }
    printf("strs: %p, *strs: %p, strs[0]: %p, strs[1]: %p, strs[2]: %p\n",
            strs, *strs, strs[0], strs[1], strs[2]);
    printf("strs: %p, &strs[0]: %p, &strs[1]: %p, &strs[2]: %p\n",
            strs, &strs[0], &strs[1], &strs[2]);

    snprintf(strs[0], 100, "ff str0\n");
    snprintf(strs[1], 100, "dd str1\n");
    snprintf(strs[2], 100, "aa str2\n");

    printf("\nbefore sort:\n");
    for (i = 0; i < n; ++i) {
        printf("%s", strs[i]);
    }

    // 传入的参数为strs[0~2],即指针的指针
    qsort(strs, n, sizeof(char *), cmp);

    printf("\nafter sort:\n");
    for (i = 0; i < n; ++i) {
        printf("%s", strs[i]);
    }
    printf("\n");

    for (i = 0; i < n; ++i) {
        free(strs[i]);
    }
    free(strs);

    return 0;
}

通过以上代码可以活得一个经验,在进行字符串数组比时较需要注意如下问题:

不能在自定义的数据比较函数中return strcmp((char *)a, (char *)b);

而是应该return strcmp(*(char **)a, *(char **)b);

strs是一个指针数组,保存3个指针,也就是说&strs[0], &strs[1], &strs[2]都是二级指针,

地址分别为

0x555555757260

0x555555757268

0x555555757270

这3个二级指针分别各自保存1个一级指针,分别为strs[0], strs[1], strs[2]

指针的地址和保存的字串分别为:

0x5555557572f0 "ff str0\n"

0x555555757360 "dd str1\n"

0x5555557573d0 "aa str2\n"

而传入到cmp函数中的指针为二级指针&strs[0], &strs[1], &strs[2]

(用void *类型作为形参类型,并于不同类型数据的转换),

二级指针保存一级指针的地址对应关系为:

&strs[0]: 0x555555757260 ->  strs[0]:0x5555557572f0 "ff str0\n"

&strs[1]: 0x555555757268->  strs[0]:0x555555757360 "dd str1\n"

&strs[2]: 0x555555757270->  strs[0]:0x5555557573d0 "aa str2\n"

若将传入的二级指针转换成char *类型,则接应用时去除的字符串是一个乱码,

因为二级指针保存的值为1个一级指针,所以接应用后的值仍然是一个一级指针,

而这个一级指针指向的内容才是需要获取的字符串。