冒泡排序

依次比较相邻的数据，将小数据放在前，大数据放在后。即第一趟先比较第1个和第2个数，大数在后，小数在前，再比较第2个数与第3个数，大数在后，小数在前，直到将最大的数移动到最后一个位置。 第二趟则将次大的数移动到倒数第二个位置，...直到将第n大的数移动到第一个输的位置，便完成排序。

算法逻辑

冒泡排序的核心操作是对两个数据进行比较和进行交换。具体做法如下（假设需要排序的数据存在一个数组变量array里面，从左往右，从小到大排序）：

1. 设置变量 i=0,j=i+1 ;
2. 取 a=array[i] ;
3. 从数组第j个元素开始，取 b=array[j] ;
4. 比较 a>b ?,如果 a>b 为真,交换 a 和 b 对应数组的值，否则不做交换。继续循环， j+1 ;
5. 当 j>=array.length 时，结束循环，否则继续 3-5 步。
6. i=i+1 ;
7. 重复操作 2-6 直到i>=array.length,算法结束，得到的array的值就是排序完成的数组。

代码实现

/**
 * 冒泡,升序
 * @param  {array} array  数值数组
 * @return {array}        排好序的数据，不该变原数组
 */
function bubbleSort (array) {
  let tempArray = [].concat(array)
  let i = 0;
  let j = 0;
  let len = tempArray.length
  for (i = 0; i < len; i++) {
    for (j = i + 1; j < len; j++) {
      let a = tempArray[i];
      let b = tempArray[j];
      if (a > b) {
        tempArray[i] = b;
        tempArray[j] = a;
      }
    }
  }
  return tempArray;
}

bubbleSort([9,8,7,6,5,4,3,2,1]);

总结

冒泡排序的核心操作是比较和数据交换，时间复杂为O(n^2)。算法稳定，但是效率并不高。

TIP

算法视频演示 (opens new window)