基本算法：冒泡排序算法

冒泡算法簡(jiǎn)介

冒泡算法（Bubble Sort)，是一種比較簡(jiǎn)單的排序算法。其排序邏輯是：重復(fù)訪問(wèn)需要排序的元素列，依次比較兩個(gè)相鄰的元素，如果順序（如從大到小首字母從A到Z）有誤，就會(huì)對(duì)元素進(jìn)行位置交換，重復(fù)該過(guò)程直到?jīng)]有相鄰的元素需要進(jìn)行交換。
算法的名稱是因?yàn)榻?jīng)過(guò)該算法排序后，越小的元素會(huì)經(jīng)過(guò)交換會(huì)像泡泡一樣慢慢浮動(dòng)到數(shù)列的頂端，故此得名冒泡算法。

算法排序詳解

假設(shè)有數(shù)組【1，6，3，5，2】，我們使用從小到大進(jìn)行的方式進(jìn)行冒泡排序。

第一趟排序：

1. 1與6相比，1小于6，位置不變?！?，6，3，5，2】
2. 6與3相比，6大于3，交換位置?！?，3，6，5，2】
3. 6與5相比，6大于5，交換位置?！?，3，5，6，2】
4. 6與2相比，6大于2，交換位置?！?，3，5，2，6】

第二趟排序：

1. 1與3相比，1小于3，位置不變。【1，3，5，2，6】
2. 3與5相比，3小于5，位置不變?！?，3，5，2，6】
3. 5與2相比，5大于2，交換位置?！?，3，2，5，6】

第三趟排序：

1. 1與3相比，1小于3，位置不變?！?，3，2，5，6】
2. 3與2相比，3大于2，交換位置?！?，2，3，5，6】

分析

• 冒泡排序每排序一趟，就會(huì)少比較一個(gè)數(shù)據(jù)。因?yàn)槊恳淮闻判蚨紩?huì)將較大值進(jìn)行下標(biāo)后移，第一趟排排序，找出最大值，第二趟排序找出次大值。比較到最后，需要比較的數(shù)據(jù)越來(lái)越少。N個(gè)長(zhǎng)度的數(shù)據(jù)要進(jìn)行冒泡排序，要進(jìn)行N-1趟排序，第i趟的排除次數(shù)為N-i-1次（因?yàn)槊恳惶司蜁?huì)少比較一個(gè)數(shù)據(jù)）。

復(fù)雜度分析

下面我們來(lái)分析下冒泡排序的時(shí)間復(fù)雜度和空間復(fù)雜度。

時(shí)間復(fù)雜度：

• 最好的情況：數(shù)據(jù)本身已經(jīng)排序完畢，那就不用元素交換。僅需n-1次即可完成排序，時(shí)間復(fù)雜度是O(n)。
• 最壞情況:數(shù)據(jù)是逆序排列，所以我們要全部重新排序一次。對(duì)于n位的數(shù)列則有比較次數(shù)為 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2=O(n^2)。
• 平均復(fù)雜度：O(n^2)

空間復(fù)雜度：該算法的所消耗的存儲(chǔ)空間。

• 最好情況：數(shù)據(jù)本身有序，不會(huì)用到臨時(shí)變量，則復(fù)雜度為0。
• 最差情況：數(shù)據(jù)逆序排序，每次都會(huì)使用到臨時(shí)變量。復(fù)雜度為O(n)。
• 平均復(fù)雜度：O(1)。

Java代碼實(shí)現(xiàn)

package top.enjoyitlife.bubble;

import java.util.Arrays;

/***
* @ClassName: BubbleAlgorithm 
* @Description: 冒泡排序算法
* @author MegaSlark 
 */
public class BubbleAlgorithm {
    public static void main(String[] args) {
        int[] nums=new int[] {1,2,3,6,7};
        BubbleAlgorithm ba = new BubbleAlgorithm();
        ba.bubbleSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    /****
     * 冒泡排序 正序 有小到大
     * @param nums
     */
    public void bubbleSort(int[] nums) {
        if(null==nums||nums.length<1) {
            return;
        }
        int length=nums.length;
        //數(shù)組下標(biāo)從0開(kāi)始，比較趟數(shù)為數(shù)組長(zhǎng)度減1
        for(int i=0;i<length-1;i++) {
            //是否需要全部循環(huán)標(biāo)識(shí)
            boolean flag=true;
            //length-1的原因同上，多減i是因?yàn)椴恍枰容^的數(shù)據(jù)為i個(gè)。每次冒泡都會(huì)找出一個(gè)不許要再次比較的數(shù)。
            for( int j=0;j<length-1-i;j++) {
                // 控制冒泡方向 倒序還是正序
                int temp=0;
                if(nums[j]  >  nums[j+1]) {
                    temp=nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=temp;
                    flag=false;
                }
            }
            if(flag) {
                break;
            }
            
        }
    }
}

以上就是冒泡排序的接受及代碼示例，希望對(duì)你有所幫助。