66. 冒泡排序如何实现？如何优化？

vlambda
2020-09-18

66. 冒泡排序如何实现？如何优化？

冒泡排序也是面试中经常看到的问题之一，以下来实现最基本的冒泡排序算法：

/** * 冒泡排序算法（原数组本身也受排序影响）--升序排序 * @param {Array} array 待排序数组 * @return 返回排序后的数组 */function bubbleSort(array) { for (let i = 0, len = array.length - 1; i < len; i++) { for (let j = 0; j < len - i; j++) { if (array[j] > array[j + 1]) { const temp = array[j] array[j] = array[j + 1] array[j + 1] = temp } } }
 return array}
const arr = [3, 9, 1, 4, 2, 8, 6, 5, 7]const result = bubbleSort(arr)console.log('计算结果：', JSON.stringify(result))// 计算结果：[1,2,3,4,5,6,7,8,9]

以上是常规实现冒泡排序的写法，其时间复杂度最好的情况是 O(n)，最坏的情况是 O(n^2)，平均时间复杂度是 O(n^2)。

当然，如果一个数组本身已经是升序排序了，还通过上述冒泡排序实现方法进行判断的话，则元素间的重复比较很冗余，所以存在可优化的余地。

我们可以将某一轮最大值放到该轮最后位置后，将该轮最后一个操作的位置作为下一轮的终点，继续进行下一轮的排序比较，这样可以减少不必要的一些冒泡：

/** * 冒泡排序算法优化（原数组本身也受排序影响）--升序排序 * @param {Array} array 待排序数组 * @return 返回排序后的数组 */function bubbleSort(array) { let i = array.length - 1
 while (i > 0) { let pos = 0 for (let j = 0; j < i; j++) { if (array[j] > array[j + 1]) { pos = j const temp = array[j] array[j] = array[j + 1] array[j + 1] = temp } } i = pos } return array}
const arr = [3, 9, 1, 4, 2, 8, 6, 5, 7]const result = bubbleSort(arr)console.log('计算结果：', JSON.stringify(result))// 计算结果：[1,2,3,4,5,6,7,8,9]