做网站的天津,广州海珠区租房子一般多少钱,长春市做网站,大数据营销案例分析前言 #x1f493;作者简介#xff1a; 加油#xff0c;旭杏#xff0c;目前大二#xff0c;正在学习C#xff0c;数据结构等#x1f440; #x1f493;作者主页#xff1a;加油#xff0c;旭杏的主页#x1f440; ⏩本文收录在#xff1a;再识C进阶的专栏#x1…前言 作者简介 加油旭杏目前大二正在学习C数据结构等 作者主页加油旭杏的主页 ⏩本文收录在再识C进阶的专栏 代码仓库旭日东升 1 欢迎大家点赞 收藏 ⭐ 加关注哦 学习目标 在上一篇博客中我们学习了回调函数以及怎么使用qsort函数去排序那么在这一篇博客中我们来更加详细地学习qsort函数内部是怎么进行排序的以及想要用冒泡排序去模拟实现一下可以排序任意类型数据最后我们要进行做题来巩固一下所学的知识点。 学习内容
通过上面的学习目标我们可以列出要学习的内容
学习qsort函数内部是怎么进行排序的用冒泡排序去模拟实现一下可以排序任意类型数据做题巩固一下知识点指针的笔试题 一、学习qsort函数内部是怎么进行排序的 在学习qsort函数内部是如何实现的我们需要在认真地将qsort函数的形参进行一遍分析因为其形参的个数实在是太多了这就和数学公式一样要记住每一个字母表示的含义这样我们才能用的对。
1.1 qsort函数中的四个参数的意思 这时我们需要打开cplusplus的网站进行搜索qsort函数如下图所示接下来一一分析 1.1.1 void* base 首先映入我们眼帘的是其类型void* 。 这个类型还是很重要的void* 类型要记住一些要点 void* 创建的变量可以接收任意类型的指针变量void* 创建的变量不能进行加减整数的运算因为不知道类型无法确定加减整数后指针移动几位字节。 之后这个参数存放的是待排序数组的第一个元素的地址。 1.1.2 size_t num 这个形参的类型可能读者也没有见过简单地理解其就是无符号整形。我们在VS转到定义时可以看到是用 typedef 定义的如下图 这个参数存放的是待排序数组的元素个数。 1.1.3 size_t size 因为qsort函数可以排序任意类型的数据但是任意类型数据的大小是不同我们需要将我们所要排序的数据类型传过去让qsort函数知道数据的大小好进行排序。 这个参数存放的是待排序数组中一个元素的大小。 1.1.4 int (*comper) (const void*, const void*) 这个参数就是我们上一篇博客所学习的函数指针qsort函数需要我们自己写一个比较函数因为qsort函数默认是升序排序的这个要知道不然容易迷。 这个比较函数所返回的值与0进行比较会产生不同的结果如果大于0即成立交换两个数如果小于0即不成立不交换。如下图如果图里的情况看不懂我们可以看下面的代码 int compare(const void* e1, const void* e2)
{int* p1 e1;int* p2 e2;if (*p1 *p2){return 1;}else if (*p1 *p2){return 0;}else if (*p1 *p2){return -1;}
} 这个参数的含义是函数指针——cmp指向了一个函数这个函数是用来比较两个元素的。 1.2 引出qsort函数内部算法的思想 qsort函数内部是用快速算法进行实现因为我的算法博客也更新到这一篇我就直接在这一篇上写了快速算法肯定不同于我们之前所学的归并排序和堆排序我们先用一个简单的题目引出类似于快速排序算法的思路。
1.2.1 将数组分为两个区域的问题 在讲述荷兰国旗问题之前我们先来看一个更简单的题来帮助我们进入荷兰国旗问题的思路。 题目 给定一个数组arr和一个数num请把数组中小于等于num的数放在数组的左边把数组中大于num的数放在数组的右边无需排序。要求空间复杂度为O(1)时间复杂度为O(N) 思路 我们可以将数组分为两个区一个是num区一个是num区。我们可以先将num区放在数组首元素的前一个位置将指针指向数组中第一个元素与num进行比较。 如果第一个元素比num小于或者等于num区往前加一将指针加一继续与num进行比较 如果指针指向的元素比num大num区不动指针向后移动直到比num小停止将这个数与num区的后面一个数进行交换即可。循环整个过程直到指针指向空。 代码 void swap(int arr[], int a, int b)
{int temp arr[a];arr[a] arr[b];arr[b] temp;
}void prather(int* arr, int left, int right, int num)
{int less left - 1;int index left;while (index right){if (arr[index] num){swap(arr, less, index);}else{index;}}
}int main()
{int arr[10] { 2,3,6,3,4,7,9,0,2,3 };int left 0;int right 9;int num 3;prather(arr, left, right, num);for (int i 0; i 10; i){printf(%d , arr[i]);}return 0;
} 这个问题的关键主要就是将数组分为两个部分而荷兰国旗问题是将数组分为三个部分是属于其的进阶。 将数组分为两个区域我们用了一个作用界限而将数组分为三个区域是否需要两个作用界限呢
1.2.2 荷兰国旗问题 题目 牛牛今天带来了一排气球气球有n个然后每一个气球里面都包含一个数字牛牛是一个善于思考的人,于是他就想到了一个问题牛牛随便给你一个值K这个值在这些气球中不一定存在聪明的你需要把气球中包含的数字是小于K的放到这排气球的左边大于K的放到气球的右边等于K的放到这排气球的中间最终返回一个整数数组其中只有两个值分别是气球中包含的数字等于K的部分的左右两个下标值,如果气球中没有K这个数字就输出-1-1。 思路 这个就相当于将一个数组通过所给的数字分为三个区一个是num区一个是num区一个是num区。我们需要将num区和num区同时卡住这样剩下就是num区的内容于是思路就有了。 定义两个指针变量一个指针变量 less 指向数组首元素的前一个位置一个指针变量 more 指向数组最后一个元素的后一个位置用一个索引index指向数组的首元素。 如果index指向的元素小于num则less交换less的元素与index指向的元素然后index 如果index指向的数组元素等于num则index 如果index指向的元素大于num则交换index与more--的元素index不。 代码 #include stdio.h
#include malloc.h
void swap(int arr[], int a, int b) {int temp arr[a];arr[a] arr[b];arr[b] temp;
}void Nether(int arr[], int left, int right, int k) {int less left - 1;int more right 1;int index left;while (index more) {if (arr[index] k)swap(arr, less, index);else if (arr[index] k)swap(arr, --more, index);elseindex;}if (less 1 more - 1) {int* ret (int*)malloc(sizeof(int) * 2);ret[0] less 1;ret[1] more - 1;for (int i 0; i 2; i) {printf(%d , ret[i]);}}else{for(int i 0; i 2; i){printf(-1 );}}
}int main() {int n 0, k 0;int arr[100010];scanf(%d %d, n, k);for (int i 0; i n; i) {scanf(%d , arr[i]);}int left 0;int right n - 1;Nether(arr, left, right, k);return 0;
} 1.3 qsort函数内部是怎么实现的 在 1.2 中学习了荷兰国旗问题的思路其实qsort函数内部算法的实现是快速排序而快速排序在发展中有三个阶段分别是快速排序 1.0快速排序 2.0 和快速排序 3.0。
1.3.1 快速排序 1.0 在这个版本下快速排序的思路与荷兰国旗问题的思路基本相同不过不一样的地方是荷兰国旗问题比较的是随机给的数字而快速排序比较的一定是数组中的数字。 不买关子了快速排序的算法思路是将数组最后一个元素作为比较数将数组分为比较数区比较数区这样就将最后一个元素排好序了其数组下标记作p将数组分为左右两个部分利用递归再比较p-1和p1的元素将他们排好序递归下去就可以将数组中的元素排好序。 但这个思路有一个比较明显的不足不足之处在于数组中有连续相等的数字但也会损失一下常数时间所以在快速排序 2.0 版本下将数组分为三个区比较数区比较数区比较数区。这样就能节省一些常数时间。
1.3.2 快速排序 2.0 在快速排序 1.0 中已经提出了快速排序 2.0 的思路了也就比快速排序 1.0优化了一下常数时间。不过这两种方式都不是最优的如果我们考虑最差情况在最差情况中两者的时间复杂度接近于O(N*N)与冒泡排序没什么两样为什么呢 原因如下因为如果数组元素中最后一个数排序过后不在中间的位置那么时间复杂度就会增加如果说如果每一次要排序元素在正中间的话是最好的情况不过不太可能所以在这两个版本下时间复杂度都会增加。 1.3.3 快速排序 3.0 快速排序 3.0中我们不同于以往将数组的最后一个元素进行比较而是将随机匹配一个数组元素进行比较根据概论发现如果数组有N个元素那么每一个元素被选中的概率是1/N。经过数学计算后会发现这个排序的时间复杂度为O(N*logN)达到了我们的目的。
1.3.4 快速排序的代码
#include stdlib.h
#include string.h
#include malloc.h
void swap(int arr[], int a, int b) //交换函数
{int temp arr[a];arr[a] arr[b];arr[b] temp;
}
int* partion(int arr[], int left, int right); //函数声明不要忘记
void quicksort(int arr[], int left, int right)
{if (left right) //递归终止条件{//先随机选一个元素与数组中最后一个元素进行交换然后进行partionint num rand() % (right - left 1); //产生0~sz的任意数字swap(arr, left num, right);int* ans (int*)malloc(sizeof(int) * 2);ans partion(arr, left, right);quicksort(arr, left, ans[0] - 1); //arr[num]区quicksort(arr, ans[1] 1, right);//arr[num]区}
}
int* partion(int arr[], int left, int right)
{int less left - 1;int more right 1;int index left;int* ret (int*)malloc(sizeof(int) * 2);while (index more){if (arr[index] arr[right]){swap(arr, less, index);}else if (arr[index] arr[right]){swap(arr, --more, index);}elseindex;}ret[0] less 1;ret[1] more - 1;return ret;
}
二、用冒泡排序去模拟实现一下可以排序任意类型数据 在模拟实现冒泡排序前先来熟悉一下冒泡排序的思想记住知识点要进行大量的重复记忆这样才能会用。
2.1 冒泡排序的思路 冒泡排序冒泡排序就是让最大的数像重物一样沉到底部两两进行比较然后进行交换位置这就是基本思路。 第一次将最大的数字沉到底部第二次将次大的数字沉到底部第三次……是一个循环将最大数从大到小依次沉到底部所以我们来实现一下代码
void bubble_sort(int arr[], int sz)
{for (int i 0; i sz - 1; i){for (int j 0; j sz - 1 - i; j){if (arr[j] arr[j 1]){swap(arr, j, j 1);}}}
}
2.2 模拟实现任何类型的冒泡排序 而单一的冒泡排序用法实在是太少了在学习了qsort函数之后我们就是能将冒泡排序也改造为能够排任意类型的数据呢那么接下来我们就要朝着这个方向进行
2.2.1 实现任何类型的冒泡排序的主体
2.2.1.1 参数部分 因为不同类型的数据进行比较时他们的比较方法是不同如果我们想要比较不同类型的数据还要写不同的比较方法这样函数就变多了这样就不是一个函数了所以我们将这个比较方法抽离出来让用户自己写。因为不同类型的数据的大小不同所以用户要传入要排序数据的大小还要传入要排序数据的多少。因此此函数与qsort函数的参数类似。 void bubble_sort(void* base, size_t num, size_t size, int (*cmp)(const void*, const void*)) 2.2.1.2 主体部分 在参数部分中有一个函数指针函数主体的大体部分是一样的我们只需要改变一下比较条件类似于qsort函数的条件默认是一个是升序排序。
void bubble_sort(void* base, size_t num, size_t size, int (*cmp)(const void*, const void*))
{for (int i 0; i num - 1; i){for (int j 0; j num - 1 - i; j){if (cmp((char* )base j * size, (char*)base (j 1) * size) 0){swap((char*)base j * size, (char*)base (j 1) * size, size);}}}
}
2.2.2 实现任何类型的冒泡排序的交换部分 不同数据类型的数据大小也是不一样的因为数据类型大小的基本单位是字节所以我们用char*指针来接收char类型的大小为1个字节。我们不能将这个数据进行交换我们只能一个字节一个字节的交换。
void swap(char* a, char* b, size_t size)
{for (int i 0; i size; i){char temp *a;*a *b;*b temp;a;b;}
}
三、一些有关 sizeof 和 strlen 的题目 这个题目有点多可能会有点费时间但是主要是将括号内的东西理解清楚是什么我们来一一进行
3.1 sizeof 类型
//一维数组
int a[] { 1,2,3,4 }; //答案
printf(%d\n, sizeof(a)); //16
printf(%d\n, sizeof(a 0)); //4/8
printf(%d\n, sizeof(*a)); //4
printf(%d\n, sizeof(a 1)); //4/8
printf(%d\n, sizeof(a[1])); //4
printf(%d\n, sizeof(a)); //4/8
printf(%d\n, sizeof(*a)); //16
printf(%d\n, sizeof(a 1)); //4/8
printf(%d\n, sizeof(a[0])); //4/8
printf(%d\n, sizeof(a[0] 1));//4/8 解析 1. 数组名在一般情况下表示的数组首元素的地址而数组名单独放在sizeof内部数组名表示整个数组计算的是整个数组的大小单位是字节。 2. 数组名未单独出现也没有所以数组名表示的是首元素的地址a 0还是首元素的地址是一个指针大小是4/8个字节。 3. 数组名未单独出现也没有所以数组名表示的是首元素的地址解引用表示数组的首元素大小为4个字节。 4. 与2类似。 5. 表示的是数组中第一个元素其大小为4个字节。 6. 数组名取出的数组的地址还是一个指针大小为4/8个字节。 7. 解引用与取地址可以互相抵消则其表示的是数组计算的是数组的大小为16个字节。 8. 与6类似数组名取出的是数组的地址加1表示跳过一个数组大小指向跳过一个数组的大小的地方。 9. a[0]表示的是取出数组首元素的地址是一个指针大小为4/8个字节。 10. 与9类似还是一个地址大小为4/8个字节。 //字符数组
char arr[] {a,b,c,d,e,f}; //答案
printf(%d\n, sizeof(arr)); //6
printf(%d\n, sizeof(arr 0)); //4/8
printf(%d\n, sizeof(*arr)); //1
printf(%d\n, sizeof(arr[1])); //1
printf(%d\n, sizeof(arr)); //4/8
printf(%d\n, sizeof(arr 1)); //4/8
printf(%d\n, sizeof(arr[0] 1)); //4/8 3.2 strlen 类型
//字符数组
char arr[] {a,b,c,d,e,f}; //答案
printf(%d\n, strlen(arr)); //随机值
printf(%d\n, strlen(arr 0)); //随机值
printf(%d\n, strlen(*arr)); //error
printf(%d\n, strlen(arr[1])); //error
printf(%d\n, strlen(arr)); //随机值
printf(%d\n, strlen(arr 1)); //随机值-6
printf(%d\n, strlen(arr[0] 1)); //随机值-1 解析 1. strlen计算的字符串的长度要有\0的结束标志由于这个字符数组中没有\0的结束标志所以是随机值。 2. 同理也是随机值。 3. *arr表示的是一个字符但在strlen中只能是地址所以strlen认为这是一个非法地址会报错。 4. 与3同理 5. arr尽管取出的是数组的地址但是在数值上与数组首元素的地址是一样所以也是随机值。 6和7与5类似。 3.3 总结
再来复习一下数组名的意义
sizeof(数组名)这里的数组名表示整个数组计算的是整个数组的大小数组名这里的数组名表示整个数组取出的是整个数组的地址除此之外所有的数组名都表示首元素的地址。 学习产出
学习qsort函数内部是怎么进行排序的用冒泡排序去模拟实现一下可以排序任意类型数据做题巩固一下知识点指针的笔试题
