冒泡排序法

冒泡排序法又称为交换排序法,是由观察水中冒泡变化构思而成,气泡随着水深压力而改变.气泡在水底时,水压最大,气泡最小,而气泡慢慢浮上水面时,气泡所受压力最小,体积慢慢变大.

冒泡排序比较方式是从第一个元素开始,比较相邻的元素大小,如果大小顺序有误,则对调后进行下一个元素比较.直到所有元素满足关系为止.

冒泡排序法分析

1. 冒泡排序法平均情况下,需要比较(n-1)/2次,时间复杂度为O(n

   ²),最好的情况只需要扫描一次,不用操作,即作n-1次比较,时间复杂度为O(n).
2. 由于冒泡排序为相邻两者相互比较对调,并不会改变其原本排列的顺序,所以是稳定的排序法
3. 只需要一个额外的空间,所以空间复杂度最佳
4. 这个排序法适用于数据量小,或者有部分数据已经排序过的情况

代码示例:

import java.util.Random;/** * 算法大神之路----排序(冒泡排序法) */public class Study01 {    public static void main(String[] args) {        //新建一个数组        int[] arr = new int[6];        Random r = new Random();        for (int i = 0; i < arr.length; i++) {        //使用随机数给数组赋值            arr[i] = r.nextInt(50);        }        System.out.print("原数组为:");        paint(arr);        System.out.println("-----排序-----");        //使用冒泡排序法进行排序,最差情况下        for (int i = arr.length-1; i >=0; i--) {            //比较当前数和后一个数,谁大,谁放后面            for (int j = 0; j < i; j++) {                if(arr[j]>arr[j+1]){                    int temp=arr[j];                    arr[j]=arr[j+1];                    arr[j+1]=temp;                }            }            System.out.print("扫描第"+(arr.length-i)+"次结果为:");            paint(arr);        }    }    public static void paint(int[] arr){        for (int i = 0; i < arr.length; i++) {            System.out.print(arr[i]+"\t");        }        System.out.println();    }}

结果:

原数组为:34    41    24    36    15    21    -----排序-----扫描第1次结果为:34    24    36    15    21    41    扫描第2次结果为:24    34    15    21    36    41    扫描第3次结果为:24    15    21    34    36    41    扫描第4次结果为:15    21    24    34    36    41    扫描第5次结果为:15    21    24    34    36    41    扫描第6次结果为:15    21    24    34    36    41

可见:

• 第一次扫描时候,把第二个数41一直比较到后面去了
• 第二次扫描则是比较了,把36放到倒数第二个数
• ...
• 最后当第四次扫描的时候,已经排好序.最差情况下需要扫描"数组元素"次,一般,想要优化的话,即在程序中设置,当扫描到已经符合要求后,就直接停止扫描即可