qsort函数实现排序及自己实现qsort函数

1.qsort函数实现排序1.1 qsort函数实现整形排序1.2qsory实现浮点数排序1.3 qsort函数实现对字符串比较2.利用冒泡排序实现qsort函数

1.qsort函数实现排序

qsort函数是无类型比较函数：对任意类型的数据进行排序（整型，浮点型，字符串类型等）

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

注意：qsort函数中的第四个参数 compar是自己写的

其中：

void* base：待排序数据的起始地址（void也可以看看出是无类型排序）

size_t num：待排序数据的个数

size_t size：待排序数据每个元素的大小 与类型无关

int (compar)(const void,const void)（函数指针）：对待排序的数据进行比较;compar函数需要传入的两个参数为待比较数据的地址

注意

qsort函数不关心数据类型，但compar比较函数需要关心数据类型；compar的返回值为int，决定排序算法的升或降,共有三种情况：1、0、-1

（0表示待比较的数据相等，1表示待比较的数据需要交换位置，大数在后）

1.1 qsort函数实现整形排序

下面以整型数组排序为例

int arr[] = { 3,2,5,7,34,1,342,782,-9,6,32,1 }；

#include <stdio.h>#pragma warning(disable:4996)#include<Windows.h>#include<assert.h>//传入数据加const 因为待比较的两个数据一般中间不会修改int CompInt(const void *xp, const void *yp)// *xp、*yp是待比较两个元素的地址{// 对参数合法性进行校验assert(xp);assert(yp);// 将待比较的两个元素类型进行强转const int *x = (const int*)(xp);const int *y = (const int*)(yp);if (*x>*y){return 1;// 升序 若为-1为降序}else if (*x < *y){return -1;}else{return 0;}}int main(){int arr[] = {3,2,5,7,34,1,342,782,-9,6,32,1 };int num = sizeof(arr) / sizeof(arr[0]);qsort(arr, num, sizeof(int), CompInt);for (int i = 0; i < num; i++){printf("%d ", arr[i]);}}

1.2qsory实现浮点数排序

3.89,2.7,5.34,7.87,3.4,1.98,34.29,78.2,-9.987,6.797,32.89,1.1

#include <stdio.h>#pragma warning(disable:4996)#include<Windows.h>#include<assert.h>//传入数据加const 因为待比较的两个数据一般中间不会修改int CompDouble(const void *xp, const void *yp)// *xp、*yp是待比较两个元素的地址{// 对参数合法性进行校验assert(xp);assert(yp);// 将待比较的两个元素类型进行强转const double *x = (const double*)(xp);const double *y = (const double*)(yp);if (*x>*y){return 1;}else if (*x < *y){return -1;}else{return 0;}}int main(){double arr[] = {3.89,2.7,5.34,7.87,3.4,1.98,34.29,78.2,-9.987,6.797,32.89,1.1 };int num = sizeof(arr) / sizeof(arr[0]);qsort(arr, num, sizeof(double), CompDouble);for (int i = 0; i < num; i++){printf("%f\n", arr[i]);}}

1.3 qsort函数实现对字符串比较

“abcdg12689”

“acasDhxsH76t”

字符串比较规则

从左向右依次比较字符串字符的ASCALL码

例如：

char *arr[] = {

“abcgyd6795”,

“asaA8389”,

“SFsasd9f8”,

“efawekHCSF08”,

“34fa3AFQW”

};

#include <stdio.h>#pragma warning(disable:4996)#include<Windows.h>#include<assert.h>//传入数据加const 因为待比较的两个数据一般中间不会修改int CompString(const void *xp, const void *yp)// *xp、*yp是字符指针的地址 void*可以保存二级指针{// 对参数合法性进行校验assert(xp);assert(yp);// 将待比较的两个元素类型进行强转const char **x = (const char**)(xp);const char **y = (const char**)(yp);//定义两个指针指向待比较的两个字符串的起始地址// *x *y表示待比较的两个字符串首地址char *_x = *x;char *_y = *y;while (*_x||*_y) // 字符串元素不为0，即字符串元素没有对比完{if (*x > *y){return 1;}else if (*x < *y){return -1;}*_x++; *_y++;}return 0;}int main(){// 将多个字符串存放在二维字符数组中char *arr[] = {"abcgyd6795","asaA8389","SFsasd9f8","efawekHCSF08","34fa3AFQW"};int num = sizeof(arr) / sizeof(arr[0]);qsort(arr, num, sizeof(char *), CompString);// 每个元素类型是一个字符指针for (int i = 0; i < num; i++){printf("%s\n", arr[i]);}}

字符串比较时也可以直接用字符串比较函数strcmp

#include <stdio.h>#pragma warning(disable:4996)#include<Windows.h>#include<assert.h>#include<string.h>//传入数据加const 因为待比较的两个数据一般中间不会修改int CompString(const void *xp, const void *yp)// *xp、*yp是字符指针的地址 void*可以保存二级指针{// 对参数合法性进行校验assert(xp);assert(yp);// 将待比较的两个元素类型进行强转const char **x = (const char**)(xp);const char **y = (const char**)(yp);return strcmp(*x, *y);}int main(){// 将多个字符串存放在二维字符数组中char *arr[] = {"abcgyd6795","asaA8389","SFsasd9f8","efawekHCSF08","34fa3AFQW"};int num = sizeof(arr) / sizeof(arr[0]);qsort(arr, num, sizeof(char *), CompString);// 每个元素类型是一个字符指针for (int i = 0; i < num; i++){printf("%s\n", arr[i]);}}

2.利用冒泡排序实现qsort函数

//-----------自己实现qsort函数-------------- #include <stdio.h>#pragma warning(disable:4996)#include<Windows.h>#include<assert.h>#include<string.h>int CompString(const void *xp, const void *yp)// *xp、*yp是字符指针的地址 void*可以保存二级指针{// 对参数合法性进行校验assert(xp);assert(yp);// 将待比较的两个元素类型进行强转const char **x = (const char**)(xp);const char **y = (const char**)(yp);return strcmp(*x, *y);}static void swap(char *x,char *y, size_t num){while (num){char temp = *x;*x = *y;*y = temp;x++, y++;num--;}}// comp是回调函数int MyQsort(void *base,size_t num, size_t size,int(*comp)(const void*,const void*))// size_t是类型重命名 无符号整性{// 对传入指针的合法性进行校验assert(base);assert(comp);// 下面是将待比较元素进行比较交换// 但是这块存在一个问题，就是不知道元素是什么类型，交换的时候应该交换几个字节？？？// 例如 int整型 是4个字节 char 字符型是1个字节// 解答：不管是什么类型，每次交换一个字节char *p = (char*)base;// 冒几轮for (int i = 0; i < num-1; i++){for (int j = 0; j < num - i-1; j++){if (comp(p+j*size,p+(j+1)*size)>0) //比较两个元素{swap(p + j * size, p + (j + 1)*size,size);// size 个字节}}}}int main(){// 将多个字符串存放在二维字符数组中char *arr[] = {"abcgyd6795","asaA8389","SFsasd9f8","efawekHCSF08","34fa3AFQW"};int num = sizeof(arr) / sizeof(arr[0]);MyQsort(arr, num, sizeof(char *), CompString);// 每个元素类型是一个字符指针for (int i = 0; i < num; i++){printf("%s\n", arr[i]);}}