还记得第一次用Javascript完成冒泡排序的时候,那种激动的心情溢于言表。但每次为了加深记忆重复编写冒泡排序方法的时候总是会因为其抽象的双层for循环卡住,我甚至一度怀疑自己到底是学会了这种排序方法呢,还是只是像抄别人数学作业那样,仅仅只是抄会了。后来又了解到了快速排序,与其说冒泡排序让我揭开了算法神秘的面纱,倒不如说是快速排序让我真正理解了何为排序。因此还是把这两者的区别以markdown的方式小小总结一下。
冒泡排序
冒泡排序是一种简单的排序算法,它重复遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的,直到没有再需要交换的元素为止。
特点
- 简单直观:易于理解和实现。
- 时间复杂度:平均和最坏情况下都是 (O(n^2)),但冒泡排序多数时候会表现更差。
- 稳定性:由于相等的元素不会交换位置,冒泡排序是稳定的排序算法。
示例代码
function sortLikeBubble(arr) {
let len = arr.length;
for (let i = 0; i < len - 1; i++) { //第一层循环,决定至多要进行len-1次排序
for (let j = 0; j < len - 1 - i; j++) { //第二层循环,比较后的实际位置交换,保证大的元素总是在最后
if (arr[j] > arr[j + 1]) {
// Swap
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
快速排序
快速排序是一种分治的排序算法,它将数列分为两个子数列,然后递归地将子数列排序。
特点
- 高效:对于大规模数据排序表现良好。
- 时间复杂度:平均情况下是 (O(n \log n)),最坏情况是 (O(n^2)),但后者非常罕见。
- 不稳定:在某些情况下可能会改变相等元素的相对顺序。
示例代码
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
let pivotIndex = Math.floor(arr.length / 2); //中心点的index
let pivot = arr.splice(pivotIndex, 1)[0]; //中心元素
let left = []; //定义左右两个数组
let right = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]); //比中心元素小,加入左边的数组
} else {
right.push(arr[i]); //比中心元素大,加入右边的数组
}
}
return quickSort(left).concat([pivot], quickSort(right)); //这是我第一次发现递归的奇妙
}
总结
- 性能:快速排序通常比冒泡排序更高效,特别是在处理大量数据时。
- 简易度:冒泡排序算法结构简单,易于理解和实现;而快速排序虽然效率高,但算法更复杂。
- 稳定性:冒泡排序是稳定的排序算法,而快速排序则不是。
这样一对比,快速排序简直香爆了,虽然其中用到了递归,但明显从概念理解上比冒泡排序更好理解,且时间复杂度也更低。虽然实际开发中我会去用Array.prototype.sort(),但这种总结的意义在于,我能更好地去感受算法的奇妙之处,它其实没有我想象的那么可怕,我们有时只需要一点点的耐心就好。