首页 > 其他分享 >冒泡排序

冒泡排序

时间:2022-10-08 22:00:10浏览次数:44  
标签:int 元素 冒泡排序 numbers 排序 比较

冒泡排序

代码

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] numbers = { 5, 1, 3, 2, 4, 6 };
        System.out.println("排序前的数组为:" + Arrays.toString(numbers));
        // 冒泡排序
        // 外层循环控制排序循环的轮数
        for (int i = 0; i < numbers.length - 1; i++) {
            // 内层循环控制两两比较
            for (int j = 0; j < numbers.length - i - 1; j++) {
                // 不通过第三遍量交换两个数的顺序
                if (numbers[j] > numbers[j + 1]) {
                    numbers[j] += numbers[j + 1];
                    numbers[j + 1] = numbers[j] - numbers[j + 1];
                    numbers[j] -= numbers[j + 1];
                }
            }
        }
        System.out.println("排序后的数组为:" + Arrays.toString(numbers));
    }
}

输出效果为:

排序前的数组为:[5, 1, 3, 2, 4, 6]

排序后的数组为:[1, 2, 3, 4, 5, 6]

释义

冒泡算法,通过两两比较得到排好顺序的数列。以[5, 1, 3, 2, 4, 6]升序排列为例,一步一步来理顺。

第一轮比较是这样的,将两个相邻的元素相比较,若前面的元素比后面的元素小则元素交换位置。先是第一个和第二个元素比较,下面依次是第二个和第三个元素比较直到倒数第二个和最后一个。通过第一轮比较可以将数值最大的元素放置到数组末尾。这里一共比较了五次
[5, 1, 3, 2, 4, 6]5和1比较
[1, 5, 3, 2, 4, 6]5和3比较
[1, 3, 5, 2, 4, 6]5和2比较
[1, 3, 2, 5, 4, 6]5和4比较
[1, 3, 2, 4, 5, 6]5和6比较
[1, 3, 2, 4, 5, 6]
接着是第二轮比较。这次比较直比较5个元素即可,因为最后一个元素已经确认。为了方便理解,最后一个元素不予显示。这里一共比较了四次
[1, 3, 2, 4, 5]1和3比较
[1, 3, 2, 4, 5]3和2比较
[1, 2, 3, 4, 5]3和4比较
[1, 2, 3, 4, 5]4和5比较
[1, 2, 3, 4, 5]
以这个数组为例并不恰当,因为第二次比较就已经得出了排好顺序的数组,但是计算机并不知道这是排好序的数组,为了更好的理解冒泡排序,我们走完它。第三次:
[1, 2, 3, 4]1和2比较
[1, 2, 3, 4]2和3比较
[1, 2, 3, 4]3和4比较
[1, 2, 3, 4]
第四次:
[1, 2, 3]1和2比较
[1, 2, 3]2和3比较
[1, 2, 3]
第五次:
[1, 2]1和2比较
[1, 2]
至此,已经比较完毕。我们一次得到了五个最大的元素。如果上面的数组不省略,最后一应该写作[1, 2, 3, 4, 5, 6]

六个元素排序,我们一共进行了五轮比较,若是进行N个元素排序,需进行N-1次比较。

每一轮的比较中,比较的次数也是有迹可循的。前一轮的比较会得到某个极值元素,我们只需将此元素排除,进行剩余的元素个数-1次比较就会得到剩余元素中的极值元素。

在实际代码过程中外层控制比较轮数,内层控制美伦比较次数。数组下标从零开始。就可以得出循环的条件:
外层循环:int i = 0; i < numbers.length - 1; i++

内层循环:int j = 0; j < numbers.length - i - 1; j++

改进

从上面的例子我们可以看出,最后的几轮排序是毫无用处的,这给计算机造成了一定程度上的资源浪费。我们应该怎么避免这种无意义的循环呢?可以设置标记变量来实现。

int flag = 1;
for (int i = 0; i < numbers.length - 1 && flag != 0; i++) {
    flag = 0;
    // 内层循环控制两两比较
    for (int j = 0; j < numbers.length - i - 1; j++) {
        // 不通过第三遍量交换两个数的顺序
        if (numbers[j] > numbers[j + 1]) {
            numbers[j] += numbers[j + 1];
            numbers[j + 1] = numbers[j] - numbers[j + 1];
            numbers[j] -= numbers[j + 1];
            // 若不交换位置,flag应为0,外层条件不成立,循环结束
            flag = 1;
        }
    }
}

总结

时间复杂度

在设置标志变量之后:

当原始序列“正序”排列时,冒泡排序总的比较次数为n-1,移动次数为0,也就是说冒泡排序在最好情况下的时间复杂度为O(n);

当原始序列“逆序”排序时,冒泡排序总的比较次数为n(n-1)/2,移动次数为3n(n-1)/2次,所以冒泡排序在最坏情况下的时间复杂度为O(n^2);

当原始序列杂乱无序时,冒泡排序的平均时间复杂度为O(n^2)。

空间复杂度

冒泡排序排序过程中需要一个临时变量进行两两交换,所需要的额外空间为1,因此空间复杂度为O(1)。

稳定性

冒泡排序是一种稳定的排序算法。这里稳定的意思是指,若两元素数值相同,他们的位置并不会发生改变。

标签:int,元素,冒泡排序,numbers,排序,比较
From: https://www.cnblogs.com/isxh/p/16770407.html

相关文章

  • 冒泡排序、选择排序 、快速排序 、
    1.冒泡排序每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位,第二趟只能将倒数第2位上的数归位,依次类推下去。如果有n个数进行排序,只需将n-1个数归......
  • 冒泡排序算法并调优
    算法步骤比较相邻的元素。如果第一个比第二个大,就交换他们两个。对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。......
  • Python 冒泡排序,选择排序,归并排序, 希尔排序 算法 及测试
    使用代码实现冒泡排序,选择排序,归并排序,希尔排序4中算法完成下列任务。对1~100000序列打乱顺序,使用上述4种排序算法进行排序。每种算法排序重复100次排序过程中记录......
  • Java冒泡排序
    publicclassArrayDome7{/*冒泡拍寻是最为出名的排序算法之一,总共又八大paixu冒泡排序的代码是:两层循环,外层冒泡轮数,里层依次比较时间......
  • 冒泡排序算法
    冒泡排序算法(BubbleSort)算法是一种简单的排序算法,它在重复访问要排序的元素列时,会依次比较相邻的两个元素,如果左边的元素大于后边的元素,就将二者交换位置,如此重复,......
  • java---冒泡排序和稀疏数组的学习
    一.冒泡排序1.冒泡排序无疑是最为出名的排序算法,总共有8大排序2.冒泡代码相当简单,两层循环,两层冒泡轮数,里面依次比较3.我们看到的嵌套循环,应该立马就可以的出这个算法的......
  • 冒泡排序
    冒泡排序是最为出名的排序算法之一,共有八大排序。冒泡的代码还是相当简单的,两层循环,外层冒泡轮数,里层依次比较,江湖中人人尽皆知。我们看到嵌套循环,应该立马就可以得......
  • 冒泡排序
    这里求解的是一个数组中的最大值和次最大值,#include<stdio.h>main(){ intarr[20]; inti,j,max=0,temp; for(i=0;i<20;i++) scanf("%d",&arr[i]); //直接用......
  • 冒泡排序
    关于冒泡排序的理解packagearray;importjava.util.Arrays;publicclassShort{publicstaticvoidmain(String[]args){int[]z={1,4,113,5,213,7,3,......
  • 冒泡排序
    inta[]={23,1,55,7,4,2};intn=6,i,j,temp;for(i=1;i<6;i++)//趟数{for(j=0;j<n-i;j++)//每趟的顺序比较 if(a[j]>a[j+1]) {......