常用算法

[ClimbYU]

1.冒泡排序

是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

/**
 * 
 * 冒泡排序算法的流程如下：
 *
 *  1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 *  2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
 *  3.针对所有的元素重复以上的步骤，除了最后一个。
 *  4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 * 
 * 
 */
let arr = [12, 45, 2, 32, 56, 71, 99, 5, 9, 5, 6, 1, 8, 78, 62]

function bubbleSort(arr) {
    let temp
    let num = arr.length;
    console.time('time')
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < num; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }

        }
        num = num - 1
    }
    console.timeEnd("time");
    return arr
}

console.log(bubbleSort(arr)) 
// [ 1, 2, 5, 5, 6, 8, 9, 12, 32, 45, 56, 62, 71, 78, 99 ]

时间复杂度：平均时间复杂度是O(n^2)
空间复杂度：由于辅助空间为常数，所以空间复杂度是O(1);

const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];

function bubbleSort(arr){
 console.time('time')
  for(let i = 0; i < arr.length - 1; i++){
    for(let j = 0; j < arr.length - i - 1; j++){
      if(arr[j] > arr[j + 1]){
        swap(arr, j, j+1);
      }
    }
  }
 console.timeEnd("time");
  return arr;
}

function swap(arr, i, j){
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
console.log(arr);

性能：

时间复杂度：平均时间复杂度是O(n)
空间复杂度：由于辅助空间为常数，所以空间复杂度是O(1);

2.选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。第一遍，从数组中选出最小的，与第一个元素进行交换；第二遍，从第二个元素开始，找出最小的，与第二个元素进行交换；依次循环，完成排序

let arr = [12, 45, 2, 32, 56, 71, 99, 5, 9, 5, 6, 1, 8, 78, 62, 3, 0, 4, 7, 10]

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function choiceSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                swap(arr, i, j)
            }
        }
    }
}
choiceSort(arr)
console.log(arr) //[ 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10, 12, 32, 45, 56, 62, 71, 78, 99 ]

时间复杂度：平均时间复杂度是O(n^2)，这是一个不稳定的算法，因为每次交换之后，它都改变了后续数组的顺序。

空间复杂度：辅助空间是常数，空间复杂度为O(1);

3.插入排序

function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        for (j = i; j > 0; j--) {
            if (arr[j - 1] > arr[j]) {
                swap(arr, j - 1, j)
            } else {
                break
            }
        }
    }
}
insertSort(arr)
console.log(arr)

4.快速排序

1.在数据集之中，选择一个元素作为”基准”（pivot）。
2.所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区 (partition) 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
3.对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

//1.选取第一个为基准元素
let arr = [12, 45, 2, 32, 56, 71, 99, 5, 9, 5, 6, 1, 8, 78, 62, 3, 0, 4, 7, 10]


function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let temp = arr[0];
    const left = [];
    const right = [];
    //从i = 1开始
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] > temp) {
            right.push(arr[i]);
        } else {
            left.push(arr[i]);
        }
    }
    return quickSort(left).concat([temp], quickSort(right));
}
console.log(quickSort(arr))
//2.选取中间元素为基准元素
function quickSort(arr) {　　
    if (arr.length <= 1) {
        return arr;
    }　　
    var pivotIndex = Math.floor(arr.length / 2);　　
    var pivot = arr.splice(pivotIndex, 1)[0];　　
    var left = [];　　
    var right = [];　　
    for (var 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));
}

5.斐波那契额数列

/**
 * 
 * 斐波那契额数列
 * f(1) = 1 f(2) = 1
 * f(n) = f(n-1) + f(n-2)  (n >= 3)
 * 
 */

 function fibonacci(n){
    
    let value = n >= 3 ?  fibonacci(n-1) + fibonacci(n-2) :  1

    return value
 }

// 尾递归版本
const fibonaci = (n, a = 1, b = 1) => {
  if (n <= 1) { return b; }
  return fibonaci(n - 1, b, a + b);
}
// 递推版本
const fibonaci = (n) => {
  const F = [];
  F[0] = 0;
  F[1] = 1;
  for (let i = 2; i <= n; i++) {
    F[i] = F[i - 1] + F[i - 2];
  }
  return F[n];
}