国外优秀的平面设计网站,网上竞价平台,为什么做网站必须用服务器,大型网络游戏排行榜2021前十名#x1f495;是非成败转头空#xff0c;青山依旧在#xff0c;几度夕阳红#x1f495; 作者#xff1a;Mylvzi 文章主要内容#xff1a;快速排序和qsort函数详解 前言#xff1a; 我们之前学习过冒泡排序#xff0c;冒泡排序尽管很方便#xff0c;但也存在一些局限性… 是非成败转头空青山依旧在几度夕阳红 作者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简单//不能固定取同一位置的元素为pivotint 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 (j1) * size) 0)//比较的的是前后两个元素的地址的数据--计算地址--(char*)basej*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;
}
