详细描述
冒泡排序是一种交换排序,基本思想是在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。
即每当两个相邻的数比较后发现它们的顺序与排序要求相反时,就将它们互换。
冒泡排序详细的执行步骤如下:
- 从第一个元素开始,比较相邻的元素,如果前一个比后一个大,就交换它们两个;
- 从前往后,对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素就会是最大的数;
- 将这次找出的最大元素放在最后一个元素位置上,然后针对除这个最大元素以外的其他所有元素重复以上 1~2 步骤;
- 重复以上步骤,直到最后第一个元素和第二个元素完成比较、交换,则排序完成。
算法图解
问题解疑
冒泡排序是原地排序算法吗?
冒泡排序是一个原地排序算法,过程只涉及相邻数据的交换操作,只需要常量级的临时空间,它的空间复杂度是 O(1)。
冒泡排序是稳定的排序算法吗?
为了保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等时可以不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。
冒泡排序的时间复杂度是多少?
使用最优时间复杂度解法,原序列是有序时的时间复杂度是 O(n);最坏情况时间复杂度为 O(n2);平均时间复杂度是 O(n2)。文章来源:https://www.toymoban.com/news/detail-411776.html
代码实现
排序接口
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; |
|
} |
|
} |
文章来源地址https://www.toymoban.com/news/detail-411776.html
到了这里,关于冒泡排序的简单理解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!