做优惠券网站,网络解决方案公司,网站虚拟主机,wordpress 数据迁移目录#xff1a; 冒泡排序 *核心思想 *分析 *代码 *优化 15.冒泡排序(bubble sort)
*核心思想#xff1a;两两相邻的元素进行比较#xff0c;满足条件则两者交换
*分析 现要求升序排序 输入: 9 8 7 6 5 4 3 2 1 0 输出#xff1a;0 1 2 3 4 5 6 7 8 9 下面展示一趟冒泡排… 目录 冒泡排序 *核心思想 *分析 *代码 *优化 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个元素时无论元素怎么排列一共需要987654321(19)*9/245步
如 输入 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]);}
}
