排序算法之冒泡算法
2023-09-14 09:12:44 时间
目录
排序算法介绍
《Hello算法》是GitHub上一个开源书籍,对新手友好,有大量的动态图,很适合算法初学者自主学习入门。而我则是正式学习算法,以这本书为参考,写写笔记,有错误的地方还请指正,下面我会用python和C++实现其中的实例
排序介绍:排序简介 - Hello 算法 (hello-algo.com)
这里有更详细的介绍。
冒泡排序
这是我最开始学习C语言就接触的方法,它是一种最基础的排序算法,非常适合初学者的排序算法。冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,是不会再交换的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。
为什么叫“冒泡”
在水中,越大的泡泡浮力越大,所以最大的泡泡会最先浮到水面。
算法流程
那么在实际过程中,具体做法:从数组最左端开始向右遍历,依次对比相邻元素大小,若 左元素 > 右元素 则将它俩交换,最终可将最大元素移动至数组最右端。完成此次冒泡操作后,数组最大元素已在正确位置,接下来只需排序剩余 n−1 个元素。
算法实现
下面将以python与C++为例
python
def bubble_sort_with_flag(nums):
n = len(nums)
# 外循环:待排序元素数量为 n-1, n-2, ..., 1
for i in range(n - 1, -1, -1):
flag = False # 初始化标志位
# 内循环:冒泡操作
for j in range(i):
if nums[j] > nums[j + 1]:
# 交换 nums[j] 与 nums[j + 1]
nums[j], nums[j + 1] = nums[j + 1], nums[j]
flag = True # 记录交换元素
if not flag:
break # 此轮冒泡未交换任何元素,直接跳出
C++
void bubbleSortWithFlag(vector<int>& nums) {
// 外循环:待排序元素数量为 n-1, n-2, ..., 1
for (int i = nums.size() - 1; i > 0; i--) {
bool flag = false; // 初始化标志位
// 内循环:冒泡操作
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// 交换 nums[j] 与 nums[j + 1]
// 这里使用了 std::swap() 函数
swap(nums[j], nums[j + 1]);
flag = true; // 记录交换元素
}
}
if (!flag) break; // 此轮冒泡未交换任何元素,直接跳出
}
}
在这里,引进了一个flag变量,并不是所有的排序需要全部进行一次遍历,若在某轮"冒泡"中未执行任何交换操作,则说明数组已经完成排序,可直接返回结果,所有这里引入了一个flag变量,进行检测。
如果你想看看其他语言的代码实现,可以直接去菜鸟教程上面查找。
相关文章
- 排序算法的复习和总结[PHP实现]
- 梳排序算法
- Java实现 蓝桥杯VIP 算法提高 质数的后代
- Java实现 蓝桥杯 算法提高 队列操作
- Java实现 蓝桥杯 算法提高 判断名次
- 常见排序算法总结与实现(冒泡、插入、选择、希尔、堆排序、归并、快排)
- Python排序算法之选择排序定义与用法示例
- 这些年,这些挖掘机算法,这些反思
- 数据结构和算法-排序算法-冒泡排序
- (算法:二分查找)在排序数组中,找出给定数字出现的次数
- 基于物品的协同过滤算法(ItemCF)
- DL之DNN:基于sklearn自带california_housing加利福尼亚房价数据集利用GD神经网络梯度下降算法进行回归预测(数据较多时采用mini-batch方式训练会更快)
- 四阶Runge-Kutta算法(C语言实现)
- 一种全局搜索策略的鲸鱼优化算法-附代码
- 算法——基础篇——高速排序
- 简单谈谈 数组排序 的方法 【自定义算法 、 冒泡算法 等】
- 【数据结构与算法Python实践系列】5分钟学会经典排序算法-插入排序
- 1665. 完成所有任务的最少初始能量-快速排序+贪心算法
- EM算法简单介绍
- 八大排序算法
- KMP算法
- 数据结构与算法_13 _ 线性排序:如何根据年龄给100万用户数据排序
- 试题 算法训练 小木棍
- 数据结构和算法 十七、排序算法
- 【C++】算法集锦(12):高楼扔鸡蛋
- DSA之十大排序算法第五种:Merge Sort
- DSA之十大排序算法第二种:Straight Selection Sort
- 【排序算法】图解冒泡排序(多图+解决两种无效比较问题)