js排序和查找算法
一、排序
1. 冒泡
（1）概念：冒泡排序只会比较两个相邻的数据，看是否满足大小关系要求。如果不满足就互换。一次遍历会让至少一个数据 移动到该有的位子。重复N次完成排序。
（2）特点：
时间复杂度O(n2)，最好情况时间复杂度O(n)，最坏情况时间复杂度O(n2)，平均时间复杂度O(n2)。
空间复杂度O(1)，也叫原地排序。
稳定性-稳定。
（3）代码：
function bubbleSort(arr){
for(let i=0;i<arr.length;i++){
for(let j=0;j<arr.length-i-1;j++){
if(arr[j]>arr[j+1]){
[arr[j],arr[j+1]]=[arr[j+1],arr[j]];
}
}
}
}
2. 插入排序
（1）概念：将数组的数据分为两个区间，已排序区间和为排序区间。初始已排序区间有一个元素（数组的第一个元素）。核心思想取未排序区间中的第一个元素，在已排序区间中找到合适的插入位子将其插入，并保证已排序区间数据一致有序。重复N次，完成排序。
（2）特点：
时间复杂度：O(n2)，最好情况时间复杂度O(n)，最坏情况时间复杂度O(n2)，平均时间复杂度O(n2)。
空间复杂度O(1)，也叫原地排序。
稳定性-稳定。
（3）代码：
function insertSort(arr){
for(let i=1;i<arr.length;i++){
let temp=arr[i];
let j=i-1;
//如果有序的序列中比当前这个值大，则进行向后移位
for(;j>=0 && arr[j]>temp;j--){
arr[j+1]=arr[j]
}
arr[j+1]=temp;//插入值
}
return arr;
}
3. 选择排序
（1）概念：将数组的数据分为两个区间，已排序区间和为排序区间。初始已排序区间有一个元素（数组的第一个元素）。核心思想取未排序区间中的最小一个元素，将其放到已排序区间的末尾。重复N次，完成排序。
（2）特点：
时间复杂度：O(n2)，最好情况时间复杂度O(n2)，最坏情况时间复杂度O(n2)，平均时间复杂度O(n2)。
空间复杂度O(1)，也叫原地排序。
稳定性-不稳定。
（3）代码：
function selectSort(arr){
for(let i=0;i<arr.length;i++){
let minIndex=i;
//在未排序的序列里找到最小的值的索引
for(let j=i+1;j<arr.length;j++){
if(arr[j]<arr[minIndex]){
minIndex=j;
}
}
[arr[i],arr[minIndex]]=[arr[minIndex],arr[i]];
}
return arr
}
三种排序插入排序最受欢迎，原因，选择排序不稳定。冒泡排序需要交换数据。而插入排序只需要移位，代码比冒泡少。
4. 归并排序
（1）概念：把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排序好的两部分合并在一起。
归并排序
（2）特点：
分治思想，用到递归。分治是一种解决问题的处理思想，递归是一种编程技巧。
时间复杂度：O(nlogn)，最好情况时间复杂度O(nlogn)，最坏情况时间复杂度O(nlogn)，平均时间复杂度O(nlogn)。
空间复杂度O(n)。
稳定性-稳定。
（3）代码：
function mergeSort(arr){
if(arr.length<=1){
return arr;
}
let middleIndex=Math.floor(arr.length/2);
let leftArr=arr.slice(0,middleIndex);
let rightArr=arr.slice(middleIndex);
return merge(mergeSort(leftArr),mergeSort(rightArr));//分治思想
}
function merge(leftArr,rightArr){
let arr=[];
while(leftArr.length>0 && rightArr.length>0){
if(leftArr[0]<rightArr[0]){
arr.push(leftArr.shift());
}else{
arr.push(rightArr.shift());
}
}
return arr.concat(leftArr,rightArr);
}
5. 快速排序
（1）概念：也用到分治的思想，随机取数据中一个元素（一般是最后一个元素），已这个元素为中点，将小与它的元素
放到它的左边，将大于它的元素放到它的右边。再以它的索引分成两个数据，每个数据重复以上逻辑，实现排序。
（2）特点：
分治思想，用到递归。分治是一种解决问题的处理思想，递归是一种编程技巧。
时间复杂度：O(nlogn)，最好情况时间复杂度O(nlogn)，最坏情况时间复杂度O(n2)，平均时间复杂度O(nlogn)。
空间复杂度O(1)。
稳定性-不稳定。
（3）代码：
function sort(arr,leftIndex=0,rightIndex=arr.length-1){
if(leftIndex>=rightIndex){return;}
let storeIndex=partition(arr,leftIndex,rightIndex);
sort(arr,leftIndex,storeIndex-1);
sort(arr,storeIndex+1,rightIndex);
}
function partition(arr,leftIndex,rightIndex){
let pivo=arr[rightIndex];
let storeIndex=leftIndex;
for(let i=leftIndex;i<rightIndex;i++){
if(arr[i]<pivo){
if(storeIndex!=i){
[arr[i],arr[storeIndex]]=[arr[storeIndex],arr[i]];
}
storeIndex++;
}
}
if(storeIndex!=rightIndex){
[arr[rightIndex],arr[storeIndex]]=[arr[storeIndex],arr[rightIndex]];
}
return storeIndex;
}
function quickSort(arr){
if(arr.length<=1){
return arr;
}
sort(arr);
return arr;
}
归并排序和快速排序的区别：可以发现，归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
aa03ae570dace416127c9ccf9db8ac05.jpg
二、查找
1. 二分法（折半查找）
（1）概念：二分法针对的事一个有序的数据集合，查找思想有点类似与分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小之前的一般，直到找到要查找到元素，或者区间被缩小到0.
（2）特点：
时间复杂度O（logn）
空间复杂度:O(1)
局限性：
二分查找依赖的顺序表解构，也就是数组。
二分查找针对的事有序数据。
数据量太小不适合二分查找。
数据量太大不适合二分查找，底层依赖数据数据结构，要求内存空间连续。
//方法一
function search(arr,value,low=0,high=arr.length-1){
if(low>high){
return -1;
}
let middleIndex=Math.floor(low+(high-low)/2);
if(arr[middleIndex]<value){
return search(arr,value,middleIndex+1,high);
}else if(arr[middleIndex]>value){
return search(arr,value,low,middleIndex-1);
}else{
return middleIndex
}
}
//方法二
function serach2(arr,value,low=0,high=arr.length-1){
while(low<=high){
let middleIndex=Math.floor(low+(high-low)/2);
if(arr[middleIndex]<value){
low=middleIndex+1;
}else if(arr[middleIndex]>value){
high=middleIndex-1;
}else{
return middleIndex;
}
}
return -1;
}
2.变体二分查找
//找到第一个等于value的值
function searchFirstOfSame(arr,value,low=0,high=arr.length-1){
if(low>high){
return -1;
}
let middleIndex=Math.floor(low+(high-low)/2);
if(arr[middleIndex]<value){
return search(arr,value,middleIndex+1,high);
}else if(arr[middleIndex]>value){
return search(arr,value,low,middleIndex-1);
}else{
if(arr[middleIndex]==arr[0]||arr[middleIndex]!=arr[middleIndex-1]){return middleIndex}
return search(arr,value,low,middleIndex-1);
}
}
//找到最后一个等于value的值
function searchLastOfSame(arr,value,low=0,high=arr.length-1){
if(low>high){
return -1;
}
let middleIndex=Math.floor(low+(high-low)/2);
if(arr[middleIndex]<value){
return searchLastOfSame(arr,value,middleIndex+1,high);
}else if(arr[middleIndex]>value){
return searchLastOfSame(arr,value,low,middleIndex-1);
}else{
if(arr[middleIndex]==arr[arr.length-1]||value!=arr[middleIndex+1]){return middleIndex}
return searchLastOfSame(arr,value,middleIndex+1,high);
}
}
三、二叉树
1. 树概念：
（1）父节点、子节点、兄弟节点、根节点、叶子节点
（2）节点高度：节点到叶子节点最长路径（边数）
（3）节点的深度：根节点到这个节点所经历的边的个数
（4）节点的层数：节点的深度+1
（5）树的高度：根节点的高度
2. 二叉树概念：
（1）二叉树：每个节点最多有两个叉，也就是两个节点，分别是左子节点，右子节点
（2）满二叉树：除了叶子节点以外，每个节点都有两个左右子节点
（3）完全二叉树：最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都达到最大
3.二叉树的存储：
一种是局域指针或者引用的二叉链式存储法（大多数都是这种），一种是基于数组的顺序存储法。
WechatIMG1.jpeg
WechatIMG2.jpeg
4.二叉树的遍历：
（1）前（根）序遍历：对树中任意节点，先打印这个节点，再打印左子树，最后打印右子树
（2）中（根）序遍历：对树中任意节点，先打印左子树，再打印它本身，最后打印右子树
（3）后（根）序遍历：对于树中任意节点，先打印左子树，再打印右子树，最后打印它本身
（4）代码：
WX20190330-213653@2x.png
5.二叉树的查找：
（1）特性：要求在树中任意子节点，其左子树中的每个节点值，都要小于这个节点的值，而右子树节点的值都要大于这个节点的值。
（1）代码：
WX20190330-214115@2x.png
6.二叉树的插入操作：
（1）特性：新插入的数据一般都在叶子节点上，需要从根节点开始，依次比较要插入的数据和节点和大小关系。如果要插入的数据比节点数据大，并且节点的右子树为空，就将新数据直接插入到右子节点的位置；如果不为空，就再遍历右子树，查找插入的位置。反之左子树同理。
（2）代码：
WX20190330-214659@2x.png
7.二叉树的删除操作：
WechatIMG3.jpeg
8.二叉树查找、插入、删除时间复杂度：
（1）最坏情况：二叉树退化成链表O(n)
（2）最好情况：完全二叉树和满二叉树O(logn2n)
