【C】初阶数据结构12 -- 冒泡排序
本篇文章主要讲解经典排序算法 -- 冒泡排序。
目录
1 算法思想
2 代码
3 时间复杂度与空间复杂度分析
1） 时间复杂度
2） 空间复杂度
1 算法思想
选择排序是一种经典的交换排序算法。其算法思想也比较简单，主要是比较相邻元素，假设这里是排升序，开始先比较 0 下标元素和 1 下标元素，如果 0 下标比 1 下标元素大，那就交换 0 下标元素和 1 下标元素；然后再比较 1 下标元素和 2 下标元素，如果 1 下标元素比 2 下标元素大，那就交换她们俩；接下来再比较 3 下标元素和 4 下标元素，4 下标元素与 5 下标元素 .... ，直到 n -2 小下标元素和 n - 1 下标元素比较完，第一轮比较就结束了，经过这轮比较之后，那么数组中最大的元素就被移到了下标为 n-1 的位置处，然后依次循环上述过程，依次将第二大，第三大元素...移到 n-2 下标位置，n-3 下标位置...，这样就完成了从小到大的排序。一次冒泡排序的过程如图所示：
可以看到图中第一轮需要排序的总共 10 个元素，第一轮总共进行了 9 次比较；依次类推，当第一轮结束之后，第二轮待排序的元素还有 9 个，所以比较的次数应该为 8 次；第三轮待排序的元素为 8 个，比较次数为 7 次，所以比较的次数 = 数组中元素的个数 - 轮数。在冒泡排序算法中，每次是将待排序元素中最大的元素放到最后面，当数组元素个数为 n 时，应该是将 n - 1 个元素放到最后面，所以轮数 = 数组元素的个数 - 1。
2 代码
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void BubbleSort(int* arr, int n)
{//轮次for (int i = 0; i < n - 1; i++){int exchange = 1;//比较对数for (int j = 0; j < n - 1 - i; j++){if (arr[j] > arr[j + 1]){Swap(&arr[j], &arr[j + 1]);exchange = 0;}}//如果一对也没有交换，就跳出循环if (exchange){break;}}
}解释：在冒泡排序算法的实现过程中，共有两层循环，第一层循环控制比较的轮次，会进行 n-1（n为元素个数） 次，第二层循环控制比较的次数，会执行 n - 1 - i （n为元素个数，i为轮数）次，如果相邻元素前一个元素比后一个元素大的话，就会将他们进行交换。在代码中还进行优化，就是如果在第二次循环中，一次也没有交换的话，就代表剩下的待排序的元素已经有序了。例如对于上面那个例子，在 7 作为最大元素排序完之后，数组中的元素的排放如下图所示：
进行下一轮循环后数组中的元素的排列会变成如下图所示：
再进行下一次循环时，1 2 3 4 5 五个待排序的元素已经有序了，直接跳出循环，完成冒泡排序。
为了实现上述的优化逻辑，在第一层循环里面设置了一个交换的标志位 exchange，刚开始定义 exchange 为1，假设在第二轮循环中进行交换了就将 exchange 变为0，代表交换了，退出第二轮循环之后，如果 exchange 还为 1 就代表一次也没有交换，代表剩下的元素已经有序了，会 break 跳出循环，结束冒泡排序。
测试用例：
int main()
{int arr[] = { 10, 2, 5, 7, 1, 4, 8, 9, 6};int n = sizeof(arr) / sizeof(arr[0]);BubbleSort(arr, n);Print(arr, n);return 0;
}3 时间复杂度与空间复杂度分析
1） 时间复杂度
冒泡排序的时间复杂度很简单，由于有两层循环，每层循环在最坏情况下都会执行 n 次，所以时间复杂度 T(n) = O(n^2)。
2） 空间复杂度
同前几个排序算法相同，冒泡排序算法只用了几个有限的变量，所以空间复杂度 S(n) = O(1)。