JavaScript实现经典排序算法之冒泡排序

JavaScript实现经典排序算法之冒泡排序

什么是冒泡排序？

冒泡排序是一种简单的排序算法，从序列左侧开始比较两个相邻的元素，如果顺序不对就交换位置，直到序列末尾，这样一次遍历后，序列最后一个元素就是当前序列最大值。然后对剩余序列重复上述过程，直到整个序列有序。

算法实现

我们来看看如何用JavaScript实现冒泡排序。

function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

代码中的bubbleSort函数接受一个数组作为参数，然后用双重循环实现冒泡排序的过程。外层循环控制比较的趟数，内层循环控制每趟比较的次数。

在内层循环中，比较相邻两个元素，如果前一个元素比后一个元素大，就交换两个元素的位置，直到序列末尾。经过一次循环，序列中最大的元素就被排在了序列的最后。

接着，外层循环将比较的范围缩小1个元素，即不再比较已经排好序的元素。重复上述过程，直到整个序列有序。

让我们看看一些数组排序示例。

示例

示例1：

var arr = [5, 1, 4, 2, 8];
var sortedArr = bubbleSort(arr);
console.log(sortedArr);  // [1, 2, 4, 5, 8]

如上所示，arr数组中包含5个元素，即要排序的序列。在排序后，sortedArr数组中的元素按从小到大的顺序排列。

示例2：

我们还可以用冒泡排序来对一个表格的行进行排序。下面是一个HTML表格示例：

<table>
  <thead>
    <tr>
      <th>ID</th>
      <th>姓名</th>
      <th>年龄</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>1</td>
      <td>张三</td>
      <td>23</td>
    </tr>
    <tr>
      <td>2</td>
      <td>李四</td>
      <td>25</td>
    </tr>
    <tr>
      <td>3</td>
      <td>王五</td>
      <td>21</td>
    </tr>
    <tr>
      <td>4</td>
      <td>赵六</td>
      <td>27</td>
    </tr>
    <tr>
      <td>5</td>
      <td>钱七</td>
      <td>22</td>
    </tr>
  </tbody>
</table>

我们可以编写以下代码，在点击表头的姓名列时，对表格的行按姓名的字母顺序（从小到大）进行排序：

var tbody = document.querySelector('tbody');
var nameTh = document.querySelector('th:nth-of-type(2)');
nameTh.addEventListener('click', function() {
  var rows = tbody.querySelectorAll('tr');
  var len = rows.length;
  for (var i = 0; i < len - 1; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      var currentName = rows[j].querySelector('td:nth-of-type(2)').textContent;
      var nextName = rows[j + 1].querySelector('td:nth-of-type(2)').textContent;
      if (currentName > nextName) {
        tbody.insertBefore(rows[j + 1], rows[j]);
      }
    }
  }
});

代码解释：

我们首先通过document.querySelector方法选中了表格的tbody和姓名列的表头。

我们给姓名列的表头添加一个click事件监听器，在每次单击表头时触发排序操作。

在事件处理程序中，使用querySeletorAll方法选中了所有的表格行tr，并通过双重循环实现冒泡排序的过程。

排序过程中，我们从每一行中提取姓名的字母顺序进行比较，然后使用insertBefore方法对其进行插入排序。

总结

以上就是JavaScript实现冒泡排序的完整攻略，我们通过详细讲解了算法的原理和实现过程，并给出了两个示例。

冒泡排序虽然简单，但是在实际应用中并不常用，因为其时间复杂度较高，在大规模数据中排序速度较慢。因此，我们更多地使用快速排序、归并排序、堆排序等快速排序算法。