关于算法:算法排序篇

冒泡

思路

1. 比拟所有的相邻元素，如果第一个比第二个大，则替换它们
2. 一轮下来，能够保障最初一个数是最大的
3. 执行 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>

比拟前后数大小，替换地位

1. 如果前一个数比后一个数要大，则替换他们的地位
2. 第一轮循环下来，数组中的最初一个数就是数组中第一大的数,(前面类推)

  <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)；