博客的开篇我们来介绍一个基础算法——冒泡排序它的作用是将未升序数组排成升序。一、冒泡排序让数组有序的基本算法冒泡排序的核心思路是两两相邻比较较大的元素向后移动。每一轮都能排好至少一个数第一轮会把最大的元素放到数组最后面因此最多需要sz - 1轮就能完成排序。void bubble_sort(int* arr, int sz) { //思路两两相邻比较较大的后移每一轮都能排好至少一个数首轮让最大的元素到最后面 //因此最多 sz - 1 轮就能排好 for (int i 0; i sz - 1; i) { for (int j 0; j sz - 1 - i; j)//在最大轮数的基础上减去 i因为轮了 i 轮会排好至少 i 个 { //逻辑如果左边比右边大就交换 //传了地址过来解引用指针就得到相应元素了 if (*(arr j) *(arr j 1)) { int temp *(arr j);//保存左边的大值 *(arr j) *(arr j 1);//把右边小值赋给左边 *(arr j 1) temp;//再把原大值赋给右边完成升序 } } } }运行结果如下图所示二、冒泡排序的优化用 flag 提前结束循环上面的程序可以顺利完成排序但我们能否进一步优化程序、节省运行时间呢例如数组可能已经排好了程序却仍然继续循环造成资源浪费。答案是肯定的我们可以借助一个flag 标记。借助flag 值的变化可以判断数组是否已经完成排序如果某一轮没有发生任何交换说明数组已经有序可直接return结束排序函数。bool flag 1;//假设数组已经有序 for (int i 0; i sz - 1 flag; i) { flag 0;//每轮开始时假设已有序 for (int j 0; j sz - 1 - i; j) { if (*(arr j) *(arr j 1)) { int temp *(arr j); *(arr j) *(arr j 1); *(arr j 1) temp; flag 1;//发生交换说明尚未完全有序 } } }优化效果示意图如下三、认识二级指针先来回顾一级指针例如int a 10; int* pa a;pa左侧的*表示pa是一个指针变量*左边的int表示指针指向的内容是int类型此时pa中存放的是整型变量a的地址。而二级指针存放的是一级指针变量的地址例如int** ppa pa;ppa左边的第一个*表示ppa是一个指针变量而*左边的int*则表示ppa指向的内容是int*类型。对于解引用**ppa等价于*pa也等价于a。也就是说对**ppa或*pa操作相当于对a本身操作。四、二级指针的用途用指针数组模拟二维数组二级指针有一个重要用途——通过指针数组模拟二维数组。所谓指针数组顾名思义就是存放指针的数组即数组元素类型为指针类型。具体逻辑是二维数组的每一行都是一维数组而指针可以通过数组名即首元素地址访问该数组。int* arr[3] { arr1, arr2, arr3 };此时arr[0]就相当于得到了arr1首元素的地址。五、总结本文从冒泡排序的相邻比较思想出发介绍了它的完整实现以及flag 提前退出优化随后由一级指针过渡到二级指针说明了二级指针的含义、解引用规则以及它借助指针数组模拟二维数组的典型用途。掌握这两块内容有助于进一步理解 C 语言中的排序算法与多级指针机制。
