對法的演算法

1. 什麼是演算法什麼是算理

1、演算法是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。

不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。

2、算理就是計算過程中的道理，是指計算過程中思維方式，是解決為什麼這樣算的問題。如計算214+35時，就是根據數的組成進行演算的：214是由2個百、1個十和4個一組成的，35是由3個十和5個一組成的，所以先把4個一與5個一相加9個一，再把1個十與3個十相加得4個十，最後把2個百、4個十和9個一合並得249，這就是算理。

(1)對法的演算法擴展閱讀：

演算法常用設計模式

1、完全遍歷法和不完全遍歷法：在問題的解是有限離散解空間，且可以驗證正確性和最優性時，最簡單的演算法就是把解空間的所有元素完全遍歷一遍，逐個檢測元素是否是我們要的解。

這是最直接的演算法，實現往往最簡單。但是當解空間特別龐大時，這種演算法很可能導致工程上無法承受的計算量。這時候可以利用不完全遍歷方法——例如各種搜索法和規劃法——來減少計算量。

2、分治法：把一個問題分割成互相獨立的多個部分分別求解的思路。這種求解思路帶來的好處之一是便於進行並行計算。

3、動態規劃法：當問題的整體最優解就是由局部最優解組成的時候，經常採用的一種方法。

4、貪心演算法：常見的近似求解思路。當問題的整體最優解不是（或無法證明是）由局部最優解組成，且對解的最優性沒有要求的時候，可以採用的一種方法。

5、簡並法：把一個問題通過邏輯或數學推理，簡化成與之等價或者近似的、相對簡單的模型，進而求解的方法。

2. JavaScript實現十大排序演算法（圖文詳解）

冒泡排序排序的效果圖解法

當前解法為升序

冒泡排序的特點，是一個個數進行處理。第i個數，需要與後續的len-i-1個數進行逐個比較。

為什麼是`len-i-1`個數？

因為數組末尾的i個數，已經是排好序的，確認位置不變的了。

為什麼確認位置不變，因為它們固定下來之前，已經和前面的數字都一一比較過了。

functionbubbleSort(arr){constlen=arr.length;for(leti=0;i<len-1;i++){for(letj=0;j<len-i-1;j++){if(arr[j]>arr[j+1]){consttmp=arr[j+1];arr[j+1]=arr[j];arr[j]=tmp;}}}returnarr;}快速排序概要

快速排序，使用的是分治法的思想。通過選定一個數字作為比較值，將要排序其他數字，分為>比較值和<比較值，兩個部分。並不斷重復這個步驟，直到只剩要排序的數字只有本身，則排序完成。

效果圖解法functionquickSort(arr){sort(arr,0,arr.length-1);returnarr;functionsort(arr,low,high){if(low>=high){return;}leti=low;letj=high;constx=arr[i];//取出比較值x，當前位置i空出，等待填入while(i<j){//從數組尾部，找出比x小的數字while(arr[j]>=x&&i<j){j--;}//將空出的位置，填入當前值，下標j位置空出//ps：比較值已經緩存在變數x中if(i<j){arr[i]=arr[j]i++;}//從數組頭部，找出比x大的數字while(arr[i]<=x&&i<j){i++;}//將數字填入下標j中，下標i位置突出if(i<j){arr[j]=arr[i]j--;}//一直循環到左右指針i、j相遇，//相遇時，i==j,所以下標i位置是空出的}arr[i]=x;//將空出的位置，填入緩存的數字x，一輪排序完成//分別對剩下的兩個區間進行遞歸排序sort(arr,low,i-1);sort(arr,i+1,high);}}希爾排序概要

希爾排序是一種插入排序的演算法，它是對簡單的插入排序進行改進後，更高效的版本。由希爾（DonaldShell）於1959年提出。特點是利用增量，將數組分成一組組子序列，然後對子序列進行插入排序。由於增量是從大到小，逐次遞減，所以也稱為縮小增量排序。

效果圖解法

注意點插入排序時，並不是一個分組內的數字一次性用插入排序完成，而是每個分組交叉進行。

執行插入時，使用交換法functionshellSort(arr){//分組規則gap/2遞減for(letgap=Math.floor(arr.length/2);gap>0;gap=Math.floor(gap/2)){for(leti=gap;i<arr.length;i++){letj=i;//分組內數字，執行插入排序，//當下標大的數字，小於下標小的數字，進行交互//這里注意，分組內的數字，並不是一次性比較完，需要i逐步遞增，囊括下個分組內數字while(j-gap>=0&&arr[j]<arr[j-gap]){swap(j,j-gap);j=j-gap;}}}returnarr;functionswap(a,b){consttmp=arr[a];arr[a]=arr[b];arr[b]=tmp;}}執行插入時，使用移動法functionshellSort(arr){for(letgap=Math.floor(arr.length/2);gap>0;gap=Math.floor(gap/2)){for(leti=gap;i<arr.length;i++){letj=i;constx=arr[j];//緩存數字，空出位置while(j-gap>=0&&x<arr[j-gap]){arr[j]=arr[j-gap];//將符合條件的數字，填入空出的位置j=j-gap;}arr[j]=x;//最後，將緩存的數字，填入空出的位置}}returnarr;}選擇排序排序的效果圖解法

當前解法為升序

functionselectionSort(arr){constlen=arr.length;for(leti=0;i<len-1;i++){letminIndex=i;for(letj=i+1;j<len;j++){if(arr[j]<arr[minIndex]){minIndex=j;//保存最小數的下標}}consttmp=arr[i];arr[i]=arr[minIndex];arr[minIndex]=tmp;}returnarr;}歸並排序概要

歸並排序，利用分治思想，將大的數組，分解為小數組，直至單個元素。然後，使用選擇排序的方式，對分拆的小數組，進行回溯，並有序合並，直至合並為一個大的數組。

效果圖小數組合並的過程解法functionmergeSort(arr){returnsort(arr,0,arr.length-1);//注意右區間是arr.length-1//sort方法，進行遞歸functionsort(arr,left,right){//當left!==right時，證明還沒分拆到最小元素if(left<right){//取中間值，分拆為兩個小的數組constmid=Math.floor((left+right)/2);constleftArr=sort(arr,left,mid);constrightArr=sort(arr,mid+1,right);//遞歸合並returnmerge(leftArr,rightArr)}//left==right,已經是最小元素，直接返回即可returnleft>=0?[arr[left]]:[];}//合並兩個有序數組functionmerge(leftArr,rightArr){letleft=0;letright=0;consttmp=[];//使用雙指針，對兩個數組進行掃描while(left<leftArr.length&&right<rightArr.length){if(leftArr[left]<=rightArr[right]){tmp.push(leftArr[left++]);}else{tmp.push(rightArr[right++]);}}//合並剩下的內容if(left<leftArr.length){while(left<leftArr.length){tmp.push(leftArr[left++]);}}if(right<rightArr.length){while(right<rightArr.length){tmp.push(rightArr[right++]);}}returntmp;}}插入排序排序的效果圖解法

當前解法為升序

functioninsertionSort(arr){constlen=arr.length;//注意，i從1開始for(leti=1;i<len;i++){letpreIndex=i-1;letcurrent=arr[i];//位置i之前，是已排好序的數字，while的作用是找到一個坑位，給當前數字current插入while(preIndex>=0&&arr[preIndex]>current){arr[preIndex+1]=arr[preIndex];//對大於current的值，往後移一位，給current的插入騰出位置preIndex--;}arr[preIndex+1]=current;}returnarr;}堆排序概要

堆的表示形式

邏輯結構的表示如下：

在物理數據層的表示如下：

堆排序，是選擇排序的優化版本，利用數據結構——樹，對數據進行管理。

以大頂堆為例:

通過構建大頂堆

將堆頂的最大數拿出，與堆底的葉子節點進行交換

接著，樹剪掉最大數的葉子

再對堆進行調整，重新變成大頂堆

返回步驟2，以此循環，直至取出所有數

效果圖

在實現代碼時，構建大頂堆時，先保證左右子樹的有序，再逐步擴大到整棵樹。

構建大頂堆

從第一個非葉子節點開始，調整它所在的子樹

調整下標1節點的子樹後，向上繼續調整它的父節點（下標0）所在的子樹

最後，完成整個樹的調整，構建好大頂堆。

逐個抽出堆頂最大值

堆頂數字與最末尾的葉子數字交換，抽出堆頂數字9。

此時，數字9位置固定下來，樹剪掉9所在的葉子。然後，重新構建大頂堆。

大頂堆構建好後，繼續抽出堆頂數字8，然後再次重新構建大頂堆。

最後，所有節點抽出完成，代表排序已完成。

解法

以大頂堆為例，對數組進行升序排序

注意點樹的最後一個非葉子節點：(arr.length/2)-1非葉子節點i的左葉子節點：i*2+1非葉子節點i的右葉子節點：i*2+2???

functionheapSort(arr){//初次構建大頂堆for(leti=Math.floor(arr.length/2)-1;i>=0;i--){//開始的第一個節點是樹的最後一個非葉子節點//從構建子樹開始，逐步調整buildHeap(arr,i,arr.length);}//逐個抽出堆頂最大值for(letj=arr.length-1;j>0;j--){swap(arr,0,j);//抽出堆頂（下標0）的值，與最後的葉子節點進行交換//重新構建大頂堆//由於上一步的堆頂最大值已經交換到數組的末尾，所以，它的位置固定下來//剩下要比較的數組，長度是j,所以這里的值length==jbuildHeap(arr,0,j);}returnarr;//構建大頂堆functionbuildHeap(arr,i,length){lettmp=arr[i];for(letk=2*i+1;k<length;k=2*k+1){//先判斷左右葉子節點，哪個比較大if(k+1<length&&arr[k+1]>arr[k]){k++;}//將最大的葉子節點，與當前的值進行比較if(arr[k]>tmp){//k節點大於i節點的值，需要交換arr[i]=arr[k];//將k節點的值與i節點的值交換i=k;//注意：交換後，當前值tmp的下標是k，所以需要更新}else{//如果tmp大於左右子節點，則它們的子樹也不用判斷，都是小於當前值break;}}//i是交換後的下標，更新為tmparr[i]=tmp;}//交換值functionswap(arr,i,j){consttmp=arr[i];arr[i]=arr[j];arr[j]=tmp;}}計數排序概要

計數排序的要點，是開辟一塊連續格子組成的空間，給數據進行存儲。將數組中的數字，依次讀取，存入其值對應的下標中。儲存完成後，再按照空間的順序，依次讀取每個格子的數據，輸出即可。

所以，計數排序要求排序的數據，必須是有范圍的整數。

效果圖解法functioncountingSort(arr){letmaxValue=Number.MIN_VALUE;letminValue=Number.MAX_VALUE;letoffset=0;//位移，用於處理負數constresult=[];//取出數組的最大值,最小值arr.forEach(num=>{maxValue=num>maxValue?num:maxValue;minValue=num>minValue?minValue:num;});if(minValue<0){offset=-minValue;}constbucket=newArray(maxValue+offset+1).fill(0);//初始化連續的格子//將數組中的每個數字，根據值放入對應的下標中，//`bucket[num]==n`格子的意義：存在n個數字，值為numarr.forEach(num=>{bucket[num+offset]++;});//讀取格子中的數bucket.forEach((store,index)=>{while(store--){result.push(index-offset);}});returnresult;}桶排序概要

桶排序是計數排序的優化版，原理都是一樣的：分治法+空間換時間。將數組進行分組，減少排序的數量，再對子數組進行排序，最後合並即可得到結果。

效果圖解法

對桶內數字的排序，本文採用的是桶排序遞歸。其實它的本質是退化到計數排序。

functionbucketSort(arr,bucketSize=10){//bucketSize每個桶可以存放的數字區間(0,9]if(arr.length<=1){returnarr;}letmaxValue=arr[0];letminValue=arr[0];letresult=[];//取出數組的最大值,最小值arr.forEach(num=>{maxValue=num>maxValue?num:maxValue;minValue=num>minValue?minValue:num;});//初始化桶的數量constbucketCount=Math.floor((maxValue-minValue)/bucketSize)+1;//桶的數量//初始化桶的容器//注意這里的js語法，不能直接fill([])，因為生成的二維下標數組，是同一個地址constbuckets=newArray(bucketCount).fill(0).map(()=>[]);//將數字按照映射的規則，放入桶中arr.forEach(num=>{constbucketIndex=Math.floor((num-minValue)/bucketSize);buckets[bucketIndex].push(num);});//遍歷每個桶內存儲的數字buckets.forEach(store=>{//桶內只有1個數字或者空桶，或者都是重復數字，則直接合並到結果中if(store.length<=1||bucketSize==1){result=result.concat(store);return;}//遞歸，將桶內的數字，再進行一次劃分到不同的桶中constsubSize=Math.floor(bucketSize/2);//減少桶內的數字區間，但必須是最少為1consttmp=bucketSort(store,subSize<=1?1:subSize);result=result.concat(tmp);});returnresult;}基數排序概述

基數排序，一般是從右到左，對進制位上的數字進行比較，存入[0,9]的10個桶中，進行排序。從低位開始比較，逐位進行比較，讓每個進制位（個、十、百、千、萬）上的數字，都能放入對應的桶中，形成局部有序。

為什麼10個桶？

因為十進制數，是由0-9數字組成，對應的進制位上的數字，都會落在這個區間內，所以是10個桶。

基數排序有兩種方式：

MSD從高位開始進行排序

LSD從低位開始進行排序

效果圖解法

當前解法，只適用正整數的場景。負數場景，需要加上偏移量解決。可參考計數排序的解法。

functionquickSort(arr){sort(arr,0,arr.length-1);returnarr;functionsort(arr,low,high){if(low>=high){return;}leti=low;letj=high;constx=arr[i];//取出比較值x，當前位置i空出，等待填入while(i<j){//從數組尾部，找出比x小的數字while(arr[j]>=x&&i<j){j--;}//將空出的位置，填入當前值，下標j位置空出//ps：比較值已經緩存在變數x中if(i<j){arr[i]=arr[j]i++;}//從數組頭部，找出比x大的數字while(arr[i]<=x&&i<j){i++;}//將數字填入下標j中，下標i位置突出if(i<j){arr[j]=arr[i]j--;}//一直循環到左右指針i、j相遇，//相遇時，i==j,所以下標i位置是空出的}arr[i]=x;//將空出的位置，填入緩存的數字x，一輪排序完成//分別對剩下的兩個區間進行遞歸排序sort(arr,low,i-1);sort(arr,i+1,high);}}0演算法復雜度擴展閱讀

筆者整理的面試筆試題

參考

JAVA十大排序演算法之桶排序詳解

JAVA十大排序演算法之基數排序詳解

圖解排序演算法(三)之堆排序

圖解排序演算法(四)之歸並排序

快速排序QuickSort

圖解排序演算法(二)之希爾排序

最近筆者在整理第一本電子書書稿《前端面試手冊》，有興趣的同學可以關注下～

喜歡我文章的朋友，可以通過以下方式關注我：

「star」或「watch」我的GitHubblog

RSS訂閱我的個人博客：王先生的基地

原文：https://juejin.cn/post/7099436855388536869

3. 根號2的計算方法

可以使用除法來計算的，不過方法比較繁瑣

第一步：整數部分，直接開方，算出最接近數字，可以得到余數

第二步：計算開方的小數部分了，這是最繁瑣的部分，比較麻煩

首先余數部分直接擴大一百倍，除數部分直接乘以20倍，再加上另一個除數

過程如下：

整數部分

後面的部分可以繼續計算下去的，越到後面計算的難度越大，前面的文字解釋部分可能不太清楚，請大家原諒，可以看看計算的部分，自己找找規律的

4. 在C語言中什麼叫選擇法

選擇法是每趟選出一個最值確定其在結果序列中的位置，確定元素的位置是從前往後，而每趟最多進行一次交換，其餘元素的相對位置不變。可進行降序排序或升序排序。
演算法要求：用選擇法對10個整數按降序排序。
基於此思想的演算法主要有簡單選擇排序、樹型選擇排序和堆排序。