关注+星标公众号，不错过精彩内容
来源 | CSDN
编排 | strongerHuang
软件排序算法中，冒泡排序是最经典的一个，很多大学教程也都是用它作为案例。
你知道冒泡排序的时间与空间复杂度吗？
概述
基本步骤
1.外循环是遍历每个元素，每次都放置好一个元素；
//打印数组元素void print_array(int *array, int length){int index = 0;printf("array:\n");for(; index < length; index++){printf(" %d,", *(array+index));}printf("\n\n");}void bubbleSort(int array[], int length){int i, j, tmp;if (1 >= length) return;// 判断参数条件for (i = length-1; i > 0; i--){//外循环，循环每个元素for (j = 0; j < i; j++){ // 内循环，if (array[j] > array[j+1]){// 交换相邻的两个元素tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;}}}}int main(void){int array[12] = {1,11,12,4,2,6,9,0,3,7,8,2};print_array(array, 12);bubbleSort(array, 12);print_array(array, 12);return 0;}
时间复杂度
1.这个时间复杂度还是很好计算的：外循环和内循环以及判断和交换元素的时间开销；
最优的时间复杂度为：O( n^2 ) ；有的说 O(n)，下面会分析这种情况；
最差的时间复杂度为：O( n^2 )；
平均的时间复杂度为：O( n^2 )；
空间复杂度
空间复杂度就是在交换元素时那个临时变量所占的内存空间；
最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0；
最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；
平均的空间复杂度为：O(1)；
最优时间复杂度 n
void bubbleSort(int array[], int length){int i, j, tmp;int flag = 1;if (1 >= length) return;for (i = length-1; i > 0; i--, flag = 1){for (j = 0; j < i; j++){if (array[j] > array[j+1]){tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;flag = 0;}}if (flag) break;}}
1、 a = a + b；b = a - b；a = a - b； 2、 a = a * b； b = a / b；a = a / b； 3、 a = a ^ b； b = a ^ b；a = a ^ b；
参考来源：
https://blog.csdn.net/p1279030826/article/details/99072021
后台回复『软件算法』『嵌入式软件基础知识』阅读更多相关文章。
点击“阅读原文”查看更多分享，欢迎点分享、收藏、点赞、在看。
