JavaScript 算法进阶

认识大O表示法

1. 例子：

   1. 比如一般公司的规模可以分为小型企业/中型企业/大型企业。
   2. 在不说明具体员工人数和占地面积的情况下，我们可以通过这样的 大概念 来描述企业的规模。

2. 大O表示法：

   1. 在算法效率的表示中，我们也可以用这种大的概念来表示。
   2. 在计算机中，这种粗略的表示法，被称为大O表示法。
   3. 在数据量发生变化的时候，算法的效率也会发生改变。

3. 常见的大O表示法表现形式：

符号	名称
O(1)	常数的
O(log(n))	对数的
O(n)	线性的
O(nlog(n))	线性和对数乘积
O($n^2$)	平方
O($2^n$)	指数的

4. 推导大O表示法的方式：
   1. 用常量1取代运行时间中所有的加法常量。
   2. 在修改后的运行次数函数中，只保留最高阶项。
   3. 如果最高存在且不为1，则去除这个项相乘的常数。

常用排序方法示例

1. 冒泡排序
   • 代码实现

     ArrayList.prototype.bubbleSort = function(array) {
         const len = array.length;
     
         for(let i = len - 1; i >= 0; i--){
             for (let j = 0; j < len - 1; j++) {
                 // 两层循环，对比j位置和j+1位置的元素大小，如果前一位比后一位大则交换
                 if (array[j] > array[j + 1]) {
                     let tamp = array[j];
                     array[j] = array[j + 1];
                     array[j + 1] = tamp;
                 }
             }
         }
     }
     

2. 选择排序
   • 代码实现

     ArrayList.prototype.selectionSort = function(array) {
         const len = array.length;
     
         // 外层循环，从0位置开始获取数据
         for(let i = 0; i < len - 1; i++){
             // 内层循环，从i+1位置开始，和后面的数据进行比较
             let min = i;
             for (let j = min + 1; j < len; j++) {
                 if (array[min] > array[j]) {
                     min = j;
                 }
             }
             let temp = array[min];
             array[min] = array[i];
             array[i] = temp;
         }
     }
     

3. 插入排序
   • 代码实现

     ArrayList.prototype.insertionSort = function(array) {
         const len = array.length;
     
         // 外层循环，从第一个位置开始获取数据，向前面局部有序的进行插入
         for(let i = 0; i < len; i++) {
             // 内层循环，获取i位置的元素，和前面的数据依次进行比较
             let temp = array[i];
             let j = i;
             while(array[j - 1] > temp && j > 0) {
                 array[j] = array[j -1];
                 j--;
             }
             // 将j位置的数据，放置temp 
             array[j] = temp;
         }
     }
     

4. 希尔排序
   • 代码实现

     ArrayList.prototype.shellSort = function(array) {
         const len = array.length;
     
         // 初始化的增量
         let gap = Math.floor(len / 2);
     
         // gap不断的减小
         while(gap >= 1) {
             // 以gap作为间隔，进行分组，对分组进行插入排序
             for(let i = gap; i < len; i++ ){
                 let temp = array[i];
                 let j = i;
                 while(array[j - gap] > temp && j > gap - 1) {
                     array[j] = array[j - gap];
                     j -= gap;
                 }
     
                 // 将j位置的元素赋值temp
                 array[j] = temp;
             }
     
             gap = Math.floor(gap / 2);
         }
     }
     

5. 快速排序
   • 代码实现

     ArrayList.prototype.quickSort = function(array) {
         //如果排序的数组长度为1的话就直接返回原数据
         if (array.length <= 1) {
             return array
         }
         //获取索引，中间值（原数组的长度除以二，再取整）
         let index = Math.floor(array.length / 2);
         //从数组中间截取一个元素保存
         let item = array.splice(index, 1)[0];
         //新建两个新数组
         let left = [];
         let right = [];
         for (var i = 0; i < array.length; i++) {
             //遍历数组，判断每一项是否大于中间项，大于放右边数组，小于放左边数组
             array[i] < item ? left.push(array[i]) : right.push(array[i]);
         }
         //最后再递归把左边和右边的数组排序一下，再把左边数组和中间值和右边数组一起拼接返回
         return quickSort(left).concat(item, quickSort(right));
     }