今天主要讲解一下qsort函数的使用，以及通过冒泡排序来模拟qsort函数
Bubble_sort
冒泡排序
先来看段简单的冒泡排序（升序）代码：
#include<stdio.h>
void Bubble_sort(int* arr, int sz)
{
int i = 0;
for (i = 0; i < sz - 1; i++)
{
int j = 0;
for (j = 0; j < sz - i - 1; j++)
{
if (*(arr + j) > *(arr + j + 1))
{
int tmp = *(arr + j);
*(arr + j) = *(arr + j + 1);
*(arr + j + 1) = tmp;
}
}
}
}
int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
Bubble_sort(arr, sz);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}想象一下，如果数组本身的数据排序就是升序，没有必要再去排序，但对于这种冒泡排序岂不是也要在排一遍，不够优化。
冒泡排序优化
#include<stdio.h>
void Bubble_sort(int* arr, int sz)
{
int i = 0;
for (i = 0; i < sz - 1; i++)
{
int flag = 1;//假设数组是升序
int j = 0;
for (j = 0; j < sz - i - 1; j++)
{
if (*(arr + j) > *(arr + j + 1))
{
int tmp = *(arr + j);
*(arr + j) = *(arr + j + 1);
*(arr + j + 1) = tmp;
flag = 0;//数组不是升序
}
}
if (flag == 1)
{
break;
}
}
}
int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
Bubble_sort(arr, sz);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}这样是不是效率就提高了不少呢？
但是
有没有思考过这样一个问题，这样的冒泡排序再怎么优化只能实现对整形数组的排序，（形参接收类型为int*）对其他的类型却无法实现排序?
对于qsort函数来说，这都不是问题，她说：“我可以排序任意类型的数据~”。
qsort的使用
void*类型
先看一下qsort类型函数是如何定义的
第一个参数：数组首元素地址
第二个参数：需要排序的长度
第三个参数：每个元素的类型大小（单位：字节）
第四个参数：函数指针——比较函数,e1和e2是需要比较的两个元素的地址
为什么会出现void*的指针呢？
viod*是无类型指针，可以接收任意类型的数据，但是要注意，对于void*指针，不能进行解引用操作，也不能+1-1操作，需要进行强制类型转换，例如我传入一个整形，如下代码
int* a = (int*)e1;创建一个整形指针来存放强制转换后的指针。
这第四个参数是什么意思呢？
qsort函数可以排序任意类型的数据，但是，她也不知道你要让他排什么类型的数据，因为不同类型的数据比较的方法不一样，（整形数据，大于小于号就可以比较，那对于结构体呢？）所以这个时候，就引入了第四个参数——函数指针，这个比较函数需要自己设计，此函数返回类型是int，规定若返回于一个大于零的数就按降序排序，若返回一个小于零的数就按升序排序
还是有点懵？继续往下看~
qsort实现各种类型排序
为了便于理解，比较函数写成以下形式：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int cmp_int(const void* _a, const void* _b)
{
int* a = (int*)_a;
int* b = (int*)_b;
return *a - *b;
}
int cmp_char(const void* _a, const void* _b)
{
char* a = (char*)_a;
char* b = (char*)_b;
return strcmp(a, b);
}
int cmp_double(const void* _a, const void* _b)
{
double* a = (double*)_a;
double* b = (double*)_b;
return *a > *b ? 1 : -1;
}
int main()
{
int in[] = { 2,5,6,4,8,7,1,3 };
char ch[] = "helloworld";
double dou[] = { 5.6,5.2,7.2,5.6,4.8,9.1,4.2 };
int size_in = sizeof(in) / sizeof(in[0]);
int size_ch = sizeof(ch) / sizeof(ch[0]);
int size_dou = sizeof(dou) / sizeof(dou[0]);
qsort(in, size_in, sizeof(in[0]), cmp_int);
qsort(ch, size_ch, sizeof(ch[0]), cmp_char);
qsort(dou, size_dou, sizeof(dou[0]), cmp_double);
//打印整形
int i = 0;
for (i = 0; i < size_in; i++)
{
printf("%d ", in[i]);
}
printf("\n");
//打印字符串
for (i = 0; i < size_ch; i++)
{
printf("%c", ch[i]);
}
printf("\n");
//打印浮点数
for (i = 0; i < size_dou; i++)
{
printf("%lf ", dou[i]);
}
printf("\n");
return 0;
}这里可以明显体现出不同类型之间的不同比较方式。
当然比较函数也可做如下调整，看起来更简洁~
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
int cmp_char(const void* e1, const void* e2)
{
return strcmp((char*)e1, (char*)e2);
}
int cmp_double(const void* e1, const void* e2)
{
return *(double*)e1 > *(double*)e2 ? 1 : -1;
}
接下来看一下结构体类型的比较
实际上也是整形、字符、字符串...等类型的比较。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct stu
{
char name[30];
int age;
};
int cmp_struct(const void* e1, const void* e2)
{
return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name);
}
int main()
{
struct stu s[] = {{"Franz Liszt",36},{"F.F.Chopin",45},{"Johann Sebastian Bach",35}};
int sz = sizeof(s) / sizeof(s[0]);
qsort(s, sz, sizeof(s[0]), cmp_struct);
return 0;
}想知道qsort内部是如何运作的吗？
往下走~
Bubble_sort模拟实现qsort
这回我们试试通过改造冒泡排序来实现qsort函数
#include<stdio.h>
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
void Swap(size_t width, char* e1,char* e2)
{
int i = 0;
for (i = 0; i < width; i++)
{
char tmp = *e1;//以最小单位一个一个字节的交换
*e1 = *e2;
*e2 = tmp;
e1++;//两地址加加，向后访问，直到到达此类型大小为止
e2++;
}
}
void Bubble_sort(void* base, size_t sz, size_t width, int(*cmp)(const void* elem1, const void* elem2))
{
int i = 0;
for (i = 0; i < sz - 1; i++)
{
int flag = 1;//假设数组是升序
int j = 0;
for (j = 0; j < sz - i - 1; j++)
{
if (cmp_int((char*)base + j * width, (char*)base + (j + 1) * width) > 0)//找到交换的起始位置地址
{//这里用char类型是因为不知道这个函数会传入什么类型，所以就用char类型，char类型可以一个一个字节的访问
//乘上每个元素的大小（width）就可以跳过该类型的大小
Swap(width, (char*)base + j * width, (char*)base + (j + 1) * width);
flag = 0;//数组不是升序
}
}
if (flag == 1)
{
break;
}
}
}
int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
Bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}解释说明都在代码注释里啦~
