用冒泡排序的方法模拟实现qsort函数

分析：

用冒泡排序的方法实现快速排序主要是用回调函数的知识，我们知道库函数中qsort的函数原型是：

void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );

函数原型中qsort函数有四个参数，分别为

base:是指目标数组的开始位置，可以理解为数组首元素的地址；

num:是指数组中元素的个数；

width:是指数组中每个元素的类型的大小；

compare:是一个函数指针，是一个比较函数，它的返回值是int,通过它来判断要比较的元素的类型；

下面是使用qsort函数例子：

#include<stdio.h>
#include<stdlib.h>
int int_cmp(const void *elem1, const void *elem2)
{
return *(int *)elem1 - *(int *)elem2;
}
int str_cmp(const void *elem1, const void *elem2)
{
return (char *)*(int *)elem1 - (char *)*(int *)elem2;
}
int main()
{
int arr[] = { 1, 5, 4, 3, 8, 7, 9, 5, 3, 4, 0 };
int size = sizeof(arr) / sizeof(arr[0]);
int i = 0;
qsort(arr, size, sizeof(int), int_cmp);
for (i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
system("pause");
return 0;
}

 我们也可以排序字符串

int main()
{
 char *arr[] = { "ddd","cccc","aaaa","bbbb" };
 int size = sizeof(arr) / sizeof(arr[0]);
 int i = 0;
 qsort(arr, size, sizeof(char *), str_cmp);
 for (i = 0; i < size; i++)
 {
  printf("%s ", arr[i]);
 }
 system("pause");
 return 0;
}

qsort可以实现多种类型的排序，我们可以模拟实现它。

要实现它我们要注意以下几点：

1. 要实现这个函数我们首先要有比较函数，用来比较两个元素大小，判断返回值的大小来确定是否要交换两个元素。比较函数应设计为返回值int,参数为void * 类型的指针，因为我们要实现多种类型的元素的排序。

2. 还要一个交换函数，当两元素满足交换条件是交换它们。交换函数的类型应该为返回值为void，参数为两个char *类型指针（元素类型不同），还有一个是元素类型的大小（字节）。交换时应该以字节为单位交换。

以下是我的实现方法：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int struct_cmp(const void *elem1, const void *elem2)   //比较结构体元素大小

{
return (*(stu *)elem1).score - (*(stu *)elem2).score; 

//将void*强制类型转换为结构体指针并对它解引用访问成员score

}
int int_cmp(const void *elem1, const void *elem2)  //比较整型元素大小
{
return *(int *)elem1 - *(int *)elem2;

//将void*强制类型转换为整型指针并对它解引用
}
int str_cmp(const void *elem1, const void *elem2) //比较字符串大小
{
return strcmp((char *)*(int *)elem1 , (char *)*(int *)elem2);

//将void*强制类型转换为整型指针并对它解引用然后转换为char *类型的指针，用strcmp比较

}
void swap(char *elem1, char *elem2, int sz)    //实现两个元素的交换
{
int i = 0;
char tmp = 0;
for (i = 0; i < sz; i++)  //一字节为单位交换
{
tmp = *(elem1 + i);
*(elem1 + i) = *(elem2 + i);
*(elem2 + i) = tmp;
}
}
void bubble(void *base, int num, int width, int(*compare)(const void *elem1, const void *elem2))
{
int i = 0;
int j = 0;
int flag = 0;  //优化冒泡排序
char *arr = (char *)base;
for (i = 0; i < num-1; i++)
{
flag = 0;
for (j = 0; j < num-1-i; j++)
{
if (compare(arr + j*width, arr + (j + 1)*width)>0)   //比较将元素大小，若返回值大于0，则交换
{
swap((char *)(arr + j*width), (char *)(arr + (j + 1)*width), width);  //交换两个元素
flag = 1;
}

}
if (flag == 0)
break;
}
}

测试如下：

typedef struct S
{
char name[10];
float score;
}stu;
int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
int size = sizeof(arr)/sizeof(arr[0]);
int i = 0;

bubble(arr, size, sizeof(int), int_cmp);

for (i = 0; i < size; i++)

{
printf("%d ", arr[i]);
}

system("pause");
return 0;
}

int main()
{

 char *arr[] = { "aaa", "dddd", "cccc", "bbbb" };
 int size = sizeof(arr) / sizeof(arr[0]);
 int i = 0;
 bubble(arr, size, sizeof(char *),str_cmp);

 for (i = 0; i < size; i++)
 {
 printf("%s ", arr[i]);
 }
 system("pause");
 return 0;
}

int main()
{
stu arr[] = { { "圆圆", 98.0 }, { "冉冉", 97.0 }, { "天天", 96.0 }, { "雯雯", 99.0 } };
int size = sizeof(arr)/sizeof(arr[0]);
int i = 0;
bubble(arr, size, sizeof(stu), struct_cmp);

for (i = 0; i < size; i++)
{
printf("%s %f\n", arr[i].name,arr[i].score);
}
system("pause");
return 0;
}

用冒泡排序的方法模拟实现qsort函数

原文：http://haipi.blog.51cto.com/10778780/1720181