冒泡排序的简单理解
2023-02-19 12:17:31 时间
详细描述
冒泡排序是一种交换排序,基本思想是在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。
即每当两个相邻的数比较后发现它们的顺序与排序要求相反时,就将它们互换。
冒泡排序详细的执行步骤如下:
- 从第一个元素开始,比较相邻的元素,如果前一个比后一个大,就交换它们两个;
- 从前往后,对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素就会是最大的数;
- 将这次找出的最大元素放在最后一个元素位置上,然后针对除这个最大元素以外的其他所有元素重复以上 1~2 步骤;
- 重复以上步骤,直到最后第一个元素和第二个元素完成比较、交换,则排序完成。
算法图解
问题解疑
冒泡排序是原地排序算法吗?
冒泡排序是一个原地排序算法,过程只涉及相邻数据的交换操作,只需要常量级的临时空间,它的空间复杂度是 \(O(1)\)。
冒泡排序是稳定的排序算法吗?
为了保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等时可以不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。
冒泡排序的时间复杂度是多少?
使用最优时间复杂度解法,原序列是有序时的时间复杂度是 \(O(n)\);最坏情况时间复杂度为 \(O(n^2)\);平均时间复杂度是 \(O(n^2)\)。
代码实现
排序接口
package cn.fatedeity.algorithm.sort;
/**
* 排序接口
*/
public interface Sort {
int[] sort(int[] numbers);
}
排序抽象类
package cn.fatedeity.algorithm.sort;
/**
* 排序抽象类
*/
public abstract class AbstractSort implements Sort {
protected void swap(int[] numbers, int src, int target) {
int temp = numbers[src];
numbers[src] = numbers[target];
numbers[target] = temp;
}
}
冒泡排序类
package cn.fatedeity.algorithm.sort;
/**
* 冒泡排序类
*/
public class BubbleSort extends AbstractSort {
@Override
public int[] sort(int[] numbers) {
if (numbers.length <= 1) {
return numbers;
}
for (int i = 0; i < numbers.length - 1; i++) {
boolean doSwap = false;
for (int j = 0; j + 1 < numbers.length - i; j++) {
if (numbers[j] > numbers[j + 1]) {
this.swap(numbers, j, j + 1);
doSwap = true;
}
}
// 优化基础冒泡排序的步骤
if (!doSwap) {
// 如果遍历整个序列无需交换,则表示整个序列已经完全有序
return numbers;
}
}
return numbers;
}
}
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023