冒泡排序是一个非常常见的排序算法，对于一个数组，每趟排序时依次比较两个相邻的数，如果他们的顺序错误就交换两数位置。所以，没趟排序都会排好一个数字，下一轮排序就可以少比较一个数字，直到只剩下一个数字，就全部排序好了。
举个例子，假设最终需要的结果是从小到大排列，对于数组：
[3, 5, 2, 6, 1, 7, 4]
第一趟排序的过程：
[3, 5, 2, 6, 1, 7, 4]// 比较过程：
// 1. 比较 3 和 5，发现顺序正确，则不变
[3, 5, 2, 6, 1, 7, 4]
// 2. 比较 5 和 2，发现顺序错误，交换位置
[3, 2, 5, 6, 1, 7, 4]
// 3. 比较 5 和 6，发现顺序正确，不变
[3, 2, 5, 6, 1, 7, 4]
// 4. 比较 6 和 1，发现顺序错误，交换位置
[3, 2, 5, 1, 6, 7, 4]
// 5. 比较 6 和 7，发现顺序正确，不变
[3, 2, 5, 1, 6, 7, 4]
// 5. 比较 7 和 4，发现顺序错误，交换位置
[3, 2, 5, 1, 6, 4, 7]
排序过程中，所有相邻数字对都比较了一遍，比较的过程中，实质上是比较的相邻位置，而不管位置上的数字是否在上一次比较中交换了位置，只管一个一个位置的比较下去，数字顺序错误就把数字位置交换。经过这趟排序，发现最大的数字 7 已经排到了最后一个位置，所以下一趟排序就不需要再比较最后一个位置的数字了。
第二趟排序过程：
// 经过第一趟排序后的数组
[3, 2, 5, 1, 6, 4, 7]// 比较过程：
// 1. 比较 3 和 2，发现顺序错误，交换位置
[2, 3, 5, 1, 6, 4, 7]
// 2. 比较 3 和 5，发现顺序正确，不变
[2, 3, 5, 1, 6, 4, 7]
// 3. 比较 5 和 1，发现顺序错误，交换位置
[2, 3, 1, 5, 6, 4, 7]
// 4. 比较 5 和 6，发现顺序正确，不变
[2, 3, 1, 5, 6, 4, 7]
// 5. 比较 6 和 4，发现顺序错误，交换位置
[2, 3, 1, 5, 4, 6, 7]
// 最后一个数字不用比较
经过第二趟排序后，数字 6 也排到了正确的位置。第三趟排序时，最后两位数字都不用比较了。
每一趟排序，都会把剩余数字中最大的排到最后面。后面的排序过程就不再分析了。清楚了排序过程，写代码来排序就很简单了，代码如下：
function bubbleSort(arr) {
var arr = arr.slice(0); // 保证排序后原数组不变
var len = arr.length;
var tmp;// 只需要进行 len – 1 趟排序
// 因为只剩下一个数字时不用再比较了
for (var i = 0; i < len – 1; ++i) {
// 每一趟都会排序好一个数字
// 所以每趟只需排 len – i 个数字
for (var j = 1; j < len – i; ++j) {
// 如果右边的数比左边的小
// 就交换位置
if (arr[j] < arr[j-1]) {
tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}
}
// 这里可以打印出每趟排序的结果
// 以便观察排序过程
// console.log(arr);
}
return arr;
}
原创文章，作者：guozi，如若转载，请注明出处：https://www.sudun.com/ask/80444.html
