前言
常见的排序算法有七种。
本篇文章将会详细介绍冒泡排序的实现。
一、冒泡排序的思想
以升序为例，冒泡排序本质上就是不断两两比较，找出较大者，让其移动到右侧，然后再将其与下一个值两两比较，重复以上步骤，让它像一个泡泡一样，移动到末尾。这样就能够排好最大值的位置，然后从头再来一遍，找出第二大的，也让它像个泡泡一样，移动到倒数第二个位置。每次遍历都能够排好一个数的位置，最终就能够排好整个顺序。
二、代码实现
1.完整代码
#include<stdio.h> // 冒泡排序--升序 void BubbleSort(int* arr, int size) { // 最外层循环，用来控制循环次数，每次排好一个数据 for (int i = 0; i < size - 1; ++i) { // 内层循环，用于单次遍历数组，每在末尾排好一个数据则不需要再次遍历到末尾 for (int j = 0; j < size - 1 - i; ++j) { // 如果左边的数据比右边的数据大 if (arr[j] > arr[j + 1]) { // 使用异或符号来 交换 这两个值 arr[j] = arr[j] ^ arr[j + 1]; arr[j + 1] = arr[j] ^ arr[j + 1]; arr[j] = arr[j] ^ arr[j + 1]; } // 此时保证右侧数据比左侧大 } // 保证这一次循环结束后使当前最大值在数组末尾 } // 保证循环 数组长度-1 次后排好所有的数据顺序 } // 主函数 int main() { // 手搓的一个无序数组 int arr[] = { 684,913,621,333,746,249,159,428,764,349,587,616,235,844 }; // 数组长度 int len = sizeof(arr) / sizeof(arr[0]); // 调用冒泡排序--升序 BubbleSort(arr, len); // 循环打印数组内容 for (int i = 0; i < len; ++i) { printf("%d ", arr[i]); } // 换行 printf("\n"); return 0; }
2.结果演示
3.要点分析
冒泡排序非常简单，只需要嵌套两次循环即可解决。需要注意的是，每遍历一次数组，就能将无序部分的最大值移动到数组末尾，我们要 排序/交换 的部分是无序部分，所以每遍历一次数组，数组的有序部分就会增加，无序部分就会减少，单次遍历的条件就要根据次数来改变。
三、优化
1.优化分析
上面的代码不管什么情况都需要遍历 数组长度-1 次数组，如果数组是较为有序的数组，只需要短短几次就能够排好序的那种数组，上面的代码就会在即使数组已经有序的情况下，冒泡排序仍然要去遍历那么多次，比较麻烦，所以我们在每次的单次遍历后判断一下数组是否有序，有序的话直接终止循环即可。
2.优化代码
#include<stdio.h> #include<stdbool.h> // 冒泡排序--升序 void BubbleSort(int* arr, int size) { // 最外层循环，用来控制循环次数，每次排好一个数据 for (int i = 0; i < size - 1; ++i) { // 用布尔值假设数组有序 bool k = true; // 内层循环，用于单次遍历数组，每在末尾排好一个数据则不需要再次遍历到末尾 for (int j = 0; j < size - 1 - i; ++j) { // 如果左边的数据比右边的数据大 if (arr[j] > arr[j + 1]) { // 使用异或符号来 交换 这两个值 arr[j] = arr[j] ^ arr[j + 1]; arr[j + 1] = arr[j] ^ arr[j + 1]; arr[j] = arr[j] ^ arr[j + 1]; // 只要在单次遍历中发生了交换，则说明还不能判断数组真的有序，k改为假有序 k = false; } // 此时保证右侧数据比左侧大 // 如果k值为真，说明本次遍历中没有发生交换，说明数组真的有序了 if (k == true) // 退出循环 break; } // 保证这一次循环结束后使当前最大值在数组末尾 } // 保证循环 数组长度-1 次后排好所有的数据顺序 } // 主函数 int main() { // 手搓的一个无序数组 int arr[] = { 684,913,621,333,746,249,159,428,764,349,587,616,235,844 }; // 数组长度 int len = sizeof(arr) / sizeof(arr[0]); // 调用冒泡排序--升序 BubbleSort(arr, len); // 循环打印数组内容 for (int i = 0; i < len; ++i) { printf("%d ", arr[i]); } // 换行 printf("\n"); return 0; }
3.要点分析
这个优化只需要记录单次遍历后数组有没有发生交换，如果发生了交换，我们就猜不到数组是否有序，需要以无序来看待，进行下次遍历。如果没有发生交换，说明数组任意两两元素都满足条件，则数组已经有序，即可直接退出排序。
四、复杂度分析
1.时间复杂度
在最坏情况下，假设数组长度为 n ，那么我们排好一个数组需要 n - 1 次遍历。而每一次排序都会使无序部分减少 1 ，所以第一次遍历需要判断 n - 1 次，第二次遍历需要判断 n - 2 次。。。。最后一次，第 n - 1 次遍历需要判断 1 次，通过数学计算，可算出需要判断 (n(n - 1)) / 2 次。所以时间复杂度为 O(n2) 。
2.空间复杂度
冒泡排序并没有额外开辟数组空间。所以空间复杂度为 O(1) 。
总结
冒泡排序属于非常简单的排序，也是大多数人第一次接触到的排序，虽然排序的效率不高，但是对了解排序思想还是有帮助的。
