簡明算法: 冒泡排序(javascript描述)

liukai90 發(fā)布于2019-08-22 15:09 / 2475人閱讀

懶惰了很久，人有點(diǎn)生銹，所以寫個(gè)算法系列讓自己腦筋活躍起來。

（所有范例一律從小到大排序）

冒泡排序

給定數(shù)組：

var list = [ 54, 26, 93, 17, 77, 31, 44, 88, 55, 20 ];

算法描述：

將第一個(gè)元素與第二個(gè)元素對比，此時(shí)第一個(gè)元素比第二個(gè)元素大，交換他們，這樣較大的元素就位于第二個(gè)位置了;

list = [ 26, 54, 93, 17, 77, 31, 44, 88, 55, 20 ];

將第二個(gè)元素與第三個(gè)元素對比，此時(shí)第二個(gè)元素比第三個(gè)元素小，保持原樣不變;

list = [ 26, 54, 93, 17, 77, 31, 44, 88, 55, 20 ];

重復(fù)上面的步驟，直到最后我們用倒數(shù)第二個(gè)元素與倒數(shù)第一個(gè)元素相比之后，經(jīng)過第一輪排序，最大的元素93被移動(dòng)到了數(shù)組最后；

list = [ 26, 54, 17, 77, 31, 44, 88, 55, 20, 93 ];

然后我們重復(fù)1，2，3步驟；經(jīng)過第二輪我們會(huì)找到次大的元素排在倒數(shù)第二位，即88被移動(dòng)到了數(shù)組倒數(shù)第二位；

list = [ 26, 17, 54, 31, 44, 77, 55, 20, 88, 93 ];

再次重復(fù)直到整個(gè)數(shù)組有序;

第1輪: [ 26, 54, 17, 77, 31, 44, 88, 55, 20, 93 ]
第2輪: [ 26, 17, 54, 31, 44, 77, 55, 20, 88, 93 ]
第3輪: [ 17, 26, 31, 44, 54, 55, 20, 77, 88, 93 ]
第4輪: [ 17, 26, 31, 44, 54, 20, 55, 77, 88, 93 ]
第5輪: [ 17, 26, 31, 44, 20, 54, 55, 77, 88, 93 ]
第6輪: [ 17, 26, 31, 20, 44, 54, 55, 77, 88, 93 ]
第7輪: [ 17, 26, 20, 31, 44, 54, 55, 77, 88, 93 ]
第8輪: [ 17, 20, 26, 31, 44, 54, 55, 77, 88, 93 ]
第9輪: [ 17, 20, 26, 31, 44, 54, 55, 77, 88, 93 ]

算法實(shí)現(xiàn):

function bubble(list) {
  // 開啟length-1輪循環(huán)，因?yàn)樽詈笠惠喼皇Ｒ粋€(gè)元素，沒必要比較
  for (let i = 0; i < list.length - 1; i++) {
    // 兩兩對比，每次循環(huán)時(shí)j的取值上限需要舍去尾部已經(jīng)有序的數(shù)據(jù)，所以length-1-i
    for (let j = 0; j < list.length - 1 - i; j++) {
      if (list[j] > list[j + 1]) {
        // ES6語法 交換元素
        [list[j], list[j + 1]] = [list[j + 1], list[j]];
      }
    }
  }
}

// 測試
var list = [ 54, 26, 93, 17, 77, 31, 44, 88, 55, 20 ];
bubble(list);
console.log(list);
// [ 17, 20, 26, 31, 44, 54, 55, 77, 88, 93 ]