① 幾種常見的排序演算法及javaScript實現
前言在學習數據結構和排序演算法過程中,會發現原理和思路都十分簡潔和清晰,難度在於用如何用代碼將過程表達出來,而這就是程序員內功的修煉了。
在學習過程中非常喜歡一句話:「好的演算法就是一本好的食譜,只要按照食譜的步驟進行,小白也能做出美味的烹飪,而學習前人的經典演算法,即使沒有多高的天分,也能幫助你解決很多問題。」
1.選擇排序選擇排序是最容易理解的一種排序演算法。
1.1演算法原理遍歷數據,把數據中的最大值(或者最小值)與起始(或者末尾)數據進行交換。
1.2演算法思路1.從「待排序數據」中找到最小值。
2.把最小值和「待排序數據起止位置的元素」交換。
3.「待排序數據」的起始位置向後移動一位。
4.循環操作1~3,直至「待排序部分」只剩下一個元素。
下圖展示了用選擇排序演算法的過程。
1.3代碼實現let?selectSort?=?(array)?=>?{??for?(let?i?=?0;?i?<?array.length-1;?i++)?{????let?min?=?array[i];//先找到起始值????for(let?j?=?i+1;j<?array.length;j++){??????if(min>?array[j]){//再次循環找到最小值????????let?temp?=?min;//使用臨時變數交換最小值和起始值????????min?=?array[j];????????array[j]?=?temp;??????}????}????array[i]?=?min//將最小值放到數組最前面????}??return?array;}let?testArray?=?[35,80,21,54,11,45,92,39];console.log(selectSort(testArray));測試結果:
1.4演算法效率選擇排序的簡單和直觀名副其實,這也造就了它出了名的慢性子,無論是哪種情況,哪怕原數組已排序完成,它也將花費將近n?/2次遍歷來確認一遍。唯一值得高興的是,它並不耗費額外的內存空間。
平均時間復雜度最好情況最壞情況空間復雜度O(n2)O(n2)O(n2)O(1)2.冒泡排序2.1演算法原理比較相鄰的兩個元素的大小關系,如果大小關系和排序順序是相反的,則交換這兩個元素的位置。
2.2演算法思路1.「待排序數據」的第1個數據和第2個數據相互比較。
2.如果第1個數據>第2個數據,那麼交換兩個數據的位置。
3.進行比較的數據位置向後移動一位。
4.直到比較到最後2個數據,那麼末尾的數據就是最大值。
5.在「待排序數據」裡面除去末尾的最大值,在新的「待排序數據」繼續上述操作。
下圖展示了進行冒泡排序的過程:
2.3代碼實現let?bubbleSort?=?(array)?=>?{??for?(let?i?=?0;?i?<array.length-1?;?i++)?{//最後一個數字不用遍歷?????for?(let?j?=?0;?j?<?array.length-1-i;?j++)?{//每次比較,都要去除末尾已經排好序的值,所以要-i????????if?(array[j]>array[j+1]){//找到較小值,交換位置??????????let?temp?=?array[j];??????????array[j]?=?array[j+1];??????????array[j+1]?=?temp;????????}????}??}??return?array;}let?testArray?=?[35,80,21,54,11,45,92,39];console.log(bubbleSort(testArray));測試結果:
2.4演算法效率冒泡排序是穩定的排序演算法,最容易實現的排序,最壞的情況是每次都需要交換,共需遍歷並交換將近n?/2次,時間復雜度為O(n?).最佳的情況是內循環遍歷一次後發現排序是對的,因此退出循環,時間復雜度為O(n).平均來講,時間復雜度為O(n?).由於冒泡排序中只有緩存的temp變數需要內存空間,因此空間復雜度為常量O(1)平均時間復雜度|最好情況|最壞情況?|空間復雜度||-------|----|-----|-----||O(n2)?|O(n)|O(n2)|O(1)
3.插入排序3.1演算法原理假設一組數據列(D0,D1,D2...,Dn)中的某個數據Di之前的數據列(D0~Di-1)是已經排好序的,那麼把Di按照大小關系插入到已經排好序的數據列中,按此方法一直操作到最後一個數據,就可以完成排序。
3.2演算法思路在開始處理之前,可以認為「已排序部分」只包括數組的起始元素,而「待排序部分」包含第二個元素及其以後的所有元素。排序過程如下:
1.第一個元素被認為已經排好序
2.找到下一個元素,與前面已排序的元素進行對比
3.如果已排序的元素大於待排序元素,將已排序元素後移
4.重復步驟3,直到找到已排序元素小於或者等於待排序元素的位置
5.把待排序元素插入到該位置
6.重復步驟2到5直到最後一個元素。
3.3實現代碼let??insertSort?=?(array)?=>?{??for?(let?i?=?1;?i?<?array.length;?i++)?{//從第二個元素開始循環????let?temp?=?array[i];//把待排序的元素放在臨時變數里,因為後移操作會覆蓋掉待排序元素????let?j?=?i-1;//往前找已經排好序的元素????while(j>=0?&&?array[j]?>?temp){//j<0,會導致找不到數組元素??????array[j+1]?=?array[j];//如果排好序的元素存在比待排序的元素大,就後移??????j--;????}????array[j+1]?=?temp;//把待排序的元素值賦值回來??}??return?array;}let?testArray?=?[35,80,21,54,11,45,92,39];console.log(insertSort(testArray));測試結果:
3.4演算法效率是穩定的排序演算法。平均時間復雜度|最好情況|最壞情況?|空間復雜度||-------|----|-----|-----||O(n2)?|O(n)|O(n2)|O(1)
4.歸並排序4.1演算法原理所謂歸並,指的是把「幾個已排序的數據列」合並成「一個已排序的數據列」,即把待排序列分為若干個子序列,每個子序列都是有序的,然後再把子序列合並成整體有序序列。
4.2演算法思路採用遞歸法:
1.將序列每相鄰兩個數字進行歸並操作,形成floor(n/2)個序列,排序後每個序列包含兩個元素
2.將上述序列再次歸並,形成floor(n/4)個序列,每個序列包含四個元素
3.重復步驟2,直到所有元素歸並完畢
4.進行合並操作,對每個排好的數據列做對比,找到最小值,放到容器中。
5.找到最小值後,原數組的下一個數據就會稱為起始值。
下圖是對3個數據列進行歸並排序的展示,可以看到每次數據列取值之後,下一個數據就會變為起始元素。
4.3代碼實現let?merge?=?(a,b)?=>?{//合並函數??if?(a.length?===?0)?return?b??if?(b.length?===?0)?return?a??return?a[0]?>?b[0]??//每次取值,找到數組中的最小值????[b[0]].concat(merge(a,?b.slice(1)))?://取值後,把數組第二個數據設置為起始值????[a[0]].concat(merge(a.slice(1),?b))}let?mergeSort?=?(array)?=>?{??let?n?=?array.length;??if(n?===?1){return?array}??let?left?=?array.slice(0,Math.floor(n/2));//將數組分割,直到長度為1??let?right?=?array.slice(Math.floor(n/2));??return?merge(mergeSort(left),mergeSort(right))}let?testArray?=?[35,80,21,54,11,45,92,39];console.log(mergeSort(testArray));測試結果:
4.4演算法效率穩定排序演算法,從效率上看,歸並排序可算是排序演算法中的」佼佼者」.假設數組長度為n,那麼拆分數組共需logn,又每步都是一個普通的合並子數組的過程,時間復雜度為O(n),故其綜合時間復雜度為O(nlogn)。另一方面,歸並排序多次遞歸過程中拆分的子數組需要保存在內存空間,其空間復雜度為O(n)。和選擇排序一樣,歸並排序的性能不受輸入數據的影響,但表現比選擇排序好的多,因為始終都是O(nlogn)的時間復雜度。代價是需要額外的內存空間。
平均時間復雜度最好情況最壞情況空間復雜度O(nlogn)O(nlogn)O(nlogn)O(n)5.快速排序5.1演算法原理通過一次排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都小,然後再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以達到整個數據變成有序序列。
5.2演算法思路快速排序使用分治策略來把一個序列(list)分為兩個子序列(sub-lists)。步驟為:1.從數列中挑出一個元素,稱為「基準」(pivot)。
2.重新排序數列,所有比基準值小的元素擺放在基準前面,所有比基準值大的元素擺在基準後面(相同數可以到任一邊)。在這個分區結束之後,該基準就處於數列的中間位置。
3.遞歸地(recursively)把小於基準值元素的子數列和大於基準值元素的子數列排序。
下圖展示了用初始元素作為基準值進行快速排序:
5.3代碼實現let?quickSort?=?(array)?=>?{??if?(array.length?<=1){return?array;}??let?pivotIndex?=?Math.floor(array.length/2);//使用數列中間的元素作為基準??let?pivot?=?array.splice(pivotIndex,1)[0];??let?left?=?[];??let?right?=?[];??for?(let?i?=?0;?i?<?array.length;?i++)?{????if?(array[i]?<?pivot){//比基準值小的放在前面,大的或者等於的放在後面??????left.push(array[i])????}else?{right.push(array[i])}??}??return?quickSort(left).concat([pivot],quickSort(right))//遞歸子數組}let?testArray?=?[35,80,21,54,11,45,92,39];console.log(quickSort(testArray));測試結果:
5.4演算法效率快速排序並不穩定,快速排序每次交換的元素都有可能不是相鄰的,因此它有可能打破原來值為相同的元素之間的順序。
平均時間復雜度最好情況最壞情況空間復雜度O(nlogn)O(nlogn)O(n2)O(1)6.希爾排序6.1演算法原理把數據按照一定間隔分割成不同的組,並且對每個組進行插入排序。
6.2演算法思路1.把分組間隔gap初始化為N/2(商的整數部分)
2.當gap當於1的時候,循環執行
3.把數據列以gap為間隔分組
4.對每一組進行插入排序
5.把gap/2代入gap。
下圖展示了使用希爾排序的過程
6.3代碼實現let?insertSortGap?=?(array,gap)?=>?{//這段代碼的解釋可以往上看插入排序的注釋????for(let?i?=?gap;i<?array.length;i++){??????let?temp?=?array[i];??????let?j?=?i-gap;??????while?(j>=?0?&&?array[j]?>?temp){????????array[j+gap]?=?array[j];????????j?-=?gap??????}??????array[j+gap]?=?temp????}}let?shellSort?=?(array)?=>?{??let?gap?=?Math.floor(array.length/2);??while?(gap>=1){????insertSortGap(array,gap)//分組後調用快速排序????gap?=?Math.floor(gap/2)??}??return?array}let?testArray?=?[35,80,21,54,11,45,92,39];console.log(shellSort(testArray));測試結果:
6.4演算法效率不穩定排序演算法,希爾排序第一個突破O(n2)的排序演算法;是簡單插入排序的改進版;它與插入排序的不同之處在於,它會優先比較距離較遠的元素,直接插入排序是穩定的;而希爾排序是不穩定的,希爾排序的時間復雜度和步長的選擇有關平均時間復雜度|最好情況|最壞情況?|空間復雜度||-------|----|-----|-----||O(n1.3)?|O(n)|O(n2)|O(1)
後續除了以上的6種演算法外,常用的還有計數排序和推排序演算法,堆排序演算法的涉及到二叉樹數據結構的知識,後面再慢慢補充把。
原文:https://juejin.cn/post/7094903421018472479
② web前端開發需要哪些技能
一、HTML5+CSS3
HTML5和CSS3是通往Web工程師路上必須學會的基本內容,主要包括了解常用瀏覽器和瀏覽器內核;了解語義化的概念;掌握HTML5語法及使用技巧;掌握HTML5常用標簽。掌握CSS語法及使用技巧;掌握DIV+CSS布局方式;掌握常見網頁布局模式。掌握HTML5新布局標簽、多媒體標簽;掌握CSS32D、3D變換、動畫效果;能夠使用CSS3新屬性美化修飾網頁;了解移動端屏幕、移動端瀏覽器、操作系統的不同等內容。
二、js交互設計
JS交互技術可以賦予頁面一個動態的效果展示,提升用戶的瀏覽體驗,這部分主要是通過JS的學習掌握JavaScript基本語法;掌握常見JavaScript演算法;掌握DOM的各種操作;熟練使用面向對象思想進行DOM編程;掌握JavaScript的高級語法;掌握JavaScript常見兼容性方案。熟練使用jQuery操作DOM;熟練使用和編寫jQuery案例。
三、Node開發
Node.js不僅僅是一個框架,它是一個完整的JavaScript環境,配備了開發人員可能需要的開發工具。所以學好Node是在打通前後端開發中需要掌握的技術。這部分需要掌握ES6的基礎用法和兼容性;掌握ES6的核心語法;使用ES6實現前端模塊化開發。使用Webpack模塊打包器;使用Node.js進行Web服務端開發;掌握JavaScript非同步編程模型;掌握JavaScript模塊化編程方式;使用Node.js操作MongoDB資料庫;獨立開發基於後台介面的動態網站、Ajax數據交互的項目;獨立完成企業網站從前台到後台的基本開發工作。
四、前端框架
前端框架是Web開發人員需要熟練掌握的技能,並且在實際開發中是會被廣泛應用的,那麼對於前端框架方面需要掌握現在主流的Vue、React、Angular等,掌握D3.js進行大數據可視化交互開發;掌握Vue技術棧進行項目開發;掌握React技術棧進行項目開發;掌握使用主流框架開發門戶網站、管理系統、移動Web等客戶端;掌握Webpack項目構建配置流程;掌握Web項目的部署與發布模式;掌握常見網站業務模塊開發等。
五、小程序與APP開發現在移動應用越來越受歡迎,掌握了小程序和APP開發技術可以增強自身競爭力,這就需要掌握小程序的開發基礎;能夠獨立開發小程序項目;能夠掌握Canvas的使用;能夠掌握小程序的部署與發布;能夠掌握小程序開發框架mpvue的使用;掌握第三方AI平台的使用。能夠掌握小游戲開發基礎;能夠獨立開發小游戲項目;能夠掌握小游戲的部署與發布;能夠獨立使用ReactNative開發原生App。
視頻教程:
網頁鏈接
③ javascript演算法題,26個字母和數字轉換,怎麼做
26個字母轉為ASCII碼:
varc='A';
console.log(c.charCodeAt(0));
26個字母轉換為1~26對應專的數字:屬
varc='A';//字母
console.log(c.toLocaleLowerCase().charCodeAt(0)-96);
④ web前端javascript能實現什麼演算法或者計算
在Web開發中,JavaScript很重要,演算法也很重要。下面整理了一下一些常見的演算法在JavaScript下的實現,包括二分法、求字元串長度、數組去重、插入排序、選擇排序、希爾排序、快速排序、冒泡法等等。僅僅是為了練手,不保證高效與美觀,或許還有Bug,有時間再完善吧。
1.二分法:
function binary(items,value){
var startIndex=0,
stopIndex=items.length-1,
midlleIndex=(startIndex+stopIndex)>>>1;
while(items[middleIndex]!=value && startIndex
if(items[middleIndex]>value){
stopIndex=middleIndex-1;
}else{
startIndex=middleIndex+1;
}
middleIndex=(startIndex+stopIndex)>>>1;
}
return items[middleIndex]!=value ? false:true;
}
2.十六進制顏色值的隨機生成:
function randomColor(){
var arrHex=["0","2","3","4","5","6","7","8","9","a","b","c","d"],
strHex="#",
index;
for(var i=0;i < 6; i++){
index=Math.round(Math.random()*15);
strHex+=arrHex[index];
}
return strHex;
}
一個求字元串長度的方法:
function GetBytes(str){
var len=str.length,
bytes=len;
for(var i=0;i < len;i++){
if(str.CharCodeAt>255){
bytes++;
}
}
return bytes;
}
3.js實現數組去重:
Array.protype.delRepeat=function(){
var newArray=new Array();
var len=this.length;
for(var i=0;i < len;i++){
for(var j=i+1;j < len;j++)
{
if(this[i]==this[j])
{
++i;
}
}
newArray.push(this[i]);
}
return newArray;
}
4.插入排序。所謂的插入排序,就是將序列中的第一個元素看成一個有序的子序列,然後不段向後比較交換比較交換。
function insertSort(arr){
var key;
for(var j = 1; j < arr.length ; j++){
//排好序的
var i = j - 1;
key = arr[j];
while(i >= 0 && arr[i] > key){
arr[i + 1] = arr[i];
i --;
}
arr[i + 1] = key;
}
return arr;
}
5.選擇排序。其實基本的思想就是從待排序的數組中選擇最小或者最大的,放在起始位置,然後從剩下的數組中選擇最小或者最大的排在這公司數的後面。
function selectionSort(data)
{
var i, j, min, temp , count=data.length;
for(i = 0; i < count - 1; i++) {
/* find the minimum */
min = i;
for (j = i+1; j < count; j++)
{
if (data[j] < data[min])
{ min = j;}
}
/* swap data[i] and data[min] */
temp = data[i];
data[i] = data[min];
data[min] = temp;
}
return data;
}
6.希爾排序,也稱遞減增量排序演算法。其實說到底也是插入排序的變種。
function shellSort(array){
var stepArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; //
reverse()在維基上看到這個最優的步長較小數組
var i = 0;
var stepArrLength = stepArr.length;
var len = array.length;
var len2 = parseInt(len/2);
for(;i < stepArrLength; i++){
if(stepArr[i] > len2){
continue;
}
stepSort(stepArr[i]);
}
// 排序一個步長
function stepSort(step){
//console.log(step) 使用的步長統計
var i = 0, j = 0, f, tem, key;
var stepLen = len%step > 0 ? parseInt(len/step) + 1 : len/step;
for(;i < step; i++){// 依次循環列
for(j=1;/*j < stepLen && */step * j + i < len;
j++){//依次循環每列的每行
tem = f = step * j + i;
key = array[f];
while((tem-=step) >= 0){// 依次向上查找
if(array[tem] > key){
array[tem+step] = array[tem];
}else{
break;
}
}
array[tem + step ] = key;
}
}
}
return array;
}
7.快速排序。其實說到底快速排序演算法就系對冒泡排序的一種改進,採用的就是演算法理論中的分治遞歸的思想,說得明白點,它的做法就是:通過一趟排序將待排序的紀錄分割成兩部分,其中一部分的紀錄值比另外一部分的紀錄值要小,就可以繼續分別對這兩部分紀錄進行排序;不段的遞歸實施上面兩個操作,從而實現紀錄值的排序。
function quickSort(arr,l,r){
if(l < r){
var mid=arr[parseInt((l+r)/2)],i=l-1,j=r+1;
while(true){
while(arr[++i] < mid);
while(arr[--j]>mid);
if(i>=j)break;
var temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
quickSort(arr,l,i-1);
quickSort(arr,j+1,r);
}
return arr;
}
8.冒泡法:
function bullSort(array){
var temp;
for(var i=0;i < array.length;i++)
{
for(var j=array.length-1;j > i;j--){
if(array[j] < array[j-1])
{
temp = array[j];
array[j]=array[j-1];
array[j-1]=temp;
}
}
}
return array;
}