面试-算法篇

1.五大算法

最常用的五大算法分别是什么？

1.1贪心（自顶向下）

1.2分治

1.3动态规划（自底向上）

动态规划与分治法相似，都是组合子问题的解来解决原问题的解，与分治法的不同在于：分治法的子问题是相互独立存在的，而动态规划应用于子问题重叠的情况。

1.4回溯

1.5分支限界法

分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支，这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。

2.排序

分类：
插入排序（直接插入排序、折半插入排序、希尔排序）；
交换排序（冒泡排序、快速排序）；
选择排序（简单选择排序、树形选择排序、堆排序）；
归并排序；
基数排序

八种排序算法的时间复杂度

2.1冒泡排序（稳定、O(n²)）

“是相邻元素之间的比较和交换，两重循环O(n2)；如果两个相邻元素相等，是不会交换的，所以它是一种稳定的排序方法。”

代码实现

function bubleSort(arr) {
    let len = arr.length;
    for(let outer = len; outer >= 2; outer--) {
    	// 内层for循环 确保每次都将较大的数字放到最后面
        for(let inner = 0; inner <= outer - 1; inner++) {
            if(arr[inner] > arr[inner + 1]) {
                [arr[inner],arr[inner + 1]] = [arr[inner + 1],arr[inner]];
            }
        }
    }
    // console.log(arr);
    return arr;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.2选择排序（不稳定、O(n²)）

思想： 遍历自身以后的元素，最小的元素跟自己调换位置。
不稳定：每个元素都与第一个元素相比，产生交换，两重循环O(n2)；举个栗子，5 8 5 2 9，第一遍之后，2会与5交换，那么原序列中两个5的顺序就被破坏了。所以不是稳定的排序算法。

代码实现

function selectSort(arr) {
    let len = arr.length;
    for(let i = 0; i < len - 1; i++) {
    //  与比自身小的元素交换位置
        for(let j = i + 1; j < len; j++) {
            if(arr[j] < arr[i]) {
                [arr[j], arr[i]] = [arr[i], arr[j]];
            }
        }
    }
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.3 插入排序（稳定、O(n²)）

思想：将元素插入到已排序好的数组中。
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。刚开始这个小序列只包含第一个元素，事件复杂度O(n²)。比较是从这个小序列的末尾开始的。想要插入的元素和小序列的最大者开始比起，如果比它大则直接插在其后面，否则一直往前找它该插入的位置。如果遇见了一个和插入元素相等的，则把插入元素放在这个相等元素的后面。所以相等元素间的顺序没有改变，是稳定的。

代码实现

function insertSort(arr) {
    let len = arr.length;
    for(let i = 1; i < len; i++) {
        for(let j = i; j > 0; j--) {
            //  将arr[j] 依次插入到有序段中
            if(arr[j] < arr[j - 1]) {
                [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
            }else{
                break;
            }
        }
    }
    console.log(arr);
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.4 希尔排序（不稳定、O(n^1.3)）

不定步数的插入排序。
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
参考JS实现希尔排序

function shellSort(arr) {
    for(let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
        // 内层循环与插入排序的写法基本一致，只是每次移动的步长变为 gap
        for(let i = gap; i < arr.length; i++) {
            let j = i;
            let temp = arr[j];
            for(; j > 0; j -= gap) {
                if(temp >= arr[j - gap]) {
                    break;
                }
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
    console.log(arr);
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.5 快速排序（不稳定、O(nlogn)）

思想：选择基准值（base），原数组长度减一（基准值），使用splice循环原数组，小的放左边（left数组），大的放右边（right）数组，concat(left, base, right)，递归继续排序left和right。

快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j]交换的时刻。

代码实现

function quickSort(arr) {
    //  递归出口
    if(arr.length <= 1) {
        return arr;
    }
                                // 在位置0 删除一个元素 
    let left = [], right = [], current = arr.splice(0, 1);
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] < current) {
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat(current,quickSort(right));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.6堆排序（不稳定、nlog(n)）

我们知道堆的结构是节点i的孩子为2i和2i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, …1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
JS实现堆排序