成都交易网站建设,企业网站建设 阿里云,做废品回收哪个网站好点,软件工程专业就业方向及前景分析目录
一、概念
二、冒泡排序
2.1 冒泡降序(从大到小排序)
2.2 冒泡升序(从小到大排序)
三、冒泡排序应用
总结 一、概念
冒泡排序核心思想#xff1a;每次比较两个相邻的元素#xff0c;如果它们不符合排序规则#xff08;升序或降序#xff09;则把它们交换过来。…目录
一、概念
二、冒泡排序
2.1 冒泡降序(从大到小排序)
2.2 冒泡升序(从小到大排序)
三、冒泡排序应用
总结 一、概念
冒泡排序核心思想每次比较两个相邻的元素如果它们不符合排序规则升序或降序则把它们交换过来。
二、冒泡排序
2.1 冒泡降序(从大到小排序)
冒泡降序每次比较相邻的两个数如果后面的数比前面的数大则交换这两个数的位置。
假设将 12 18 76 35 99 这 5 个数进行从大到小的排序即越小的越靠后。 如上图所示从左往右逐列看5 个数总共需要遍历 4 次即 n - 1 次而每列从上往下逐行看每遍历一次总共需要排序 n - i 次i 代表遍历的次数。 1. 首先看第一列 1.1 第一行比较第 1 位和第 2 位的大小发现 12 比 18 要小因为是降序所以需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 12 76 35 99 1.2 第二行比较第 2 位和第 3 位的大小发现 12 比 76 要小因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 76 12 35 99 1.3 第三行比较第 3 位和第 4 位的大小发现 12 比 35 要小因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 76 35 12 99 1.4 第三行比较第 4 位和第 5 位的大小发现 12 比 99 要小因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 76 35 99 12 遍历第一次并经过 4 次排序后5 个数中最小的一个 12 已经归位到队列的最后一位了即第 5 位。 2. 再看第二列 2.1 第一行比较第 1 位和第 2 位的大小发现 18 比 76 要小因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 76 18 35 99 12 2.2 第二行比较第 2 位和第 3 位的大小发现 18 比 35 要小因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 76 35 18 99 12 2.3 第三行比较第 3 位和第 4 位的大小发现 18 比 99 要小因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 76 35 99 18 12 遍历第二次并经过 3 次排序后5 个数中倒数第二小的一个 18 已经归位到队列的倒数第二位了即第 4 位。 3. 再看第三列 2.1 第一行比较第 1 位和第 2 位的大小发现 76 比 35 要大则不需要交换这两个数的位置。并且这 5 个数的顺序仍然是 76 35 99 18 12 2.2 第二行比较第 2 位和第 3 位的大小发现 35 比 99 要小因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 76 99 35 18 12 遍历第三次并经过 2 次排序后5 个数中倒数第三小的一个 35 已经归位到队列的倒数第三位了即第 3 位。 3. 最后看第四列 2.1 第一行比较第 1 位和第 2 位的大小发现 76 比 99 要小因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 99 76 35 18 12 遍历第四次并经过 1 次排序后5 个数中倒数第四小的一个 76 已经归位到队列的倒数第四位了即第 2 位。 最后总结一下如果有 n 个数进行排序只需将 n-1 个数归位也就是说要进行 n-1 次操作。而 “每一次” 都需要从第 1 位开始进行相邻两个数的比较将较小的一个数放在后面比较完毕后向后移一位继续比较下面两个相邻数的大小重复此步骤直到最后一个尚未归位的数已经归位的数则无需再进行比较。
冒泡降序例程1(推荐)
#include stdio.hvoid main()
{int arr[5];int n;int tmp;scanf(%d, n); //输入一个数n表示接下来有n个数for (int i 0; i n; i) //循环读入n个数到数组arr中scanf(%d, arr[i]);//冒泡降序的核心代码for (int i 1; i n - 1; i) { //n个数排序只需进行 n-1 次(i从1开始因此i需要包含 n-1)for (int j 0; j n - i; j) { //i从1开始则j从第1位(数组0下标)开始与后面一个数比较直到最后一个尚未归位的数(已归位的数无需再比较因此只需排序 n-i 次)if (arr[j] arr[j1]) { //相邻两个数比较大小并交换tmp arr[j];arr[j] arr[j1];arr[j1] tmp;}}}//输出结果for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);
}
冒泡降序例程2
#include stdio.hvoid main()
{int arr[5];int n;int tmp;scanf(%d, n); //输入一个数n表示接下来有n个数for (int i 0; i n; i) //循环读入n个数到数组arr中scanf(%d, arr[i]);//冒泡降序的核心代码for (int i 0; i n - 1; i) { //n个数排序只需进行 n-1 次(i从0开始因此i不能包含 n-1)for (int j 1; j n - i; j) { //i从0开始则j从第2位(即数组1下标)开始与前面一个数比较直到最后一个尚未归位的数(已归位的数无需再比较因此只需排序 n-i 次)if (arr[j-1] arr[j]) { //相邻两个数比较大小并交换tmp arr[j-1];arr[j-1] arr[j];arr[j] tmp;}}}//输出结果for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);
}
冒泡降序例程3
#include stdio.hvoid main()
{int arr[5];int n;int tmp;scanf(%d, n); //输入一个数n表示接下来有n个数for (int i 0; i n; i) //循环读入n个数到数组arr中scanf(%d, arr[i]);//冒泡降序的核心代码for (int i 0; i n - 1; i) { //n个数排序只需进行 n-1 次 (i从0开始因此i不能包含 n-1)for (int j 0; j n - i - 1; j) { //从第1位(数组0下标)开始与后面一个数比较直到最后一个尚未归位的数(已归位的数无需再比较然而i和j都是从0开始因此只需排序 n-i-1 次)if (arr[j] arr[j1]) { //相邻两个数比较大小并交换tmp arr[j];arr[j] arr[j1];arr[j1] tmp;}}}//输出结果for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);
}
2.2 冒泡升序(从小到大排序)
冒泡升序每次比较相邻的两个数如果后面的数比前面的数小则交换这两个数的位置。
假设将 99 35 18 76 12 这 5 个数进行从小到大的排序即越大的越靠后。 如上图所示从左往右逐列看5 个数总共需要遍历 4 次即 n - 1 次而每列从上往下逐行看每遍历一次总共需要排序 n - i 次i 代表遍历的次数。 1. 首先看第一列 1.1 第一行比较第 1 位和第 2 位的大小发现 99 比 35 要大因为是升序所以需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 99 18 76 12 1.2 第二行比较第 2 位和第 3 位的大小发现 99 比 18 要大因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 18 99 76 12 1.3 第三行比较第 3 位和第 4 位的大小发现 99 比 76 要大因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 18 76 99 12 1.4 第三行比较第 4 位和第 5 位的大小发现 99 比 12 要大因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 18 76 12 99 遍历第一次并经过 4 次排序后5 个数中最大的一个 99 已经归位到队列的最后一位了即第 5 位。 2. 再看第二列 2.1 第一行比较第 1 位和第 2 位的大小发现 35 比 18 要大因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 35 76 12 99 2.2 第二行比较第 2 位和第 3 位的大小发现 35 比 76 要小则不需要交换这两个数的位置。并且这 5 个数的顺序仍然是 18 35 76 12 99 2.3 第三行比较第 3 位和第 4 位的大小发现 76 比 12 要大因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 35 12 76 99 遍历第二次并经过 3 次排序后5 个数中第二大的一个 76 已经归位到队列的倒数第二位了即第 4 位。 3. 再看第三列 2.1 第一行比较第 1 位和第 2 位的大小发现 18 比 35 要小则不需要交换这两个数的位置。并且这 5 个数的顺序仍然是 18 35 12 76 99 2.2 第二行比较第 2 位和第 3 位的大小发现 35 比 12 要大因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 12 35 76 99 遍历第三次并经过 2 次排序后5 个数中第三大的一个 35 已经归位到队列的倒数第三位了即第 3 位。 3. 最后看第四列 2.1 第一行比较第 1 位和第 2 位的大小发现 18 比 12 要大因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 12 18 35 76 99 遍历第四次并经过 1 次排序后5 个数中第四大的一个 18 已经归位到队列的倒数第四位了即第 2 位。 最后总结一下如果有 n 个数进行排序只需将 n-1 个数归位也就是说要进行 n-1 次操作。而 “每一次” 都需要从第 1 位开始进行相邻两个数的比较将较大的一个数放在后面比较完毕后向后移一位继续比较下面两个相邻数的大小重复此步骤直到最后一个尚未归位的数已经归位的数则无需再进行比较。
冒泡升序例程1(推荐)
#include stdio.hvoid main()
{int arr[5];int n;int tmp;scanf(%d, n); //输入一个数n表示接下来有n个数for (int i 0; i n; i) //循环读入n个数到数组arr中scanf(%d, arr[i]);//冒泡降序的核心代码for (int i 1; i n - 1; i)) { //n个数排序只需进行 n-1 次(i从1开始因此i需要包含 n-1)for (int j 0; j n - i; j) { //i从1开始则j从第1位(数组0下标)开始与后面一个数比较直到最后一个尚未归位的数(已归位的数无需再比较因此只需排序 n-i 次)if (arr[j] arr[j1]) { //相邻两个数比较大小并交换tmp arr[j];arr[j] arr[j1];arr[j1] tmp;}}}//输出结果for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);
}
冒泡升序例程2
#include stdio.hvoid main()
{int arr[5];int n;int tmp;scanf(%d, n); //输入一个数n表示接下来有n个数for (int i 0; i n; i) //循环读入n个数到数组arr中scanf(%d, arr[i]);//冒泡降序的核心代码for (int i 0; i n - 1; i) { //n个数排序只需进行 n-1 次(i从0开始因此i不能包含 n-1)for (int j 1; j n - i; j) { //i从0开始则j从第2位(即数组1下标)开始与前面一个数比较直到最后一个尚未归位的数(已归位的数无需再比较因此只需排序 n-i 次)if (arr[j-1] arr[j]) { //相邻两个数比较大小并交换tmp arr[j-1];arr[j-1] arr[j];arr[j] tmp;}}}//输出结果for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);
}
冒泡升序例程3
#include stdio.hvoid main()
{int arr[5];int n;int tmp;scanf(%d, n); //输入一个数n表示接下来有n个数for (int i 0; i n; i) //循环读入n个数到数组arr中scanf(%d, arr[i]);//冒泡降序的核心代码for (int i 0; i n - 1; i) { //n个数排序只需进行 n-1 次 (i从0开始因此i不能包含 n-1)for (int j 0; j n - i - 1; j) { //从第1位(数组0下标)开始与后面一个数比较直到最后一个尚未归位的数(已归位的数无需再比较然而i和j都是从0开始因此只需排序 n-i-1 次)if (arr[j] arr[j1]) { //相邻两个数比较大小并交换tmp arr[j];arr[j] arr[j1];arr[j1] tmp;}}}//输出结果for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);
}
三、冒泡排序应用
假设一个班有 5 个学生需要将这 5 个学生期末考试的分数从高到低排序并且输出对应的学生姓名和性别。大家可以思考一下该如何实现
根据 2.1 冒泡降序原理在此我们只需要声明一个结构体其成员包含学生的姓名、性别和分数假设满分为 100并分数只有整数。下面是实际的例子。
#include stdio.hstruct student {char name[24];char sex[8];int score;
};void main()
{struct student stu[5];struct student tmp;int n;scanf(%d, n); //输入班级总人数for (int i 0; i n; i) //循环读入学生总数到数组stu中scanf(%s %s %d, stu[i].name, stu[i].sex, stu[i].score);//开始对学生进行分数排序for (int i 1; i n - 1; i) {for (int j 0; j n - i; j) {if (stu[j].score stu[j1].score) { //比较相邻的两个数分数高的排前面tmp stu[j];stu[j] stu[j1];stu[j1] tmp;}}}//输出结果for (int i 0; i n; i)printf(%s %s %d, stu[i].name, stu[i].sex, stu[i].score);printf(\n);
}
可以输入以下数据进行验证 5 李文 男 80 韩飞 男 50 晓晓 女 86 胡峰 男 78 陈肖 女 66 运行结果是 晓晓 女 86 李文 男 80 胡峰 男 78 陈肖 女 66 韩飞 男 50 总结
1. 冒泡降序每次比较相邻的两个数如果后面的数比前面的数大则交换这两个数的位置
2. 冒泡升序每次比较相邻的两个数如果后面的数比前面的数小则交换这两个数的位置
3. 从例程代码来看可知冒泡排序有很多种方法但是万变不离其宗都是围绕 “如果有 n 个数进行排序则需遍历 n-1 次而 “每一次” 需要排序 n-i 次并且都是从第 1 位开始进行相邻两个数的比较将较小或较大的一个数放在后面如此重复直到最后一个尚未归位的数” 展开。
4. “冒泡降序” 与 “冒泡升序” 例程代码的唯一差异是相邻的两个数较小或较大的放在后面。例如if (arr[j] arr[j1]) 或 if (arr[j] arr[j1])
5. 冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是 O()。这是一个非常高的时间复杂度。正如 Donald E. Knuth 所说“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外似乎没有什么值得推荐的。”
那还有没有更好的排序算法呢有请看下章节——快速排序。
