用qsort 函数优化冒泡排序

109 阅读 0 评论 72 点赞

我是靠谱客的博主自信乌冬面，这篇文章主要介绍用qsort 函数优化冒泡排序，现在分享给大家，希望可以做个参考。

在讲解qsort函数之前，我们先来复习一下冒泡排序

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<stdio.h>
int main()
{
int i=0,j=0;
int arr[]={1,2,3,4,5,6,7,8,9,10};
int sz=sizeof(arr)/sizeof(arr[0]);
for(i=0;i<sz;i++)
{
for(j=0;j<sz-i-1;j++)
{
if(arr[j+1]>arr[j])
{
int temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
}

通过双循环来将整数数组进行排列，相比于传统的将各个数进行比较其大小，但是其缺点也显而易见，那就是传统的冒泡排序只能对整型进行排序，功能十分单一，接下来我们就利用qsort函数的思想来优化代码，使其成为可以排序任意类型的一串代码。

再开始改造之前，我们首先需要了解一下qsort函数

void* qsort(void* base,size_t num,size_t width,int(*cmp)(const void*e1,const void* e2))

第一个参数表示需要排序参数的首地址，第二个参数是排序内容的个数，第三个参数表示字节大小，最后一个参数为一个函数，此函数为一个比较函数，需要我们自己来实现。

复制代码

1
2
3
4
char cmp(const void* e1, const void* e2)
{
return (*(char*)e1 - *(char*)e2);
}

函数的类型由自己来定义，此函数为升序，若要实现降序就讲两参数相互对掉即可。

接下来模拟qsort函数

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void my_qsort(void* base, int num, int width, char(*cmp)(const void*e1, const void* e2))
{
int i = 0;
char tmp[16];
for (i = 0; i < num-1; i++)
{
int j = 0;
for (j = 0; j < num - 1 - i; j++)
{
if (cmp((char*)base+j*width,(char*)base+(j+1)*width) > 0)
{
memcpy(tmp, (char*)base + j * width,width);
memcpy((char*)base + j * width, (char*)base + (j + 1)*width,width);
memcpy((char*)base + (j + 1)*width, tmp, width);
}
}
}
}

定义tmp为16个字节是为了防止long double类型，利用memcpy库函数来防止发生其他不必要的麻烦，完整代码如下（以排序字符串为例）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<stdio.h>
#include<string.h>
char cmp(const void* e1, const void* e2)
{
return (*(char*)e1 - *(char*)e2);
}
void my_qsort(void* base, int num, int width, char(*cmp)(const void*e1, const void* e2))
{
int i = 0;
char tmp[16];
for (i = 0; i < num-1; i++)
{
int j = 0;
for (j = 0; j < num - 1 - i; j++)
{
if (cmp((char*)base+j*width,(char*)base+(j+1)*width) > 0)
{
memcpy(tmp, (char*)base + j * width,width);
memcpy((char*)base + j * width, (char*)base + (j + 1)*width,width);
memcpy((char*)base + (j + 1)*width, tmp, width);
}
}
}
}
int main()
{
char arr[10] = "fedcba";
int sz = strlen(arr);
my_qsort(arr,sz,sizeof(char),cmp);
puts(arr);
return 0;
}