各种常用算法介绍

各种排序的时间复杂度

对于以上的O可能有部分人不是很了解，O表示算法的性能和复杂度。(通常来说就是占用cpu的情况）

冒泡排序

就是两层for循环，前后两个值进行比较

function popSort() {
   var a = [1,5,6,7,8,10,9,3,21,6];
   var n=a.length;
   var tem;
   for(let i=0;i<n;i++){
            for(int j=0;j<n-i-1;j++){
                if(a[j]>a[j+1]){
                    tem=a[j];
                    a[j]=a[j+1];
                    a[j+1]=tem;
                }
            }
        }
}

把冒泡时间负责度缩小的办法

// 改进冒泡排序
function bubbleSort1(arr) {
    let i = arr.length - 1;

    while (i > 0) {
        let pos = 0;
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                pos = j;
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        i = pos;
    }
    console.log(arr);
}

快速排序

采取的思想为分而治的思想，以基数来进行比较

// 快速排序
const quickSort = (arr, left, right) => {
    let len = arr.length,
        partitionIndex;
    left = typeof left != 'number' ? 0 : left;
    right = typeof right != 'number' ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
};

const partition = (arr, left, right) => {
    //分区操作
    let pivot = left, //设定基准值（pivot）
        index = pivot + 1;
    for (let i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
};

const swap = (arr, i, j) => {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

快排不需要额外的内存空间，也就是原地排序算法
因为快排每次排序的要交换的元素可能是相邻的，也可能相隔几个的元素，所以说快排是不稳定的
快排的时间复杂度，极端情况 就是数组本身是有序的所以只要O(n), 如果数组是倒叙排列O(n2)，平均下来（O(nlngn)

堆排序

堆的插入就是——每次插入都是将新数据放在数组最后，而从这个新数据的父结点到根结点必定是一个有序的数列，因此只要将这个新数据插入到这个有序数列中即可。

参考：https://juejin.im/post/5d371aa6e51d455d850d3bbe