java冒泡排序算法怎么用

這篇文章主要講解了“java冒泡排序算法怎么用”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“java冒泡排序算法怎么用”吧！

       冒泡排序是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。 

1.1 算法描述

• 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；

• 對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)；

• 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；

• 重復(fù)步驟1~3，直到排序完成。

  
  

 1/**
 2 * @description: 冒泡排序
 3 * 冒泡排序只會(huì)操作相鄰的兩個(gè)數(shù)據(jù)。每次冒泡操作都會(huì)對(duì)相鄰的兩個(gè)元素進(jìn)行比較，看是否滿足大小關(guān)系要求。
 4 * 如果不滿足就讓它倆互換。一次冒泡會(huì)讓至少一個(gè)元素移動(dòng)到它應(yīng)該在的位置，重復(fù)n 次，
 5 * 就完成了 n 個(gè)數(shù)據(jù)的排序工作。
 6 **/
 7public class BubbleSort {
 8    public void bubbleSort(Integer[] arr, int n) {
 9        if (n <= 1) return;       //如果只有一個(gè)元素就不用排序了
10
11        for (int i = 0; i < n; ++i) {
12            // 提前退出冒泡循環(huán)的標(biāo)志位,即一次比較中沒(méi)有交換任何元素，這個(gè)數(shù)組就已經(jīng)是有序的了
13            boolean flag = false;
14            for (int j = 0; j < n - i - 1; ++j) {        //此處你可能會(huì)疑問(wèn)的j<n-i-1，因?yàn)槊芭菔前衙枯喲h(huán)中較大的數(shù)飄到后面，
15                // 數(shù)組下標(biāo)又是從0開(kāi)始的，i下標(biāo)后面已經(jīng)排序的個(gè)數(shù)就得多減1，總結(jié)就是i增多少，j的循環(huán)位置減多少
16                if (arr[j] > arr[j + 1]) {        //即這兩個(gè)相鄰的數(shù)是逆序的，交換
17                    int temp = arr[j];
18                    arr[j] = arr[j + 1];
19                    arr[j + 1] = temp;
20                    flag = true;
21                }
22            }
23            if (!flag) break;//沒(méi)有數(shù)據(jù)交換，數(shù)組已經(jīng)有序，退出排序
24        }
25    }

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

• 如果我們的數(shù)據(jù)正序，只需要走一趟即可完成排序。所需的比較次數(shù)C和記錄移動(dòng)次數(shù)M均達(dá)到最小值，

即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的時(shí)間復(fù)雜度為O(n)。

• 如果很不幸我們的數(shù)據(jù)是反序的，則需要進(jìn)行n-1趟排序。每趟排序要進(jìn)行n-i次比較(1≤i≤n-1)，且每次比較都必須移動(dòng)記錄三次來(lái)達(dá)到交換記錄位置。在這種情況下，比較和移動(dòng)次數(shù)均達(dá)到最大值：

即最壞情況下時(shí)間復(fù)雜度為O(n2)【n的平方】;

• 所以，冒泡排序總的平均時(shí)間復(fù)雜度為：O(n2) 。

感謝各位的閱讀，以上就是“java冒泡排序算法怎么用”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)java冒泡排序算法怎么用這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！