算法|排序算法-冒泡排序

vlambda
2021-04-30

算法|排序算法-冒泡排序

概述

冒泡排序是很多初学编程的程序员接触到的第一种排序算法，它也是所有排序算法中最简单的算法，但是它是众多排序算法中，排序效率最差的一个。

冒泡排序比较所有相邻的两个项，如果第一个比第二个大，则交换它们。元素项向上移动至正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。

冒泡排序全解析

假如有这样一组数值不等的数组，将天平放在数组序列的右端，并比较天平左右的数字。

在这种情况下，我们将比较7和6。

冒泡排序-图解过程1

比较后，如果两个树中，右边的数字较小，则交换这两个数字的位置。

因为6比7小，所以这两个数字要进行交换。

算法|排序算法-冒泡排序

冒泡排序-图解过程2

比较完成后，天平往前左移一个位置。

再重复比较数字的操作

因为6大于4，所以不需要进行交换。

算法|排序算法-冒泡排序

冒泡排序-图解过程3

比较完成后，天平再接着往前左移一个位置。

不断重复比较两个数字和天平往前左移一个位置的操作……

直到天平移动到左端。

算法|排序算法-冒泡排序

冒泡排序-图解过程4

此时最左端的数字已经排序好了

算法|排序算法-冒泡排序

冒泡排序-图解过程5

再将天平返回右端，重复之前相同的操作，对其他数组进行排序(忽略已经排序好的数字)

冒泡排序-图解过程6

每重复一轮相同的操作，左侧会有一个数字被排序好，直到所有数字都被排序。

冒泡排序-图解过程7

此时，这一组数值不等的数组，已经被排序完成。

代码实现冒泡排序

为方便排序时的相邻数字比较或交换，定义一些比较和交换用的常量和方法

// 比较用的常量对象(保证代码优雅)export const Compare = { LESS_THAN: -1, // 如果第一个元素小于第二个元素，它就返回-1 BIGGER_THAN: 1, // 如果第一个元素大于第二个元素，它就返回1 EQUALS: 0 // 如果元素有相同的引用，它就返回 0};// 比较用的方法export function defaultCompare(a, b) { // 如果元素有相同的引用，它就返回 0 if (a === b) { return Compare.EQUALS; } // 如果第一个元素小于第二个元素，它就返回-1,否之返回1 return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;}/** * 交换函数 * @param {*} array 传入需要交换的数组(这里传入堆) * @param {*} a 传入要交换的节点A * @param {*} b 传入要交换的节点B */export function swap(array, a, b) { // ES5写法(性能较好) /* const temp = array[a]; // 要交换数组中的两个值，我们需要一个辅助变量来复制要交换的第一个元素 array[a] = array[b]; // 然后，将第二个元素赋值到第一个元素的位置 array[b] = temp; */ // 最后，将复制的第一个元素的值覆盖到第二个元素的位置 // ES6写法(性能较差) https://bugzilla.mozilla.org/show_bug.cgi?id=1177319 [array[a], array[b]] = [array[b], array[a]];}

实现冒泡排序

/** * 冒泡排序 * 冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。 * @param {array} array 要进行排序的数组 * @param {function} compareFn // 比较用的方法，默认为defaultCompare * @returns {array} 返回排序后的数组 */export function bubbleSort(array, compareFn = defaultCompare) { const { length } = array; // 声明一个名为length的变量，用来存储数组的长度 for (let i = 0; i < length; i++) { // 外循环，冒泡排序每一趟只能确定将一个数归位，所以数组中的每一项都需要经过一轮排序，轮数和数组长度一致 // console.log('--- '); for (let j = 0; j < length - 1; j++) { // 内循环，用当前项与下一项做比较，对n个数进行排序，只用进行n-1趟 // console.log('compare ' + array[j] + ' with ' + array[j + 1]); if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) { // 如果这两项顺序不对（当前项比下一项大） // console.log('swap ' + array[j] + ' with ' + array[j + 1]); swap(array, j, j + 1); // 则交换它们(位置为j+1的值将会被换置到位置j处) } } } // 返回排序后的数组 return array;}

上述的冒泡排序算法，并没有忽略已经排序好的数字，导致对已经排序好的数字进行了较多无用的对比判断。

所以可以对算法进行改进，对比时忽略已经排序好的数字:

/** * 改进后的冒泡排序 * 冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。 * @param {array} array 要进行排序的数组 * @param {function} compareFn // 比较用的方法，默认为defaultCompare * @returns {array} 返回排序后的数组 */export function modifiedBubbleSort(array, compareFn = defaultCompare) { const { length } = array; // 声明一个名为length的变量，用来存储数组的长度 for (let i = 0; i < length; i++) { // 外循环，冒泡排序每一趟只能确定将一个数归位，所以数组中的每一项都需要经过一轮排序，轮数和数组长度一致 // console.log('--- '); for (let j = 0; j < length - 1 - i; j++) { // 内循环，用当前项与下一项做比较，对n个数进行排序，只用进行n-1趟,再从内循环减去外循环中已跑过的轮数i(已跑过轮数的数已归位，无须再进行比较) // console.log('compare ' + array[j] + ' with ' + array[j + 1]); if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) { // 如果这两项顺序不对（当前项比下一项大） // console.log('swap ' + array[j] + ' with ' + array[j + 1]); swap(array, j, j + 1); // 则交换它们(位置为j+1的值将会被换置到位置j处) } } } // 返回排序后的数组 return array;}