java常見(jiàn)排序方式-冒泡排序
一.冒泡排序介紹
冒泡排序是我們得最多的排序方式之一，原因是簡(jiǎn)單易實(shí)現(xiàn)，且原理易懂。顧名思義，冒泡排序，它的排序過(guò)程就像水中的氣泡一樣，一個(gè)一個(gè)上浮到水面。
二.冒泡排序原理分析
三.冒泡排序代碼實(shí)現(xiàn)
/**
* @Author {LearnAndGet}
* @Time 2019年1月8日
* @Discription:
*/
package com.sort;
import java.util.Arrays;
public class MaopaoSort {
static int[] array = {3,2,4,1,5,0};
public static void maopaoSort(int[] a)
{
//外層循環(huán)，是需要進(jìn)行比較的輪數(shù)，一共進(jìn)行5次即可
for(int i=0;i1;i++)
{
//內(nèi)存循環(huán)，是每一輪中進(jìn)行的兩兩比較
for(int j=0;j1;j++)
{
if(a[j] > a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
System.out.println("第"+(i+1)+"輪排序后的數(shù)組為: "+Arrays.toString(a));
}
}
public static void main(String[] args) {
maopaoSort(array);
}
}
輸出結(jié)果
第1輪排序后的數(shù)組為: [2, 3, 1, 4, 0, 5]
第2輪排序后的數(shù)組為: [2, 1, 3, 0, 4, 5]
第3輪排序后的數(shù)組為: [1, 2, 0, 3, 4, 5]
第4輪排序后的數(shù)組為: [1, 0, 2, 3, 4, 5]
第5輪排序后的數(shù)組為: [0, 1, 2, 3, 4, 5]
四.冒泡排序的優(yōu)化
1 .觀察上述代碼和運(yùn)行結(jié)果，我們可以發(fā)現(xiàn)，當(dāng)?shù)谝惠喗Y(jié)束后，最后一個(gè)數(shù)字一定是數(shù)組中最大的元素，那么我們?cè)谶M(jìn)行第二趟的兩兩比較時(shí)，實(shí)際上是沒(méi)有必要再對(duì)第5個(gè)和第6個(gè)進(jìn)行比較的。那么我們可以修改代碼如下：
public static void maopaoSort(int[] a)
{
//外層循環(huán)，是需要進(jìn)行比較的輪數(shù)，一共進(jìn)行5次即可
for(int i=0;i1;i++)
{
//內(nèi)存循環(huán)，是每一輪中進(jìn)行的兩兩比較
//并且每一輪結(jié)束后，下一次的兩兩比較中可以少比較一次
for(int j=0;j1;j++)
{
if(a[j] > a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
System.out.println("第"+(i+1)+"輪排序后的數(shù)組為: "+Arrays.toString(a));
}
}
繼續(xù)運(yùn)行后，可以發(fā)現(xiàn)運(yùn)行結(jié)果是一樣的。
2 .當(dāng)我們用數(shù)組：{1,2,0,3,5,4}來(lái)測(cè)試上述冒泡排序時(shí)，運(yùn)行結(jié)果如下：
第1輪排序后的數(shù)組為: [1, 0, 2, 3, 4, 5]
第2輪排序后的數(shù)組為: [0, 1, 2, 3, 4, 5]
第3輪排序后的數(shù)組為: [0, 1, 2, 3, 4, 5]
第4輪排序后的數(shù)組為: [0, 1, 2, 3, 4, 5]
第5輪排序后的數(shù)組為: [0, 1, 2, 3, 4, 5]
可以看到，在第2輪排序完成后，其實(shí)我們就已經(jīng)的到了排好序的數(shù)組，但是我們的程序并不知道，仍然進(jìn)行了后續(xù)的無(wú)用工作。那么，我們?nèi)绾蝸?lái)讓程序知道已經(jīng)完成好排序了呢？
這里可以想到，當(dāng)某一輪的兩兩比較中，如果都沒(méi)有發(fā)生數(shù)組元素的互換，那么其實(shí)排序工作已經(jīng)完成了，所以我們可以考慮在程序中加入一個(gè)flag，默認(rèn)為false，含義是該輪比較中是否發(fā)生了元素互換，當(dāng)程序中執(zhí)行到元素互換時(shí)，將該flag置為true，當(dāng)該輪比較結(jié)束時(shí)，若flag為flase，則說(shuō)明該輪比較未發(fā)生元素互換，那么排序完成，若flag為true，說(shuō)明本輪比較仍然有元素互換，需要繼續(xù)進(jìn)行下輪排序。代碼實(shí)現(xiàn)如下：
/**
* @Author {LearnAndGet}
* @Time 2019年1月8日
* @Discription:
*/
package com.sort;
import java.util.Arrays;
public class MaopaoSort {
static int[] array = {1,2,0,3,5,4};
public static void maopaoSort(int[] a)
{
//外層循環(huán)，是需要進(jìn)行比較的輪數(shù)，一共進(jìn)行5次即可
for(int i=0;i1;i++)
{
boolean flag = false;
//內(nèi)存循環(huán)，是每一輪中進(jìn)行的兩兩比較
for(int j=0;j1;j++)
{
if(a[j] > a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
flag = true;
}
}
System.out.println("第"+(i+1)+"輪排序后的數(shù)組為: "+Arrays.toString(a));
if(flag == false)
{
System.out.println("本輪中的兩兩比較未發(fā)生元素互換，排序已經(jīng)完成啦");
return;
}
}
}
public static void main(String[] args) {
maopaoSort(array);
}
}
運(yùn)行結(jié)果：
第1輪排序后的數(shù)組為: [1, 0, 2, 3, 4, 5]
第2輪排序后的數(shù)組為: [0, 1, 2, 3, 4, 5]
第3輪排序后的數(shù)組為: [0, 1, 2, 3, 4, 5]
本輪中的兩兩比較未發(fā)生元素互換，排序已經(jīng)完成啦
五.冒泡排序的時(shí)間復(fù)雜度
冒泡排序是一種用時(shí)間換空間的排序方法，最壞情況是把順序的排列變成逆序，或者把逆序的數(shù)列變成順序。在這種情況下，每一次比較都需要進(jìn)行交換運(yùn)算。舉個(gè)例子來(lái)說(shuō)，一個(gè)數(shù)列 5 4 3 2 1 進(jìn)行冒泡升序排列
第一輪的兩兩比較，需要比較4次；得到 4 3 2 1 5
第二輪的兩兩比較，需要比較3次；得到 3 2 1 4 5
第三輪的兩兩比較，需要比較2次；得到 2 1 3 4 5
第四輪的兩兩比較，需要比較1次；得到 1 2 3 4 5
所以總的比較次數(shù)為 4 + 3 + 2 + 1 = 10次
對(duì)于n位的數(shù)列則有比較次數(shù)為 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2，這就得到了最大的比較次數(shù)。
而O(N^2)表示的是復(fù)雜度的數(shù)量級(jí)。舉個(gè)例子來(lái)說(shuō)，如果n = 10000，那么 n(n-1)/2 = (n^2 - n) / 2 = (100000000 - 10000) / 2，相對(duì)10^8來(lái)說(shuō)，10000小的可以忽略不計(jì)了，所以總計(jì)算次數(shù)約為0.5 * N^2。用O(N^2)就表示了其數(shù)量級(jí)（忽略前面系數(shù)0.5）。
綜上所述，冒泡排序的時(shí)間復(fù)雜度為：O(n²)
