💕是非成败转头空，青山依旧在，几度夕阳红💕
作者：Mylvzi
文章主要内容：快速排序和qsort函数详解
前言：
我们之前学习过冒泡排序，冒泡排序尽管很方便，但也存在一些局限性，冒泡排序只能排序整型数据，对于浮点型的数据以及结构体数据的排序无能为力，但是在C语言的库中，有一个库函数能够实现这样的排序-->qsort函数
qsort函数其实是一种基于快速排序的算法，其时间复杂度为O(N*logN),下面带大家了解一下快速排序算法：
一.快速排序：QuickSort
分析：
可以知道，快速排序的核心在于“分区操作”，即每次都要根据基准元素进行分区；
代码实现：
//QuickSort 排序 的实现 //找基准元素，分区，递归，合并 //交换函数 void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } //分割函数：以基准元素为轴，分而治之 int Partition(int arr[], int left, int right)//返回值：基准元素的下标 { //设置默认基准元素 int pivot = arr[right]; int i = left-1;//将小于基准元素的值放在左边，i是左子数组的下标 //遍历数组，移动元素 for (int j = left; j <= right; j++) { if (arr[j] < pivot)//小于，就放到左边,交换值 { i++; Swap(&arr[i], &arr[j]); } } //将基准元素置于轴 Swap(&arr[i + 1], &arr[right]); return i + 1; } void QuickSort(int arr[], int left, int right)//left左下标 right右下标 { if (left < right) { //找到基准元素的下标 int PivotIndex = Partition(arr, left, right); //对左子数组进行递归分区 QuickSort(arr, left, PivotIndex - 1); //对右子数组进行递归分区 QuickSort(arr, PivotIndex + 1, right); } } int main() { int arr[] = { 6, 3, 8, 5, 2, 7, 4 }; int n = sizeof(arr) / sizeof(arr[0]); //打印原数组 printf("Original array: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } // 调用快速排序函数对数组进行排序 QuickSort(arr, 0, n-1); //打印排序之后的数组 printf("\nSorted array: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
验证：
优化QuickSort:
优化一：
缺陷：选取的pivot如果是整个序列的中间值，在第一次partition之后，会得到一个较为平均的分区，处理这样的分区更加简单，效率更高（处理4 4比处理1 8更简单）
解决方法：利用三数取中法使我的pivot是中间值的概率更高
得到数组左中右下标的数据，使pivot为中间值
//设置默认基准元素 int pivot; //优化一：三数取中法优化pivot的取值（处理4 4比处理1 8简单） //不能固定取同一位置的元素为pivot int m = left+ (right - left) / 2; if (arr[left] < arr[right])//保证右边元素较小 { Swap(&arr[left], &arr[right]); } if (arr[left] < arr[m])//保证中间元素较小 { Swap(&arr[m], &arr[right]); } if (arr[m] > arr[right])//保证右边元素是中间值 { Swap(&arr[m], &arr[left]); } pivot = arr[right];//将左中右三个元素的中间值赋给pivot
二.基于快速排序的函数-->qsort函数
原型：
代码1：比较整形数据
//qsort函数 //快速的排序算法，适用于不同的数据类型 //void qsort( // void* base,//需要被排序的数组（首地址） // size_t num,//数组元素个数 // size_t size,//元素类型大小 // int(*cmp)(const void* ptr1, const void* ptr2)//比较函数 // //ptr1 >ptr2 返回>0 交换位置 默认是升序排序的 //); //利用qsort函数进行冒泡排序 int cmp_int(const void* ptr1, const void* ptr2) { //默认是升序排序的 //结果>0,就会交换位置 return (*(int*)ptr1 - *(int*)ptr2); //降序-->添加负号 /*return -(*(int*)ptr1 - *(int*)ptr2);*/ } int main() { int arr[6] = { 4,25,6,78,534,94 }; int sz = sizeof(arr) / sizeof(arr[0]); qsort(arr, 6, sizeof(arr[0]), cmp_int); //打印输出排序后的数组 int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } return 0; }
代码2：比较结构体数据
typedef struct Stu { char name[20]; int age; }Stu; /*按年龄排序*/ int cmp_by_stu_age(const void* ptr1, const void* ptr2) { return ((struct Stu*)ptr1)->age - ((struct Stu*)ptr2)->age; } void test() { Stu arr[3] = { {"zhangsan",13},{"lisi",5},{"wangwu",18} }; //按年龄排序 int sz = sizeof(arr) / sizeof(arr[0]); qsort(arr, sz, sizeof(arr[0]), cmp_by_stu_age); } /*按照姓名排序*/ int cmp_stu_by_name(const void* ptr1, const void* ptr2) { return strcmp(((Stu*)ptr1)->name, ((Stu*)ptr2)->name); } void test2() { Stu arr[3] = { {"zhangsan",13},{"lisi",5},{"wangwu",18} }; int sz = sizeof(arr) / sizeof(arr[0]); qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_name); } //排序结构体 int main() { //test(); test2(); return 0; }
代码3：利用冒泡排序的思想模拟实现qsort函数
//利用冒泡排序的思想模拟qsort函数 //模仿qsort的参数 //未知类型数组-->void* base -->起始地址 //元素个数-->int num //未知类型-->int size //比较函数-->将需要比较的数据传递给cmp函数，根据其返回值判断是否需要交换位置 //如果返回值>0，就交换元素位置（一个一个字节交换） void Swap(char* buf1, char* buf2,int size) { int i = 0; for (i = 0; i < size; i++) { int tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } } void bubble_sort(void* base, int num, int size, int(*cmp)(const void* ptr1, const void* ptr2)) { //基本逻辑不变，两两比较，一次确定一个元素的位置 int i = 0;//趟数 sz-1趟 int j = 0;//每次需要比较的元素个数 for (i = 0; i < num - 1; i++) { for (j = 0; j < num - 1 - i; j++) { //初始地址 if (cmp((char*)base + j * size, (char*)base + (j+1) * size) > 0)//比较的的是前后两个元素的地址的数据-->计算地址-->(char*)base+j*size-->返回值>0,就交换 { //前面的元素>后面元素就交换位置 Swap((char*)base + j * size, (char*)base + (j + 1) * size, size); } } } } int main() { int arr[6] = { 4,25,6,78,534,94 }; int sz = sizeof(arr) / sizeof(arr[0]); qsort(arr, 6, sizeof(arr[0]), cmp_int); for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); } return 0; }
