算法

??冒泡排序作為最基礎(chǔ)最簡單的排序算法，實(shí)質(zhì)是相鄰兩元素比較，若有序則跳過，若無序則交換。最多需n-1趟排序，第i趟需比較n-i次。所以時(shí)間復(fù)雜度為o(n*n)，是一種比較低效率的排序算法。不過對于初學(xué)者來說是必須掌握的一種算法。
??冒泡排序有一點(diǎn)可以改進(jìn)的地方，初學(xué)者可能沒注意到。就是當(dāng)序列已經(jīng)整體有序時(shí)，就不需要再作不必要的比較了?？梢栽O(shè)置一個(gè)布爾變量，當(dāng)一趟下來未發(fā)生交換時(shí)，直接跳出循環(huán)，能夠提高排序效率。

Codes

package com.fairy.InnerSort;

import java.util.Scanner;
/**
 * 冒泡排序
 * @author Fairy2016
 *
 */
public class BubbleSort {
    
    public static void sort(int a[], int n) {
        boolean flag = false;
        for(int i = 1; i <= n-1; i++) {
            flag = false;
            for(int j = 1; j <= n-i; j++) {
                if(a[j] > a[j+1]) {
                    //交換a[j]與a[j+1]
                    a[0] = a[j];
                    a[j] = a[j+1];
                    a[j+1] = a[0];
                    //標(biāo)記發(fā)生了交換
                    flag = true;
                }
            }
            //若未發(fā)生交換，直接退出，排序已完成
            if(!flag) {
                break;
            }
        }
    }

    public static void Print(int a[], int n) {
        for(int i = 1; i <= n; i++) {
            System.out.print(a[i]+" ");
        }
    }

    public static void main(String args[]) {
        int n;
        int a[];
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            n = scanner.nextInt();
            if(n > 0) {
                a = new int[n+1];
                for(int i=1; i <= n; i++) {
                    a[i] = scanner.nextInt();
                }
                sort(a, n);
                Print(a, n);
            }
        }
        scanner.close();
    }
}