前端面试攻略1------算法部分

时间：2019-03-02 20:43:17 阅读：148 评论：0 收藏：0 [点我收藏+]

前端面试攻略1------算法部分

1、基本排序的方式

　　冒泡法（Bubble Sort）：

　　　　冒泡排序特点：

　　　　什么时候最快（Best Cases）：

　　　　　　当输入的数据已经是正序时

　　　　什么时候最慢（Worst Cases）：

　　　　　　当输入的数据是反序时

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        //相邻元素两两对比
                var temp = arr[j+1];        //元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

　　快速排序（Quick Sort）

　　　　快速排序特点：

　　又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高! 它是处理大数据最快的排序算法之一了。

　　快速排序的最坏运行情况是O(n²)，比如说顺序数列的快排。但它的平摊期望时间是O(n log n) ，且O(n log n)记号中隐含的常数因子很小，比复杂度稳定等于O(n log n)的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

　　快速排序的内循环比大多数排序算法都要短小，这意味着它无论是在理论上还是在实际中都要更快。它的主要缺点是非常脆弱，在实现时要非常小心才能避免低劣的性能。

function quickSort(arr, left, right) {
    var 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;
}

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

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

　　堆排序（Heap Sort）

堆排序特点：

堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列

var len;    //因为声明的多个函数都需要数据长度，所以把len设置成为全局变量

function buildMaxHeap(arr) {   //建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i &gt;= 0; i--) {
        heapify(arr, i);
    }
}

function heapify(arr, i) {     //堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;

    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}

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

function heapSort(arr) {
    buildMaxHeap(arr);

    for (var i = arr.length-1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}

　　插入排序（Insertion Sort）

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

　　归并排序（Merge Sort）

　　作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第2种方法）
自下而上的迭代

function mergeSort(arr) {  //采用自上而下的递归方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length>0 && right.length>0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

　　桶排序（Bucket Sort）

　　桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的N个数据均匀的分配到K个桶中

　　同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

　　什么时候最快（Best Cases）：

　　当输入的数据可以均匀的分配到每一个桶中

　　什么时候最慢（Worst Cases）：

　　当输入的数据被分配到了同一个桶中

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                //输入数据的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                //输入数据的最大值
      }
    }

    //桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            //设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;   
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

    //利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      //对每个桶进行排序，这里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                      
        }
    }

    return arr;
}

2、二分搜索

二分搜索法：

　　也称折半搜索，是一种在有序数组中查找特定元素的搜索算法。

实现步骤：

　　1. 首先从数组中间开始查找对比，若相等则找到，直接返回中间元素的索引。

　　2. 若查找值小于中间值，则在小于中间值的那一部分执行步骤1的操作。

　　3. 若查找值大于中间值，则在大于中间值的那一部分执行步骤1的操作。

　　4. 否则，返回结果为查不到，返回-1。

function binary_search1(arr, key) {
        var low = 0;
        var high = arr.length - 1;

        while (low <= high) {
            var mid = parseInt((low + high) / 2);

            if (key === arr[mid]) {
                return mid;
            }
            else if (key < arr[mid]) {
                high = mid + 1;
            }
            else if (key > arr[mid]) {
                low = mid - 1;
            }
            else {
                return -1;
            }
        }
    }

　　var arr = [1,2,3,4,5,6,7,8];
　　console.log(binary_search1(arr, 3));

function binary_search2 (arr, low, high, key) {
        if (low > high) {
            return -1;
        }

        var mid = parseInt((low + high) / 2);

        if (key === arr[mid]) {
            return mid;
        }
        else if (key < arr[mid]) {
            high = mid - 1;
            return binary_search2(arr, low, high, key);
        }
        else if (key > arr[mid]) {
            low = mid + 1;
            return binary_search2(arr, low, high, key);

        }
    }

　　
　　　var arr = [1,2,3,4,5,6,7,8];
　　　console.log(binary_search2(arr, 0, 7, 3));

3、二叉树遍历

例如前序遍历中序遍历后序遍历等，深度优先搜索和广度优先最好掌握。还有二叉树的反转。

二叉树的遍历

二叉树的遍历指的是按照某种顺序，依次访问二叉树的每个节点，有且访问一次。

二叉树的遍历有以下三种

（1）前序遍历，从根节点，到左子树，再到右子树，简称根左右。

（2）中序遍历，从左节点，到根节点，再到右子树，简称左根右。

（3）后序遍历，从左子树，到右子树，再到根节点，简称左右根。

<!DOCTYPE html>
<html>
<head>
    <meta charset="UTF-8">
    <title>Document</title>
    <style>
        *{
            margin: 0;
            padding: 0;
        }
        .wrap{
            display: flex;
            border:1px solid #000;
            width: 600px;
            margin:0 auto;
            height: 150px;
            align-items: center;
            justify-content:center;
        }
        .wrap div{
            display: flex;
            height: 70%;
            width: 44%; 
            margin:0 3%;
            border:1px solid #000;
            justify-content:center;
            align-items: center;   
            background: #fff;         
        }
        .btn-wrap{
            text-align: center;
            padding-top: 20px;
        }
        .btn-wrap button{
            display: inline-block;
            padding:4px 10px;
        }
        
    </style>
</head>
<body>
    <div class="wrap">
        <div>
            <div>
                <div>
                    <div></div>
                    <div></div>
                </div>
                <div>
                    <div></div>
                    <div></div>
                </div>
            </div>
            <div>
                <div>
                    <div></div>
                    <div></div>
                </div>
                <div>
                    <div></div>
                    <div></div>
                </div>
            </div>
        </div>
        <div>
            <div>
                <div>
                    <div></div>
                    <div></div>
                </div>
                <div>
                    <div></div>
                    <div></div>
                </div>
            </div>
            <div>
                <div>
                    <div></div>
                    <div></div>
                </div>
                <div>
                    <div></div>
                    <div></div>
                </div>
            </div>            
        </div>
    </div>
    <div class="btn-wrap"> 
        <button>前序</button>
        <button>中序</button>
        <button>后序</button>
    </div>
    <script>
        var wrap = document.querySelector(".wrap");
        var btn_wrap = document.querySelector(".btn-wrap");
        var btn1 = btn_wrap.querySelectorAll("button")[0];
        var btn2 = btn_wrap.querySelectorAll("button")[1];
        var btn3 = btn_wrap.querySelectorAll("button")[2];
        var arr = [];
        var last;
        var toggle = false;
        //给按钮绑定事件
        btn1.onclick = function(){
            if(!toggle){
                toggle = true;
                reset();
                preOrder(wrap);
                showWay();
            }
        }
        btn2.onclick = function(){
            if(!toggle){
                toggle = true;
                reset();
                inOrder(wrap);
                showWay();
            }
        }
        btn3.onclick = function(){
            if(!toggle){
                toggle = true;
                reset();
                postOrder(wrap);
                showWay();
            }
        }
        //二叉树的遍历的三种方式
        //(1)前序遍历（DLR
        function preOrder(node){
            if(node){
                arr.push(node);
                preOrder(node.firstElementChild);
                preOrder(node.lastElementChild);
            }
        }
        //(2)中序遍历（LDR）
        function inOrder(node){
            if(node){
                inOrder(node.firstElementChild);
                arr.push(node);
                inOrder(node.lastElementChild);
            }
        }
        //(3)后序遍历（LRD）
        function postOrder(node){
            if(node){
                postOrder(node.firstElementChild);
                postOrder(node.lastElementChild);
                arr.push(node);
            }
        }
        //显示遍历的过程
        function showWay(){
            for(var i=0; i<arr.length; i++){
                setTimeout(function(i){
                    return function(){
                        if(i == arr.length-1){
                            toggle = false;
                        }
                        if(last){
                            last.style.background = "white";
                        }
                        arr[i].style.background = "red";
                        last = arr[i];
                    }
                }(i),i*1000)
            }
        }
        //初始化
        function reset(){
            arr = [];
            if(last){
                last.style.background = "white";
            }
        }
    </script>
</body>
</html>

前端面试攻略1------算法部分

原文：https://www.cnblogs.com/NightTiger/p/10457708.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)