详解冒泡排序

2020年3月23日15:07:21算法评论38阅读模式

基本思想

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

例子

给定一个数组如下:
[ 5 , 8 , -2 , 20 -6 ]
定义两个变量 ij,初始状态 i 存第一个元素的索引,ji代表元素的下一个元素的索引;文章源自随机的未知-https://sjdwz.com/11137.html

如下图:文章源自随机的未知-https://sjdwz.com/11137.html

详解冒泡排序
初始状态

第一趟排序文章源自随机的未知-https://sjdwz.com/11137.html

(1) 5 < 8不用发生交换文章源自随机的未知-https://sjdwz.com/11137.html

详解冒泡排序
然后 i ,j 均向后移动;文章源自随机的未知-https://sjdwz.com/11137.html

详解冒泡排序
(2) 8 > -2 需要发生交换文章源自随机的未知-https://sjdwz.com/11137.html

详解冒泡排序
然后 i ,j 均向后移动;文章源自随机的未知-https://sjdwz.com/11137.html

详解冒泡排序
第一趟排序3

(3) 8 < 20 不需要发生交换文章源自随机的未知-https://sjdwz.com/11137.html

详解冒泡排序
然后 i ,j 均向后移动;文章源自随机的未知-https://sjdwz.com/11137.html

详解冒泡排序
第一趟排序5

(4) 20 > -6 需要发生交换
详解冒泡排序文章源自随机的未知-https://sjdwz.com/11137.html

此时 j已经不能向后移动,第一趟排序结束,将当前最大的元素 20 移动到了最后的位置。文章源自随机的未知-https://sjdwz.com/11137.html

详解冒泡排序
第一趟排序7

第二趟排序文章源自随机的未知-https://sjdwz.com/11137.html

i ,j重新赋值如下:
详解冒泡排序
详解冒泡排序文章源自随机的未知-https://sjdwz.com/11137.html

第三趟排序文章源自随机的未知-https://sjdwz.com/11137.html

i ,j重新赋值如下:
详解冒泡排序文章源自随机的未知-https://sjdwz.com/11137.html

详解冒泡排序
第三趟排序

第四趟排序文章源自随机的未知-https://sjdwz.com/11137.html

i ,j重新赋值如下:
详解冒泡排序文章源自随机的未知-https://sjdwz.com/11137.html

详解冒泡排序
第四趟排序

四个数组均到达该到的位置,排序完毕。
由此可见,每一趟排序都会减少比较次数。
会 有数组长度-1趟排序。文章源自随机的未知-https://sjdwz.com/11137.html

代码

使用双重循环来完成:文章源自随机的未知-https://sjdwz.com/11137.html

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直接退出循环。
代码如下:文章源自随机的未知-https://sjdwz.com/11137.html

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 = = ;
所以冒泡排序的时间复杂度是。文章源自随机的未知-https://sjdwz.com/11137.html

稳定性

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

总结

冒泡排序的思想是通过对待排序的序列从前向后依次比较相邻元素的值,如果发现逆序则交换。
优化方法是,若一趟排序中没有发生交换则退出循环,已经有序。
冒泡排序的时间复杂度是,是稳定的排序算法。文章源自随机的未知-https://sjdwz.com/11137.html

欢迎关注

欢迎大家的关注文章源自随机的未知-https://sjdwz.com/11137.html

扫描下方的二维码关注我的微信公众号:随机的未知
详解冒泡排序文章源自随机的未知-https://sjdwz.com/11137.html

文章源自随机的未知-https://sjdwz.com/11137.html
欢迎关注本站微信公众号:随机的未知 如果喜欢本文,欢迎点赞,收藏,转发,打赏。
算法最后更新:2022-3-24
  • 本文由 发表于 2020年3月23日15:07:21
  • 转载请注明:来源:随机的未知 本文链接https://sjdwz.com/11137.html
算法

详解堆排序

什么是堆 堆首先是一个完全二叉树,堆分为大顶堆和小顶堆; 大顶堆 : 每个节点的值大于或等于其左右孩子节点的值,称为大顶堆。 小顶堆同理就是每个节点的值小于或等于其左右孩子节点的值。 注意: 每个节点...
算法

详解基数排序

基本思想 基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。 例子 本文以数组中元素均为正整数来演示思想。 给定一个数组 arr = < 6, 56, 89 , ...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定