【再识C进阶2(下)】详细介绍指针的进阶——利用冒泡排序算法模拟实现qsort函数，以及一下习题和指针笔试题

1.3 qsort函数内部是怎么实现的

       在 1.2 中，学习了荷兰国旗问题的思路，其实qsort函数内部算法的实现是快速排序，而快速排序在发展中，有三个阶段：分别是快速排序 1.0，快速排序 2.0 和快速排序 3.0。

1.3.1 快速排序 1.0

       在这个版本下，快速排序的思路与荷兰国旗问题的思路基本相同，不过不一样的地方是荷兰国旗问题比较的是随机给的数字，而快速排序比较的一定是数组中的数字。

       不买关子了，快速排序的算法思路是：将数组最后一个元素作为比较数，将数组分为：<=比较数区，>比较数区，这样就将最后一个元素排好序了，其数组下标记作p；将数组分为左右两个部分，利用递归再比较p-1和p+1的元素，将他们排好序，递归下去，就可以将数组中的元素排好序。

       但这个思路有一个比较明显的不足，不足之处在于数组中有连续相等的数字，但也会损失一下常数时间，所以在快速排序 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 #include #include 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]区}}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 类型

3.1.1 一维数组

//一维数组int a[] = { 1,2,3,4 };            //答案  printf("%d\n", sizeof(a));        //16  printf("%d\n", sizeof(a + 0));    //4/8printf("%d\n", sizeof(*a));       //4printf("%d\n", sizeof(a + 1));    //4/8printf("%d\n", sizeof(a[1]));     //4printf("%d\n", sizeof(&a));       //4/8printf("%d\n", sizeof(*&a));      //16printf("%d\n", sizeof(&a + 1));   //4/8printf("%d\n", sizeof(&a[0]));    //4/8printf("%d\n", sizeof(&a[0] + 1));//4/8

解析： 

数组名在一般情况下，表示的数组首元素的地址，而数组名单独放在sizeof内部，数组名表示整个数组，计算的是整个数组的大小，单位是字节。

数组名未单独出现，也没有&，所以数组名表示的是首元素的地址，a + 0还是首元素的地址，是一个指针，大小是4/8个字节。

数组名未单独出现，也没有&，所以数组名表示的是首元素的地址，解引用表示数组的首元素，大小为4个字节。

与2类似。

表示的是数组中第一个元素，其大小为4个字节。

&数组名取出的数组的地址，还是一个指针，大小为4/8个字节。

解引用与取地址可以互相抵消，则其表示的是数组，计算的是数组的大小，为16个字节。

与6类似，&数组名取出的是数组的地址，加1表示跳过一个数组大小，指向跳过一个数组的大小的地方。

&a[0]表示的是取出数组首元素的地址，是一个指针，大小为4/8个字节。

与9类似，还是一个地址，大小为4/8个字节。

3.1.2 字符数组 

//字符数组char arr[] = {'a','b','c','d','e','f'};    //答案printf("%d\n", sizeof(arr));               //6printf("%d\n", sizeof(arr + 0));           //4/8printf("%d\n", sizeof(*arr));              //1printf("%d\n", sizeof(arr[1]));            //1printf("%d\n", sizeof(&arr));              //4/8printf("%d\n", sizeof(&arr + 1));          //4/8printf("%d\n", sizeof(&arr[0] + 1));       //4/8

3.1.3 二维数组 

//二维数组int a[3][4] = {0};                    //答案printf("%d\n", sizeof(a));            //48printf("%d\n", sizeof(a[0][0]));      //4printf("%d\n", sizeof(a[0]));         //16printf("%d\n", sizeof(a[0] + 1));     //4/8printf("%d\n", sizeof(*(a[0] + 1)));  //4printf("%d\n", sizeof(a + 1));        //4/8printf("%d\n", sizeof(*(a + 1)));     //16printf("%d\n", sizeof(&a[0] + 1));    //4/8printf("%d\n", sizeof(*(&a[0] + 1))); //16printf("%d\n", sizeof(*a));           //16printf("%d\n", sizeof(a[3]));         //16

解析：

当数组名单独出现在sizeof内部时，数组名表示整个数组，计算的是整个数组的大小，单位是字节；

a[0][0]表示的是这个二维数组的第一行第一列的数组元素，sizeof计算的是类型大小，即数组元素的类型大小，单位是字节；

这里要对二维数组有一个新的认识，就是二维数组是一维数组的数组，其首元素表示的是二维数组的第一行，即一维数组。因此，当二维数组的首元素单独出现在sizeof内部时，表示的是二维数组的一行元素，计算的是一行元素的大小，单位是字节；

如果二维数组的元素不是单独出现，则表示的是这一行首元素的地址，加减一个整数即为地址，因为没有对二维数组元素进行取地址，则这里指针的类型是int* ，当加一时，表示的是这一行元素的第二个元素；

由4可得，对这个地址进行解引用，得到的是一个元素的大小；

数组名没有单独出现，表示的是数组的第一行地址，此时指针类型为数组指针类型，进行加一时，指向的是第二行的地址；

由6可得，指向的是数组第二行的地址，进行解引用时，得到的是第二行元素的大小；

&数组名，取出的是第一行元素的地址，再加一，指向的是第二行地址；

由8可得，对第二行地址进行解引用，得到的是第二行元素的大小；

数组名未单独出现，对其解引用得到的是数组首元素，即第一行元素的大小；

这里并没有越界，因为sizeof只是需要知道，用户传过去的是什么类型的即可，并没有去访问。a[3]与a[0]一样表示的一行元素，即一行元素的大小。

 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));              //errorprintf("%d\n", strlen(arr[1]));            //errorprintf("%d\n", strlen(&arr));              //随机值printf("%d\n", strlen(&arr + 1));          //随机值-6printf("%d\n", strlen(&arr[0] + 1));       //随机值-1

解析：

strlen计算的字符串的长度，要有'\0'的结束标志，由于这个字符数组中没有'\0'的结束标志，所以是随机值。

同理，也是随机值。

*arr表示的是一个字符，但在strlen中，只能是地址，所以strlen认为这是一个非法地址，会报错。

与3同理

&arr尽管取出的是数组的地址，但是在数值上与数组首元素的地址是一样，所以也是随机值。

6和7与5类似。

3.3 总结

再来复习一下数组名的意义：

1. sizeof(数组名)，这里的数组名表示整个数组，计算的是整个数组的大小；
2. &数组名，这里的数组名表示整个数组，取出的是整个数组的地址；
3. 除此之外，所有的数组名都表示首元素的地址。

四、指针的笔试题

       这个题目有点多，在这里小编先挑几条重要进行讲解，之后小编会整理一下所有的笔试题在写一篇博客的。那么，我们来看笔试题：

笔试题一：

题目：

int main(){    int a[4] = { 1,2,3,4 };    int* ptr1 = (int*)(&a + 1);    int* ptr2 = (int*)((int)a + 1);    printf("%x, %x\n", ptr1[-1], *ptr2);    return 0;}

解析：

       第一个是比较简单的，&数组名将数组的整个地址取出，进行加一时，跳过整个数组，看图；第二个就有点难度，因为a表示的是数组首元素的地址，强制类型转换为整形，再加一，只跳过一个字节，而一个整形的大小是4个字节，即这个指针指向的是第一个整形变量中的第二个字节，因此要考虑编译器是小端传输还是大端传输，这是很重要的。

答案：

0x00000004, 0x02000000

笔试题二： 

题目：

int main(){    int a[5][5];    int(*p)[4];    p = a;    printf("%p, %d\n", &p[4][2] - &a[4][2], &p[4][2] - &a[4][2]);    return 0;}

解析：

       p是一个数组指针，将二维数组a的地址赋给p不太合适，但是也能接收，那就可以将p看成一行元素为4个的二维数组，看解析图：

答案：

       大家自己去验证，这里就不算了。

学习产出：

1. 学习qsort函数内部是怎么进行排序的
2. 用冒泡排序去模拟实现一下可以排序任意类型数据
3. 做题巩固一下知识点
4. 指针的笔试题

来源地址：https://blog.csdn.net/2301_77868664/article/details/132850670