# 前端的算法与数据结构
# 算法分类
十种常见排序算法可以分为两大类：
- 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
- 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
相关概念
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
# 深度优先遍历和广度优先遍历
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title></title>
</head>
<body>
<div class="parent">
<div class="child-1">
<div class="child-1-1">
<div class="child-1-1-1">a</div>
</div>
<div class="child-1-2">
<div class="child-1-2-1">b</div>
</div>
<div class="child-1-3">c</div>
</div>
<div class="child-2">
<div class="child-2-1">d</div>
<div class="child-2-2">e</div>
</div>
<div class="child-3">
<div class="child-3-1">f</div>
</div>
</div>
</body>
</html>
<script type="text/javascript">
var p=document.querySelector(".parent")
// 深度遍历 方法一： 递归方式实现
const deepTraversal1 = (node, nodeList = []) => {
if (node !== null) {
nodeList.push(node)
let children = node.children
for (let i = 0; i < children.length; i++) {
deepTraversal1(children[i], nodeList)
}
}
//console.log(1)
console.log(nodeList)
return nodeList
}
// var t1=deepTraversal1(p)
// console.log(t1)
// 深度遍历 方法二： 非递归方式实现
const deepTraversal2 = (node) => {
let stack = []
let nodes = []
if (node) {
// 推入当前处理的node
stack.push(node)
while (stack.length) {
let item = stack.pop()
console.log(item)
let children = item.children
nodes.push(item)
// node = [] stack = [parent]
// node = [parent] stack = [child3,child2,child1]
// node = [parent, child1] stack = [child3,child2,child1-2,child1-1]
// node = [parent, child1-1] stack = [child3,child2,child1-2]
for (let i = children.length - 1; i >= 0; i--) {
stack.push(children[i])
}
}
}
return nodes
}
var t2=deepTraversal2(p)
console.log(t2)
</script>
- 广度算法
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title></title>
</head>
<body>
<div class="parent">
<div class="child-1">
<div class="child-1-1">
<div class="child-1-1-1">a</div>
</div>
<div class="child-1-2">
<div class="child-1-2-1">b</div>
</div>
<div class="child-1-3">c</div>
</div>
<div class="child-2">
<div class="child-2-1">d</div>
<div class="child-2-2">e</div>
</div>
<div class="child-3">
<div class="child-3-1">f</div>
</div>
</div>
</body>
</html>
<script type="text/javascript">
const widthTraversal = (node) => {
let nodes = []
let stack = []
if (node) {
stack.push(node)
while (stack.length) {
let item = stack.shift()
let children = item.children
nodes.push(item)
// 队列，先进先出
// nodes = [] stack = [parent]
// nodes = [parent] stack = [child1,child2,child3]
// nodes = [parent, child1] stack = [child2,child3,child1-1,child1-2]
// nodes = [parent,child1,child2]
for (let i = 0; i < children.length; i++) {
stack.push(children[i])
}
}
}
console.log(nodes)
return nodes
}
var p=document.querySelector(".parent")
widthTraversal(p)
</script>
# 排序
# 冒泡排序（Bubble Sort）
原理：比较两个相邻的元素，将值大的元素交换到右边
算法描述
- 比较第一位与第二位，如果第一位比第二位大，则交换位置
- 继续比较后面的数，按照同样的方法进行比较，到最后一位的时候，最大的数将被排在最后一位
- 重复进行比较，直到排序完成，注意由于上一次排序使得最后一位已经是最大的数，所以每次排序结束之后，下一次比较的时候可以相应的减少比较数量
let arr = [3, 45, 16, 8, 65, 15, 36, 22, 19, 1, 96, 12, 56, 12, 45];
let flag;
let len = arr.length;
let num1 = 0; // 比较的次数
let num2 = 0; // 交换的次数
// 有15个数，只需要选出14个最大的数，最后一个数就是最小的，不用进行比较
for(let i = 0; i < len -1 ; i++){
// 每次i变化之后最大的值已经排序到最后一位，无需对最后一位进行比较，所以j的最大值为len-i-1
for(let j = 0; j < len - i - 1; j++){
num1 += 1;
// 如果当前位置的数比下一位置的数大，则交换位置
if(arr[j] > arr[j+1]){
num2++;
flag = arr[j];
arr[j] = arr[j+1];
arr[j+1] = flag
}
}
}
console.log(arr,num1,num2);
//[1, 3, 8, 12, 12, 15, 16, 19, 22, 36, 45, 45, 56, 65, 96] 105 46
从代码中看出，排序过程中，所需要的临时变量一直都没有变化，因此空间复杂度为O(1)；代码进行了两次for循环且是嵌套循环，因此时间复杂度为O(n²)。
冒泡排序的最优情况是原数组默认正序排序，此时比较的次数num1仍为105，而交换次数num2为0，此时的时间复杂度仍然为O(n²)，那么为什么前面的复杂度表格中说是O(n)呢？经过一番研究发现，需要对上述代码进行简单优化。
如果排序的数组是：[1,2,3,4,5]，此时完全符合最优复杂度情况，当我们进行第一次循环发现，两两相邻的数据一次都没有进行交换，也就是说所有的数都比前一个数大，此时就是正序，无需再进行下次排序，所以我们只需要加上一个变量进行判断：
// 初始未产生交换
let isSwap = false;
for(let i = 0; i < len -1 ; i++){
// 每次i变化之后最大的值已经排序到最后一位，无需对最后一位进行比较，所以j的最大值为len-i-1
for(let j = 0; j < len - i - 1; j++){
num1 += 1;
// 如果当前位置的数比下一位置的数大，则交换位置
if(arr[j] > arr[j+1]){
num2 =+ 1;
isSwap = true;
flag = arr[j];
arr[j] = arr[j+1];
arr[j+1] = flag
}
}
// 如果没有产生任何交换，则可以直接结束循环
if(!isSwap){
return
}else{
// 如果之前已经产生了交换，那么下次循环重新设置isSwap
// 因为加入仅仅有一个数位置不对，没有这里他之后isSwap一直都是true
// 就再也不能处理位置不变的情况了
isSwap =false
}
}
# 选择排序
原理:将序列分为未排序和已排序，从未排序序列中找到最小的数，放到无序序列起始位置，然后继续从剩余未排序序列中继续寻找最小值
算法描述
初始无序序列为待排序序列，有序序列为空 从无序序列中找到最小值，放到无序序列起始位置，也就是和起始位置交换 将无序序列起始位向后推一个位置，继续2步骤
// 选择出无序序列中最小的值放到无序第一位
let arr = [3, 45, 16, 8, 65, 15, 36, 22, 19, 1, 96, 12, 56, 12, 45];
let len = arr.length;
let minIndex;
let flag;
let num1 = 0; // 比较次数
let num2 = 0; // 交换次数
for(let i = 0; i < len - 1;i++){
// 每次选择最小值之后，无序区的开始位置往后推1
minIndex = i;
// j循环到最后一位，选择出当前无序数组中数值最小的索引值
for(let j = i + 1; j < len;j++){
num1 += 1;
if(arr[minIndex]>arr[j]){
minIndex = j;
}
}
num2 += 1;
flag = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = flag;
}
console.log(arr,num1,num2)
//[1, 3, 8, 12, 12, 15, 16, 19, 22, 36, 45, 45, 56, 65, 96] 105 14
- 为什么说选择排序是不稳定的呢？
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。
举个例子，序列arr = [5 8 5 2 9]，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法
# 插入排序
构建有序序列，对于未排序的数据，从有序序列后向前扫描，找到相应位置插入
let arr = [3, 45, 16, 8, 65, 15, 36, 22, 19, 1, 96, 12, 56, 12, 45];
let len = arr.length;
// 定义当前未排序数据起始位置值也就是即将插入的数据
let currentValue;
// 有序序列遍历位置
let preIndex;
let num1 = 0; // 比较次数
let num2 = 0; // 交换次数
for(let i = 1;i < len; i++){
// 定义原始数据第二位为未排序数据第一位，默认原始数据第一位已排序
currentValue = arr[i];
// 当前有序序列最大索引
preIndex = i - 1;
// 当索引大于等于0且当前索引值大于需要插入的数据时
for(let j = preIndex;j>=0;j--){
// 第一次比较，如果有序序列最大索引值其实就是待插入数据前一位，比待插入数据大，则后移一位
num1+=1;
console.log(arr[preIndex],preIndex)
if(arr[preIndex]>currentValue){
arr[preIndex+1] = arr[preIndex];
preIndex --;
// 索引减1，继续向前比较
}else{
break;
}
}
// 当出现索引所在位置值比待插入数据小时，将待插入数据插入
// 为什么是preIndex+1，因为在循环里面后移一位之后，当前索引已经变化
num2 += 1;
arr[preIndex+1] = currentValue;
}
console.log(arr,num1,num2)
# 希尔排序
希尔排序将序列分割成若干小序列（逻辑上分组），对每一个小序列进行插入排序，此时每一个小序列数据量小，插入排序的效率也提高了。
# 算法描述
- 选择一个增量序列，t1，t2....tk，其中ti>tj，tk = 1；
- 按增量序列个数k，对序列进行k次排序；
- 每次排序，根据增量ti，将待排序序列分成若干子序列，分别对子序列进行直接插入排序。当增量为tk也就是1时，进行最后一次排序，此时子序列为排序序列本身。
let arr = [3, 45, 16, 8, 65, 15, 36, 22, 19, 1, 96, 12, 56, 12, 45];
let len = arr.length;
let willInsertValue;
let gap = len; // 定义增量
// 动态定义增量序列，每一次增量变为上次一半，最后一次的gap为1
while(gap>0&&(gap = Math.trunc(gap/2))){
// 对每个分组进行插入排序，为什么i开始是gap，因为插入排序默认第一位是已排序序列，arr[gap]是第一个分组第二位
for(let i = gap;i<len;i++){
// 待进行插入的值为a[i]
willInsertValue = arr[i];
// 按组进行插入，这里比较绕人，前面说了，只是逻辑上的分组，实际上还是一个序列，这里按组插入的时候是交叉
// 进行插入
let j = i - gap;
// 下面就是个直接插入排序，只不过每次移位的时候下标差值为gap
while(j>=0&&arr[j]>willInsertValue){
arr[j+gap] = arr[j];
j -= gap
}
arr[j+gap] = willInsertValue
}
}
console.log(arr)
//[1, 3, 8, 12, 12, 15, 16, 19, 22, 36, 45, 45, 56, 65, 96]
希尔排序是对直接插入排序的一种优化，可以用于大型的数组，希尔排序比插入排序和选择排序要快的多，并且数组越大，优势越大。
# 堆排序
- 每个元素arr【i】的节点为arr【2i+1】和arr【2i+2】。
- 最后一个父节点为arr.length/2-1.
function sort(arr){
//初始化一个堆结构
for(var i =parseInt(arr.length/2)-1;i>=0;i--){
adHeap(i,arr,arr.length);
}
for(var j=arr.length-1;j>0;j--){
//只有第一个元素被替换，剩下的满足堆排序的特点，所以从0开始就可以
swap(arr,0,j);
adHeap(0,arr,j)
}
}
//实现堆结构
function adHeap(i,arr,length){
let temp = arr[i];
for(var k=i*2+1;k<length;k=k*2+1){
//找到大的那个节点，然后赋值给父节点
if(k+1<length && arr[k]<arr[k+1]){
k++;
}
if(arr[k]>temp){
arr[i] = arr[k];
i = k;
}else{
break;
}
}
//再用父节点的元素给补充上
arr[i] = temp;
}
function swap(arr,i,j){
let empty = arr[i];
arr[i] = arr[j];
arr[j] = empty;
}
let arr = [4,1,2,3,5,0,9,20,6,1];
sort(arr);
console.log(arr);