冒泡
思路
- 比拟所有的相邻元素，如果第一个比第二个大，则替换它们
- 一轮下来，能够保障最初一个数是最大的
- 执行n-1轮，就能够实现排序（例如第二轮，能够保障倒数第二个数是数据中第二大的）
代码实现
数组原型上的办法和this
<script> Array.prototype.bubbleSort = function () { console.log(this); //[5, 4, 3, 2, 1]; } const arr = [5, 4, 3, 2, 1]; arr.bubbleSort() </script>获取数组中的所有相邻元素
<script> Array.prototype.bubbleSort = function () { for(let j =0;j<this.length-1;j++){ console.log(this[j],this[j+1]); //5 4 //4 3 //3 2 //2 1 } } const arr = [5, 4, 3, 2, 1]; arr.bubbleSort() </script>比拟前后数大小，替换地位
- 如果前一个数比后一个数要大，则替换他们的地位
- 第一轮循环下来，数组中的最初一个数就是数组中第一大的数,(前面类推)
<script> Array.prototype.bubbleSort = function () { for(let j =0;j<this.length-1;j++){ if(this[j] > this[j+1]){ let temp = this[j] this[j] = this[j+1] this[j+1] = temp } } } const arr = [5, 4, 3, 2, 1]; arr.bubbleSort() console.log('arr',arr); //[4, 3, 2, 1, 5] </script>所有元素排完序
执行n-1轮循环，就能够对数组中所有的元素排完序
<script> Array.prototype.bubbleSort = function () { for (let i = 0; i < this.length - 1; i++) { for (let j = 0; j < this.length - 1; j++) { if (this[j] > this[j + 1]) { let temp = this[j] this[j] = this[j + 1] this[j + 1] = temp } } } } const arr = [5, 4, 3, 2, 1]; arr.bubbleSort() console.log('arr', arr); //[1, 2, 3, 4, 5] </script>优化(残缺代码)
例如:第二轮循环下来，倒数的第二个数就是第二大的数，所以就不必去循环数组中第二大前面的数
<script> Array.prototype.bubbleSort = function () { for (let i = 0; i < this.length - 1; i++) { for (let j = 0; j < this.length - 1-i; j++) { if (this[j] > this[j + 1]) { let temp = this[j] this[j] = this[j + 1] this[j + 1] = temp } } } } const arr = [5, 4, 3, 2, 1]; arr.bubbleSort() console.log('arr', arr); //[1, 2, 3, 4, 5] </script>时空复杂度
工夫复杂度
O(n^2)，因为2个嵌套循环
空间复杂度
空间复杂度就是在替换元素时那个长期变量所占的内存空间；
最优的空间复杂度就是开始元素程序曾经排好了，则空间复杂度为：0；
最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；
均匀的空间复杂度为：O(1)；