【排序算法】冒泡排序原理及Java实现

今天药忘吃喽~ 2022-08-21 10:42 226阅读 0赞

## 1、基本思想 ##

冒泡排序顾名思义就是整个过程像气泡一样往上升，单向冒泡排序的基本思想是（假设由小到大排序）：对于给定n个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换位置，进行一轮比较和换位后，n个记录的最大记录将位于第n位，然后对前（n-1）个记录进行第二轮比较；重复该过程，直到记录剩下一个为止。

## 2、复杂度分析 ##

当最好的情况，也就是要排序的序列本身就是有序的，需要进行*（n-1）*次比较，没有数据交换，时间复杂度为*O(n)*.  
当最坏的情况，即待排序的表是逆序的情况，此时需要比较次数为：*1+2+3+…+(n-1)=n(n-1)/2* 次，并作等数量级的记录移动，因此总的时间复杂度为![这里写图片描述][20160427091644346]。

## 3、排序过程如下 ##

以数组\{49,38,65,97,76,13,27,49\}为例，  
![这里写图片描述][20160426212450715]  
![这里写图片描述][20160426212501340]

## 4、Java实现如下 ##

public class BubbleSort {
        public static void bubbleSort(int[] a) {
            int temp;
            for (int i = 0; i < a.length - 1; ++i) {
                for (int j = a.length - 1; j > i; --j) {
                    if (a[j] < a[j - 1]) {
                        temp = a[j];
                        a[j] = a[j - 1];
                        a[j - 1] = temp;
                    }
                }
            }
    
        }
    
        public static void main(String[] args) {
    
            int a[] = { 49,38,65,97,76,13,27,49};
            bubbleSort(a);
            System.out.println(Arrays.toString(a));
        }
    
    }

[20160427091644346]: /images/20220724/4c0c9e332b8a45c781c5f22916e2fd68.png
[20160426212450715]: /images/20220724/b0afdf20f6954598aeffc570ded1f1b7.png
[20160426212501340]: /images/20220724/b26190171c2c44fb96bb53f7995f31a7.png