当前位置：首页 > news >正文

视频类网站建设的成果深圳搜索引擎优化推广便宜

news 2025/8/19 19:50:23

视频类网站建设的成果,深圳搜索引擎优化推广便宜,东莞建站公司,健身器械网站建设案例前端面试攻略1------算法部分 1、基本排序的方式冒泡法（Bubble Sort）： 冒泡排序特点： 什么时候最快（Best Cases）： 当输入的数据已经是正序时什么时候最慢（Worst Cases）…

前端面试攻略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;            //设置桶的默认数量为5bucketSize = 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)前序遍历（DLRfunction 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>