42.【C语言】冒泡排序

目录：

冒泡排序

     *核心思想

     *分析

     *代码

     *优化

15.冒泡排序(bubble sort)

*核心思想：两两相邻的元素进行比较，满足条件则两者交换

*分析

现要求升序排序

输入: 9 8 7 6 5 4 3 2 1 0

输出：0 1 2 3 4 5 6 7 8 9

 下面展示一趟冒泡排序

图中显示：9被一步一步“冒泡”到最右边

可见：N个数字，第一趟冒泡排序需要(N-1)步

下图表示每趟冒泡排序后的结果

由图可知：N个数字，第一趟冒泡排序需要(N-1)步

                  N个数字，第二趟冒泡排序需要(N-2)步

                 N个数字，第三趟冒泡排序需要(N-3)步

                 ……

一共需要(N-1)趟

*代码

由上述分析，需要两个循环来控制趟数(i)和步数(j)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{int n = 0;int arr[100] = { 0 };int tmp = 0;//输入元素printf("输入数组元素个数：");scanf("%d", &n);printf("输入数组元素：");for (int k = 0; k < n; k++){scanf("%d", &arr[k]);}//冒泡排序for (int i = 1; i <= n - 1; i++)//趟数{for (int j = 0; j <=n - i-1 ; j++)//步数{if (arr[j] > arr[j + 1]){tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}}//打印结果for (int q = 0; q < n; q++){printf("%d ", arr[q]);}
}

 

*优化

反思：该代码是否有优化的空间？

对于上方的代码，当有10个元素时，无论元素怎么排列，一共需要9+8+7+6+5+4+3+2+1=(1+9)*9/2=45步

如 输入 9 0 1 2 3 4 5 6 7 8 一趟冒泡排序后就已经完成任务了，但仍然要执行剩下的44次，导致效率降低，而且并没有发生数组元素之间的交换

解决方法：有顺序时取消交换，提前退出循环，输出结果

回想标志寄存器(flag register)的概念：标志寄存器用于存储状态信息，这些状态信息可以影响程序的流程控制

同理可以在程序中创建“标志变量”flag来控制循环

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{int n = 0;int arr[100] = { 0 };int tmp = 0;//输入元素printf("输入数组元素个数：");scanf("%d", &n);printf("输入数组元素：");for (int k = 0; k < n; k++){scanf("%d", &arr[k]);}int flag = 1;//冒泡排序for (int i = 1; i <= n - 1; i++)//趟数{for (int j = 0; j <= n - i - 1; j++)//步数{if (arr[j] > arr[j + 1]){tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;flag = 0;//发生交换flag置0}}if (1 == flag){break;//未发生交换则退出循环}}//打印结果for (int q = 0; q < n; q++){printf("%d ", arr[q]);}
}