前言
在上篇指针进阶中，我们对函数指针、函数指针数组、函数指针数组指针以及回调函数有了一定的了解，文章末尾简单的对qsort函数进行了展示，今天我们主要以qsort函数用冒泡排序的模拟实现以及各种类型的排序，后面针对指针和数组一些细节上的讲解~
一、qsort函数介绍
qsort是一个库函数，快速排序的方法来实现的， 头文件是<stdlib.h>
qsort库函数：
void qsort( void *base, size_t num, size_t size, int (*compare )(const void *, const void *) );
传入的参数，一个是指针，一个整形，一个整形，一个函数指针；
base 数组首元素（就是数组名），num数组里有多少个元素，size每个元素的大小（单位是字节），compare指向数组中比较方式的函数指针；
功能介绍：
使用函数确定顺序，对指向的数组的元素进行排序，每个元素的长度以字节为单位。
此函数使用的排序算法通过调用指定的函数(要自己定义元素比较方式函数传给qsort)并将指向元素的指针作为参数来比较元素.
该函数不返回任何值，而是通过按定义重新排序数组元素来修改指向的数组的内容。
二、qsort函数的应用
由于使用qsort函数时，并不知道要排序的元素是什么类型，这时需要写一个compare函数，并对立面的参数强制类型转化
2.1 整型数组排序
#include<stdio.h> #include<stdlib.h> void Print(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } } int com_int(const void* e1, const void* e2) { return *(int*)e1 - *(int*)e2; } int main() { int arr[] = { 1,3,7,5,8,9,0,2,4,6 }; int sz = sizeof(arr) / sizeof(arr[0]); qsort(arr, sz, sizeof(arr[0]), com_int); Print(arr, sz); return 0; }
运行结果：
0 1 2 3 4 5 6 7 8 9
2.2 浮点型数组排序
#include <stdio.h> #include <stdlib.h> void Print(double arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%2.2lf ", arr[i]); } } int com_double(const void* e1, const void* e2) { return *(double*)e1 - *(double*)e2; } int main() { double arr[6] = { 8.26, 65.5, 73.53, 43.45, 95.3, 19.5 }; int sz = sizeof(arr) / sizeof(arr[0]); qsort(arr, sz, sizeof(arr[0]), com_double); Print(arr, sz); return 0; }
运行结果：
8.26 19.50 43.45 65.50 73.53 95.30
2.3 字符型排序
#include <stdio.h> #include <stdlib.h> void Print(char arr[],int sz) { for (int i = 0; i < sz; i++) printf("%c ", arr[i]); } int char_sort(const void* e1, const void* e2) { return (*(char*)e1) - (*(char*)e2); } int main() { char arr[10] = { 'd','g','b','a','e','i','h','c','j','f' }; int sz = sizeof(arr) / sizeof(arr[0]); qsort(arr, sz, sizeof(arr[0]), char_sort); Print(arr, sz); return 0; }
运行结果：
a b c d e f g h i j
2.4 结构体数组排序
#include <stdio.h> #include <stdlib.h> typedef struct student { char name[15]; int age; float score; }S; void Print(struct student* stu,int sz) { for (int i = 0; i < sz; i++) { printf("%-12s %-5d %-5.2fm\n", stu[i].name, stu[i].age, stu[i].score); } } int com_age(const void* e1, const void* e2) { return (((S*)e1)->age - ((S*)e2)->age); } int com_score(const void* e1, const void* e2) { return ((S*)e1)->score - ((S*)e2)->score; } int com_name(const void* e1, const void* e2) { return strcmp(((S*)e1)->name, ((S*)e2)->name); } int main() { S stu[5] = { {"chu jie niu",20,1.73f}, {"xiao wang",19,1.68f}, {"qing niao",21,1.59f}, {"wao shu li",16,1.83f}, {"peng hu wan",15,1.81f} }; int sz = sizeof(stu) / sizeof(stu[0]), input = 0; qsort(stu, sz, sizeof(stu[0]), com_age); printf("姓名 年龄 身高\n"); Print(stu, sz); return 0; }
运行结果：
姓名 年龄 身高 peng hu wan 15 1.81 m wao shu li 16 1.83 m xiao wang 19 1.68 m chu jie niu 20 1.73 m qing niao 21 1.59 m
三、qsort模拟实现(冒泡排序)
3.1 冒泡排序
#include <stdio.h> void Print(int arr[], int sz) { for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); } } 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[] = { 5,3,7,6,1,8,9,2,4,0 }; int sz = sizeof(arr) / sizeof(arr[0]); bubble_sort(arr,sz); Print(arr, sz); return 0; }
3.2 qsort模拟实现
第一步：冒泡函数的参数
首先要修改的是冒泡排序函数的参数
void bubble_sort(void* arr,size_t num,size_t width,int(*compare)(const void*,const void*))
需要注意的是qsort函数事先是不知道传过来的数组是什么类型，所以都先用void*接受
第二步：比较元素的方法
在对两元素比较时，事先是不知道类型的
- 要先将arr强制类型转化为char*，因为一个字节是类型的最小单位，这时候就需要用到width了
- 元素的比较方式不再是单一的相减，这里用到自定义函数，元素的比较方式函数
if(cmp((char*)arr+jwidth),(char)arr+(j+1)*width)>0)
第三步：交换函数
修改为char*类型进行交换
swap(char* e1, char* e2, int width) { int i = 0; char p = 0; for (i = 0; i < width; i++) { p = *(e1 + i); *(e1 + i) = *(e2 + i); *(e2 + i) = p; } }
注意：
void*可以接受任何类型的变量，但是并不能直接使用，要强制类型转化为对应类型使用
代码展示：
#include <stdio.h> void Print(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } } void swap(char* e1, char* e2, int width) { int i = 0; char p = 0; for (i = 0; i < width; i++) { p = *(e1 + i); *(e1 + i) = *(e2 + i); *(e2 + i) = p; } } void bubble_sort(void* base, int sz, int width, int (*cmp)(const void* e1, const void* e2)) { int i = 0; int j = 0; for (i = 0; i < sz; i++) { for (j = 0; j < sz - 1 - i; j++) { if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0) { swap((char*)base + j * width, (char*)base + (j + 1) * width, width);//一个字节一个字节的交换 } } } } int com_int(const void* e1, const void* e2) { return *(int*)e1 - *(int*)e2; } int main() { int arr[] = { 1, 3, 6, 2, 0, 9, 4, 8, 5, 7 }; int sz = sizeof(arr) / sizeof(arr[0]); bubble_sort(arr, sz, sizeof(arr[0]), com_int); Print(arr, sz); return 0; }
qsort函数用冒泡排序的模拟实现就讲到这里，指针的进阶也到此结束了，接下来对指针和数组一些细节上的补充到时候会在文章见分晓，欢迎大家互三，一起交流，互相学习~~
