专栏首页code随笔的专栏详解冒泡排序算法

详解冒泡排序算法

基本思想

冒泡排序的基本思想是: 通过对待排序的序列从前向后依次比较相邻元素的值,如果发现逆序则交换。 逆序的含义:如果想把序列从小到大排序,那么两个数中前面的比后面的大就是逆序。 若需求是将序列从小到大排序,那么每一趟比较都会把值较大的逐渐从前面移动到后面。 就像水底的泡泡一样: (如下图,图片来源于网络)

水底冒泡图片

例子

给定一个数组如下: [ 5 , 8 , -2 , 20 -6 ] 定义两个变量 ij,初始状态 i 存第一个元素的索引,ji代表元素的下一个元素的索引;

如下图:

初始状态

第一趟排序

(1) 5 < 8不用发生交换

第一趟排序1 然后 i ,j 均向后移动;

第一趟排序2 (2) 8 > -2 需要发生交换

第一趟排序2 然后 i ,j 均向后移动;

第一趟排序3

(3) 8 < 20 不需要发生交换

第一趟排序4 然后 i ,j 均向后移动;

第一趟排序5

(4) 20 > -6 需要发生交换

第一趟排序6

此时 j已经不能向后移动,第一趟排序结束,将当前最大的元素 20 移动到了最后的位置。

第一趟排序7

第二趟排序

i ,j重新赋值如下:

第二趟排序初始状态

第二趟排序

第三趟排序

i ,j重新赋值如下:

第三趟排序初始状态

第三趟排序

第四趟排序

i ,j重新赋值如下:

第四趟排序初始状态

第四趟排序

四个数组均到达该到的位置,排序完毕。 由此可见,每一趟排序都会减少比较次数。 会 有数组长度-1趟排序。

代码

使用双重循环来完成:

int temp;//用于交换的临时变量
for(int i=0;i<arr.length - 1;i++){
        for(int j = 0;j<arr.length - 1 - i ; j++){
            if(arr[j] > arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
       }
}

优化

如果一趟排序都没有发生交换,表示已经有序了,没必要进行接下来的排序了。 可以定义一个 flag ,初始值为false,如果发生交换,就赋值为true,否则一直是false直接退出循环。 代码如下:

import java.lang.reflect.Array;
import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        bubbleSort(new int[]{5,8,-2,20,-6});
    }
    public static void bubbleSort(int[] arr) {

        int temp;//用于交换的临时变量
        boolean flag = false;//表示是否进行交换
        for(int i=0;i<arr.length - 1;i++){
            for(int j = 0;j<arr.length - 1 - i ; j++){
                if(arr[j] > arr[j + 1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if(!flag){
                break;
            }else{
                flag = false;//将flag重新置为false
            }
        }

        System.out.println(Arrays.toString(arr));
    }
}

时间复杂度

如果原数组有序,则遍历一遍就可以,最好的时间复杂度是

; 如果原数组倒序,则比较次数是: n-1 + n-2 + … + 2 + 1 =

=

; 所以冒泡排序的时间复杂度是

稳定性

冒泡排序就是把逆序的元素进行交换,每次都是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,是不会再交换的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

总结

冒泡排序的思想是通过对待排序的序列从前向后依次比较相邻元素的值,如果发现逆序则交换。 优化方法是,若一趟排序中没有发生交换则退出循环,已经有序。 冒泡排序的时间复杂度是

,是稳定的排序算法。

欢迎关注

欢迎大家的关注

扫描下方的二维码关注我的微信公众号:code随笔

微信公众号:code随笔

本文分享自微信公众号 - code随笔(yzsgxhywh),作者:灿烂星空StarrySky

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 42题 接雨水(Trapping Rain Water)

    https://leetcode-cn.com/problems/trapping-rain-water/

    code随笔
  • 详解快速排序算法

    本文的思路是以从小到大为例讲的。 快速排序的基本思想是任取待排序序列的一个元素作为中心元素(可以用第一个,最后一个,也可以是中间任何一个),习惯将其称为pivo...

    code随笔
  • 详解选择排序算法

    选择排序的思想是: 给定一个数组arr,其长度为n; 第一次从 arr[0] 到 arr[n-1] 中选取一个最值(按照需求,可以是最...

    code随笔
  • 你知道什么是漂亮排序法吗?哦,知道,不就是臭皮匠排序法嘛!

    在《算法导论》第二版第 7 章(快速排序)的思考题(第 95 页)中提及到一种 低效的递归排序算法:Stooge 排序, Howard、Fine 等教授将这个算...

    五分钟学算法
  • 普林斯顿大学算法公开课笔记——选择排序 普林斯顿大学算法公开课笔记——选择排序

    简单选择排序的特点是交换移动次数很少(至多n-1次),其时间复杂度为 O(n²) (时间主要花在比较上,总的比较次数为N=(n-1)+(n-2)+…+1=n*(...

    尾尾部落
  • 算法之排序(上)

    排序算法有很多种,甚至有很多都完全没有听过,我们最常见,也最经典的就是:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

    信安本原
  • Qml教程-第一个HelloWorld程序

    Qt君
  • 数据结构与算法学习笔记之如何分析一个排序算法?

    现在IT这块找工作,不会几个算法都不好意思出门,排序算法恰巧是其中最简单的,我接触的第一个算法就是它,但是你知道怎么分析一个排序算法么?有很多时间复杂度相同的排...

    Dawnzhang
  • 不学不知道,sort()方法中的坑

    今天的前端零基础课,在讲到js中的sort()排序方法的时候,说sort()这个方法在给数字排序的时候,根本不是按数字大小来排序的。 它是把数字都当成字符串来看...

    web前端教室
  • VSCode配置eslint

    在Vue.js项目中,使用的是eslint检查。 而在我写完代码后,cnpm run dev运行命令。。。然后悲剧了,一大堆报错!╮(╯▽╰)╭ 安装插件:Ve...

    用户1149564

扫码关注云+社区

领取腾讯云代金券