一、排序
1. 冒泡
（1）概念：冒泡排序只會比較兩個相鄰的數據，看是否滿足大小關系要求。如果不滿足就互換。一次遍歷會讓至少一個數據 移動到該有的位子。重復N次完成排序。
（2）特點：
時間復雜度O(n2)，最好情況時間復雜度O(n)，最壞情況時間復雜度O(n2)，平均時間復雜度O(n2)。
空間復雜度O(1)，也叫原地排序。
穩(wěn)定性-穩(wěn)定。
（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）概念：將數組的數據分為兩個區(qū)間，已排序區(qū)間和為排序區(qū)間。初始已排序區(qū)間有一個元素（數組的第一個元素）。核心思想取未排序區(qū)間中的第一個元素，在已排序區(qū)間中找到合適的插入位子將其插入，并保證已排序區(qū)間數據一致有序。重復N次，完成排序。
（2）特點：
時間復雜度：O(n2)，最好情況時間復雜度O(n)，最壞情況時間復雜度O(n2)，平均時間復雜度O(n2)。
空間復雜度O(1)，也叫原地排序。
穩(wěn)定性-穩(wěn)定。
（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）概念：將數組的數據分為兩個區(qū)間，已排序區(qū)間和為排序區(qū)間。初始已排序區(qū)間有一個元素（數組的第一個元素）。核心思想取未排序區(qū)間中的最小一個元素，將其放到已排序區(qū)間的末尾。重復N次，完成排序。
（2）特點：
時間復雜度：O(n2)，最好情況時間復雜度O(n2)，最壞情況時間復雜度O(n2)，平均時間復雜度O(n2)。
空間復雜度O(1)，也叫原地排序。
穩(wěn)定性-不穩(wěn)定。
（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
}
三種排序插入排序最受歡迎，原因，選擇排序不穩(wěn)定。冒泡排序需要交換數據。而插入排序只需要移位，代碼比冒泡少。
4. 歸并排序
（1）概念：把數組從中間分成前后兩部分，然后對前后兩部分分別排序，再將排序好的兩部分合并在一起。
（2）特點：
分治思想，用到遞歸。分治是一種解決問題的處理思想，遞歸是一種編程技巧。
時間復雜度：O(nlogn)，最好情況時間復雜度O(nlogn)，最壞情況時間復雜度O(nlogn)，平均時間復雜度O(nlogn)。
空間復雜度O(n)。
穩(wěn)定性-穩(wě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)。
穩(wěn)定性-不穩(wěn)定。
（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;
}
歸并排序和快速排序的區(qū)別：可以發(fā)現，歸并排序的處理過程是由下到上的，先處理子問題，然后再合并。而快排正好相反，它的處理過程是由上到下的，先分區(qū)，然后再處理子問題。歸并排序雖然是穩(wěn)定的、時間復雜度為 O(nlogn) 的排序算法，但是它是非原地排序算法。我們前面講過，歸并之所以是非原地排序算法，主要原因是合并函數無法在原地執(zhí)行。快速排序通過設計巧妙的原地分區(qū)函數，可以實現原地排序，解決了歸并排序占用太多內存的問題。
二、查找
1. 二分法（折半查找）
（1）概念：二分法針對的事一個有序的數據集合，查找思想有點類似與分治思想。每次都通過跟區(qū)間的中間元素對比，將待查找的區(qū)間縮小之前的一般，直到找到要查找到元素，或者區(qū)間被縮小到0.
（2）特點：
時間復雜度O（logn）
空間復雜度:O(1)
局限性：
二分查找依賴的順序表解構，也就是數組。
二分查找針對的事有序數據。
數據量太小不適合二分查找。
數據量太大不適合二分查找，底層依賴數據數據結構，要求內存空間連續(xù)。
//方法一
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）父節(jié)點、子節(jié)點、兄弟節(jié)點、根節(jié)點、葉子節(jié)點
（2）節(jié)點高度：節(jié)點到葉子節(jié)點最長路徑（邊數）
（3）節(jié)點的深度：根節(jié)點到這個節(jié)點所經歷的邊的個數
（4）節(jié)點的層數：節(jié)點的深度+1
（5）樹的高度：根節(jié)點的高度
2. 二叉樹概念：
（1）二叉樹：每個節(jié)點最多有兩個叉，也就是兩個節(jié)點，分別是左子節(jié)點，右子節(jié)點
（2）滿二叉樹：除了葉子節(jié)點以外，每個節(jié)點都有兩個左右子節(jié)點
（3）完全二叉樹：最后一層的葉子節(jié)點都靠左排列，并且除了最后一層，其他層的節(jié)點個數都達到最大
3.二叉樹的存儲：
一種是局域指針或者引用的二叉鏈式存儲法（大多數都是這種），一種是基于數組的順序存儲法。
4.二叉樹的遍歷：
（1）前（根）序遍歷：對樹中任意節(jié)點，先打印這個節(jié)點，再打印左子樹，最后打印右子樹
（2）中（根）序遍歷：對樹中任意節(jié)點，先打印左子樹，再打印它本身，最后打印右子樹
（3）后（根）序遍歷：對于樹中任意節(jié)點，先打印左子樹，再打印右子樹，最后打印它本身
（4）代碼：
5.二叉樹的查找：
（1）特性：要求在樹中任意子節(jié)點，其左子樹中的每個節(jié)點值，都要小于這個節(jié)點的值，而右子樹節(jié)點的值都要大于這個節(jié)點的值。
（1）代碼：
6.二叉樹的插入操作：
（1）特性：新插入的數據一般都在葉子節(jié)點上，需要從根節(jié)點開始，依次比較要插入的數據和節(jié)點和大小關系。如果要插入的數據比節(jié)點數據大，并且節(jié)點的右子樹為空，就將新數據直接插入到右子節(jié)點的位置；如果不為空，就再遍歷右子樹，查找插入的位置。反之左子樹同理。
（2）代碼：
7.二叉樹的刪除操作：
8.二叉樹查找、插入、刪除時間復雜度：
（1）最壞情況：二叉樹退化成鏈表O(n)
（2）最好情況：完全二叉樹和滿二叉樹O(logn2n)
