哈嘍，我是程式員大鵬，
最近在招聘程序中，發現好多小伙伴最基礎的一些演算法回答，接下來會做一個系列，把基礎的排序等演算法采用影片的形式做決議，
這是第一篇冒泡排序，
冒泡排序思想
冒泡排序(Bubble Sort)是一種交換排序，基本思想是兩兩比較相鄰記錄，如果逆序則進行交換，直到沒有逆序的記錄為止，
冒泡演算法有很多種實作方式，我們在這里只列舉出來兩種實作方式來講解冒泡排序，
排序原理
- 比較相鄰的元素，如果第一個比第二個大，就交換他們兩個，
- 對每一對相鄰元素做同樣的作業，從開始第一對到結尾的最后一對，在這一點，最后的元素應該會是最大的數，
- 對所有的元素重復以上的步驟，除了最后一個，
- 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較，
排序影片
排序實作
簡單的冒泡排序
public static void sort(int[] arg) {
//冒泡排序
for (int i = 0; i < arg.length - 1; i++) {
for (int j = arg.length - 1; j > i; j--) {
if (arg[j] < arg[j - 1]) {//交換兩個數字
int temp = arg[j];
arg[j] = arg[j - 1];
arg[j - 1] = temp;
}
}
}
}
上面的代碼是根據影片進行的實作，假設我們的資料為{7,5,1,3,2,6}，當i=0時，進行第一輪排序，變數j由5開始一直回圈到1，逐個進行兩兩相鄰數字的比較，最后將數字最小的1排到第一位，當i=1時，進行第二輪排序，變數j由5開始一直回圈到2，逐個進行兩兩相鄰數字的比較，最后將數字2排到第二位，依次進行i的下一輪比較，最終實作了資料的排序，
在這個程序中，由于數字像是浮起來的泡泡，所以稱之為冒泡排序，
排序優化
上面的演算法還有優化的空間嗎？我們來看下面的這組資料，比如{6,5,4,3,1,2}，經過一輪排序已經變為了{6,5,4,3,2,1}，第二輪開始排序之后，還是{6,5,4,3,2,1}，數字的順序是沒有改變的，說明數字已經處于排序的狀態了，則沒有必要進行排序，所以還可以進行優化，代碼如下：
public void sort(int[] arg) {
//冒泡排序優化
for (int i = 0; i < arg.length - 1; i++) {
boolean isSorted = true;
for (int j = arg.length - 1; j > i; j--) {
if (arg[j] < arg[j - 1]) {//交換兩個數字
int temp = arg[j];
arg[j] = arg[j - 1];
arg[j - 1] = temp;
isSorted = false;//如果有資料交換，則isSorted為false
}
}
if (isSorted) {//isSorted為true，說明沒有進行資料交換，資料已經有序，則退出回圈
break;
}
}
}
這樣經過上面的優化，冒泡排序會避免在資料已經有序的情況下繼續進行資料回圈比較，性能得到了一定的提升，
冒泡排序的復雜度分析
資料正序的情況
比如資料為{6,5,4,3,2,1}，按照優化后的演算法，只需要，只會進行5次比較，也就是n-1次的比較，所以時間復雜度為O{n}
資料逆序的情況
最壞的情況就是全部資料都是逆序，比如{6,5,4,3,2,1}，(n(n-1))/2次的資料操作和資料移動，所以總的時間復雜度為 (O(n2))
綜合上面的情況，冒泡排序的時間復雜度為(O(n2))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/69375.html
標籤：Java
下一篇：JVM中字串的秘密