javascript实践教程-09-冒泡排序

冒泡排序算法详解与JavaScript实现

冒泡排序（Bubble Sort）是一种基础的交换排序算法，其核心思想是通过多次遍历数组，每次比较相邻的两个元素，如果顺序错误就交换它们的位置，从而将较大的元素逐步“冒泡”到数组的末尾。

1. 比较相邻元素：从数组的第一个元素开始，依次比较相邻的两个元素。
2. 交换位置：如果前一个元素比后一个元素大（假设是升序排序），则交换它们的位置。
3. 重复遍历：对数组进行多轮遍历，每一轮都将当前未排序部分的最大元素“冒泡”到正确的位置。
4. 优化：如果在某一轮遍历中没有发生任何交换，说明数组已经有序，可以提前结束排序。

以下是使用JavaScript实现冒泡排序的代码：

1. 外层循环：for (let i = 0; i < len - 1; i++)

   控制排序的轮数，总共需要 len - 1 轮（因为最后一个元素会自动到位）。

2. 内层循环：for (let j = 0; j < len - 1 - i; j++)

   控制每轮比较的次数，随着轮数的增加，比较的次数逐渐减少（因为每轮都会将一个最大元素放到正确位置）。

   len - 1 - i 是因为每轮结束后，数组末尾的 i 个元素已经是有序的，无需再比较。

3. 交换元素：

   如果 arr[j] > arr[j + 1]，则交换两个元素的位置，确保较小的元素向前移动。

4. 优化：

   可以在外层循环中添加一个标志位，如果在某一轮中没有发生交换，说明数组已经有序，可以提前退出循环。

1. 插入排序：

   思路：将数组分为已排序和未排序两部分，每次从未排序部分取出第一个元素，插入到已排序部分的正确位置。

   实现：

   function insertionSort(arr) { for (let i = 1; i < arr.length; i++) { let key = arr[i]; let j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } return arr;}

2. 选择排序：

   思路：每次从未排序部分选择最小的元素，放到已排序部分的末尾。

   实现：

   function selectionSort(arr) { for (let i = 0; i < arr.length - 1; i++) { let minIndex = i; for (let j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } if (minIndex !== i) { let temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } return arr;}

3. 平衡字符串：

   思路：平衡字符串是指字符串中'L'和'R'的数量相等。可以通过遍历字符串，统计'L'和'R'的数量，当数量相等时分割字符串。

   实现：

   function balancedStringSplit(s) { let count = 0; let balance = 0; for (let char of s) { if (char === 'L') balance++; else balance--; if (balance === 0) count++; } return count;}

冒泡排序是一种简单但效率较低的排序算法，适合小规模数据的排序。通过理解其基本思想和实现方式，可以更好地掌握其他排序算法。同时，练习插入排序、选择排序和平衡字符串等问题，有助于提升编程能力和逻辑思维。