前端程序員面試分類真題23

前端程序員面試分類真題23簡答題1.

一群猴子排成一圈，按1，2，…，n依次編號。然后從第1只開始數(shù)，數(shù)到第m只，把它踢出圈，從它后面再開始數(shù)，數(shù)到第m只，再把它踢出去……，如此不停地進行下去，直到最后只（江南博哥）剩下一只猴子為止，那只猴子就稱為大王。要求編程模擬此過程，輸入m、n輸出最后那個大王的編號。正確答案：首先將猴子從1到n編號存放在數(shù)組中，對猴子的總個數(shù)進行循環(huán)，循環(huán)時將數(shù)到編號的猴子從數(shù)組刪除，而沒有數(shù)到編號的猴子將調(diào)整位置，移動到數(shù)組末尾。只要判斷該編號數(shù)組元素個數(shù)大于1就繼續(xù)循環(huán)，直到數(shù)組最后只剩下一個編號，那么這個編號對應(yīng)的猴子就是大王。實現(xiàn)代碼為：

functionmonkeyKing(n,m){

//將各個編號放入數(shù)組中

varmonkeys=newArray(n+1)

.join("0")

.split("")

.map(function(value,key){

returnkey+1;

});

//只有一個編號就直接返回

if(n==1){

returnmonkeys[0];

}

vari=0;

//如果當前只有一個編號,那么其他位置中都不會存在編號

while(monkeys.length-2inmonkeys){

if((i+1)%m==0){

//數(shù)到m時,刪除該編號,即踢出圈

deletemonkeys[i];

}else{

//將當前編號放到數(shù)組末尾并且刪除原來位置上的編號

monkeys,push(monkeys[i]);

deletemonkeys[i];

}

i++;

}

//只有數(shù)組的最后位置存在編號

returnmonkeys[monkeys.length-1];

}

varmonkey=monkeyKing(5,2);

console.log("最后當王的猴子編號是:"+monkey);

//3[考點]經(jīng)典算法題

2.

漢諾塔(又稱河內(nèi)塔)問題是印度的一個古老傳說。開天辟地的神勃拉瑪在一個廟里留下了三根金剛石棒，第一根上面套著64個圓的金片，最大的一個在底下，其余一個比一個小，依次疊上去。廟里的眾僧不倦地把它們一個個從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每次只能搬一個，而且大的不能放在小的上面。經(jīng)過運算移動圓片的次數(shù)為18446744073709551615，看來眾僧們耗盡畢生精力也不可能完成金片的移動。

后來，這個傳說就演變?yōu)闈h諾塔游戲，游戲規(guī)則如下：

(1)有三根桿子A、B、C，A桿上有若干碟子。

(2)每次移動一塊碟子，小的只能疊在大的上面。

(3)把所有碟子從A桿全部移到C桿上。

(4)經(jīng)過研究發(fā)現(xiàn)，漢諾塔的破解很簡單，就是按照移動規(guī)則向一個方向移動金片。

(5)如3階漢諾塔的移動：A→C，A→B，C→B，A→C，B→A，B→C，A→C。

此外，漢諾塔問題也是程序設(shè)計中的經(jīng)典遞歸問題。正確答案：如果柱子標為A、B、C，要由A搬至C，在只有一個盤子時，就將它直接搬至C，當有兩個盤子，就將B當作輔助柱。如果盤數(shù)超過兩個，將第三個以下的盤子遮起來，就很簡單了，即每次處理兩個盤子，也就是A-＞B、A-＞C、B-＞C這三個步驟，而被遮住的部分，其實就是進入程序的遞歸處理。事實上，若有n個盤子，則移動完畢所需次數(shù)為2^n-1，所以當盤數(shù)為64時，所需次數(shù)為2^64-1=18446744073709551615，為5.05390248594782e+16年，如果對這個數(shù)字沒什么概念，可假設(shè)每秒鐘搬一個盤子，也要約5850億年左右。實現(xiàn)代碼為：

functionhanou(n,x,y,Z){

if(n==1){

console.log("移動片1從"+x+"到"+z);

}else{

hanou(n-1,x,z,y);

console.log("移動片"+n+"從"+x+"到"+z);

hanou(n-1,y,x,z);

}

}

hanou(3,"A","B","C");

程序的運行結(jié)果為：

移動片1從A到C

移動片2從A到B

移動片1從C到B

移動片3從A到C

移動片1從B到A

移動片2從B到C

移動片1從A到C[考點]經(jīng)典算法題

3.

據(jù)說著名猶太歷史學家Josephus有過以下的故事。在羅馬人占領(lǐng)喬塔帕特后，39個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式：41個人排成一個圓圈，由第1個人開始報數(shù)，每到第3個人該人就必須自殺，然后再由下一個重新開始報數(shù)，直到所有人都自殺身亡為止。

然而Josephus和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。

約瑟夫問題可用代數(shù)分析來求解，假設(shè)現(xiàn)在你與m個朋友不幸參與了這個游戲，你要如何保護你與你的朋友?正確答案：實際上只要畫兩個圓圈就可以讓自己與朋友免于死亡游戲，這兩個圓圈中內(nèi)圈是排列順序，而外圈是自殺順序，如下圖所示。

排列順序和自殺順序

如果要使用公式來求解，那么只要將排列當作環(huán)狀來處理，在陣列中由計數(shù)1開始，每三個數(shù)得到一個計數(shù)，直到計數(shù)達41為止；然后將陣列由索引1開始列出，就可以得知每個位置的自殺順序，這就是約瑟夫排列。41個人報數(shù)的約琴夫排列如下所示。

1436138152243031634425175403161826737198352792032104121112839122233132923

由上可知，最后一個自殺的是在第31個位置，而倒數(shù)第二個自殺的要排在第16個位置，之前的人都死光了，所以他們也就不知道約琴夫與他的朋友并沒有遵守游戲規(guī)則了。實現(xiàn)代碼為：

varN=41,M=3,man=[],

count=1,i=0,pos=-1,

alive=3;

//想救的人數(shù)

while(count＜=N){

do{

pos=(pos+1)%N;

//環(huán)狀處理

if(!man[pos])

i++;

i=f(i==M){

//報數(shù)為3

i=0;

break;

}

}while(1);

man[pos]=count;

count++;

}

console.log("約琴夫排列:",man.join(""));

vartxt="L表示要救的"+alive+"個人要放的位置:";

for(i=0;i＜N;i++){

if(man[i]＞(N-alive))

txt+="L";

else

txt+="D";

if((i+1)%5=0)

txt+="";

}

console.log(txt);

程序的運行結(jié)果為：

約琴夫排列：1436138152243031634425175403161826737198352792032104121112839122233132923

L表示要救的3個人要放的位置：DDDDDDDDDDDDDDDLDDDDDDDDDDDDDDLDDDLDDDDDD[考點]經(jīng)典算法題

4.

在三位的整數(shù)中，例如153可以滿足1^3+5^3+3^3=153，這樣的數(shù)稱之為Armstrong數(shù)，試寫出一程序找出所有三位數(shù)的Armstrong數(shù)。正確答案：Armstrong數(shù)的尋找，其實是將一個數(shù)字分解為個位數(shù)、十位數(shù)、百位數(shù)……，只要使用除法與余數(shù)運算即可求出個、十、百位的數(shù)字，例如輸入一個數(shù)字為abc，則：

百位：a=Math.floor(input/100)

十位：b=Math.floor((input%100)/10)

個位：c=input%10

實現(xiàn)代碼為：

vara,b,c,x,y,txt="Armstrong數(shù):";

for(varnum=100;num＜=999;num++){

a=Math.floor(num/100);

b=Math.floor((num%100)/10);

c=num%10;

x=a*a*a+b*b*b+c*c*c;

y=num;

if(x==num)

txt+=num+"";

}

console.log(txt);

//153370371407[考點]經(jīng)典算法題

5.

將一組數(shù)字、字母或符號進行排列，以得到不同的組合順序，例如123這三個數(shù)的排列組合有：123、132、213、231、312和321。正確答案：可以使用遞歸將問題切割為較小的單元進行排列組合，例如1234的排列可以分為1[234]、2[134]、3[124]、4[123]進行排列。這個過程可以使用旋轉(zhuǎn)法來實現(xiàn)，即先將旋轉(zhuǎn)間隔設(shè)為0，再將最右邊的數(shù)字旋轉(zhuǎn)至最左邊，并逐步增加旋轉(zhuǎn)的間隔，然后對后面的子數(shù)組使用遞歸的方式進行求解。例如：

1234-＞旋轉(zhuǎn)1-＞繼續(xù)將右邊234進行遞歸處理。

2134-＞旋轉(zhuǎn)12變?yōu)?1-＞繼續(xù)將右邊134進行遞歸處理。

3124-＞旋轉(zhuǎn)123變?yōu)?12-＞繼續(xù)將右邊124進行遞歸處理。

4123-＞旋轉(zhuǎn)1234變?yōu)?123-＞繼續(xù)將右邊123進行遞歸處理。

實現(xiàn)代碼為：

varN=4,

num=[];

for(vari=1;i＜=N;i++)

num[i]=i;

perm(num,1);

functionperm(num,i){

varj,k,tmp;

if(i＜N){

for(j=i;j＜=N;j++){

tmp=num[j];

//旋轉(zhuǎn)該區(qū)段最右邊數(shù)字至最左邊

for(k=j;k＞i;k--)

num[k]=num[k-1];

num[i]=tmp;

perm(num,i+1);

//還原

for(k=i;k＜j;k++)

num[k]=num[k+1];

num[j]=tmp;

}

}else{

//顯示此次排列

vartxt="";

for(j=1;j＜=N;j++)

txt+=num[j]+"";

console.log(txt);

}

}

程序的運行結(jié)果為：

1234

1243

1324

1342

1423

1432

……(由于結(jié)果較長，此處省略羅列)[考點]經(jīng)典算法題

6.

古典問題：若有一只兔子每個月生一只小兔子，小兔子一個月后也開始生產(chǎn)。起初只有一只兔子，一個月后就有兩只兔子，二個月后就有三只兔子，三個月后有五只兔子(小兔子投入生產(chǎn))，n個月后有多少只兔子?正確答案：兔子的出生規(guī)律數(shù)列為1，1，2，3，5，8，13，21，…實際上是求解斐波那契數(shù)列，公式為：S(n)=S(n-1)+S(n-2)。首先用k表示要求解多少個月，k1表示上個月的兔子數(shù)量，k2代表上上個月的兔子數(shù)量，sum為兔子的總數(shù)。然后從1月開始循環(huán)，通過斐波那契數(shù)列公式得到sum=k1+k2，之后，把k1(上個月的兔子數(shù)量)賦值給k2(上上個月的兔子數(shù)量)，再把sum(當月的兔子總數(shù))賦值給k1(上個月的兔子數(shù)量)。循環(huán)結(jié)束后輸出的sum就是兔子的總數(shù)了。JavaScript代碼實現(xiàn)為：

vark=12,

//一共12個月

k1=1,

//記錄上個月兔子數(shù)量

k2=0,

//記錄上個月兔子數(shù)量

sum=0;

//總和

for(vari=1;i＜k;i++){

sum=k1+k2;

//當月的兔子和

k2=k1;

//上個月的兔子數(shù)量賦值給上上個月的記錄

k1=sum;

//當月的兔子數(shù)量賦值給上個月的記錄

}

console.log(sum);

//144[考點]經(jīng)典算法題

7.

請根據(jù)楊輝三角的規(guī)律，用JavaScript實現(xiàn)楊輝三角。正確答案：楊輝三角是二項式系數(shù)在三角形中的一種幾何排列，歐洲的帕斯卡在1654年發(fā)現(xiàn)這個規(guī)律，所以也叫帕斯卡三角形。楊輝三角具有以下規(guī)律：

(1)第n行的數(shù)字有n項。

(2)第n行的數(shù)字和為2^(n-1)。

(3)每行數(shù)字左右對稱，由1逐漸增大。

(4)第n行的m個數(shù)可表示為C(n-1，m-1)，即為從n-1個不同元素中取m-1個元素的組合數(shù)。

(5)每個數(shù)字等于上一行的左右兩個數(shù)字之和，即第n+1行的第i個數(shù)等于第n行的第i-1個數(shù)和第i個數(shù)之和，這是楊輝三角組合數(shù)的性質(zhì)之一。即C(n+1，i)=C(n，i)+C(n，i-1)。

根據(jù)楊輝三角的規(guī)律，可以通過一個二維數(shù)組，把第一位和最后一位的值存入數(shù)組，然后通過公式C(n+1，i)=C(n，i)+C(n，i-1)遍歷二維數(shù)組求出每行其余的值。JavaScript代碼實現(xiàn)為：

vara=[],

i,j,txt;

for(i=0;i＜6;i++){

a[i]=[];

a[i][0]=1;

a[i][i]=1;

}

//將第一位和最后一位以外的值保存在數(shù)組中

for(i=2;i＜6;i++){

for(j=1;j＜i;j++){

a[i][j]=a[i-1][j-1]+a[i-1][j];

}

}

for(i=0;i＜6;i++){

txt="";

for(j=0;j＜=i;j++){

txt+=a[i][j]+"";

}

console.log(txt);

}

程序的運行結(jié)果為：

1

11

121

1331

14641

15101051[考點]經(jīng)典算法題

8.

有一母牛，到4歲可生育，每年一頭，假設(shè)所生均是一樣的母牛，到15歲絕育，不再能生，20歲死亡，問n年后有多少頭牛?正確答案：根據(jù)條件定義一個函數(shù)，參數(shù)n代表多少年，定義最開始牛的數(shù)量為1。在循環(huán)中，當母牛年齡大于4并且小于15時，每年可以生一頭小牛(即牛的總數(shù)加1)，然后遞歸調(diào)用這個函數(shù)，函數(shù)的參數(shù)為n減去已過去的年數(shù)。另外，函數(shù)內(nèi)還要實現(xiàn)牛的年齡為20時，牛的數(shù)量減1。實現(xiàn)代碼為：

varnum=1;

functionbull(n){

for(varj=1;j＜=n;j++){

if(j＞=4&&j＜15){

num++;

bull(n-j);

}

if(j==20){

num--;

}

}

returnnum;

}

console.log(bull(8));

//7[考點]經(jīng)典算法題

9.

公雞5文錢1只，母雞3文錢1只，小雞1文錢買3只，現(xiàn)在用100文錢共買了100只雞，假設(shè)每種至少一只，問：在這100只雞中，公雞、母雞和小雞各是多少只?正確答案：根據(jù)百錢買百雞的要求，可以設(shè)有i只公雞，j只母雞，k只小雞，并且它們的總數(shù)為100，總價i×5+j×3+k×1為100文錢。依次對公雞、母雞、小雞的總數(shù)進行循環(huán)來求出符合這兩個公式的最優(yōu)解。實現(xiàn)代碼為：

vari,j,k;

for(i=1;i＜100;i++){

for(j=1;j＜100;j++){

for(k=1;k＜100;k++){

if((i+j+k==100)&&(i*5+j*3+k/3=100)){

console.log("公雞:",i,'只,母雞:',j,'只,小雞:',k,'只');

}

}

}

}

程序的運行結(jié)果為：

公雞:4只,母雞:18只,小雞:78只

公雞:8只,母雞:11只,小雞:81只

公雞:12只,母雞:4只,小雞:84只[考點]經(jīng)典算法題

10.

假設(shè)某人有100,000現(xiàn)金，每經(jīng)過一次路口需要進行一次交費。交費規(guī)則為當現(xiàn)金大于50,000時每次需要交現(xiàn)金的5%，當現(xiàn)金小于或等于50,000時每次交5,000。請寫一程序計算此人可以經(jīng)過多少次路口。正確答案：初始條件為某人擁有的總現(xiàn)金為100,000，初始經(jīng)過路口的次數(shù)為0，當金額低于5,000時，不能再過路口。所以可以通過循環(huán)來求次數(shù)，當現(xiàn)金大于50,000時，剩余金額為：總金額×(1-5%)，當現(xiàn)金小于50,000時，剩余金額為：總金額-5000，依次循環(huán)累加過路口的次數(shù)，直到不符合條件退出循環(huán)。實現(xiàn)代碼為：

varsum,num;

for(sum=100000,num=0;sum＞=5000;){

if(sum＞=50000){

sum=0.95*sum;

}else{

sum=sum-5000;

}

num++;

}

console,log(num);

//23[考點]經(jīng)典算法題

11.

一個球從100米高度自由落下，每次落地后反跳回原高度的一半后再落下。求它在第10次落地時，共經(jīng)過多少米?第10次反彈多高?正確答案：根據(jù)題目要求，設(shè)初始總高度為100米，已知每次下落后反彈回的高度為上一次的一半，循環(huán)10次，每次循環(huán)都對上次反彈后的高度除以2并且將結(jié)果累加到總高度中，從而求解出共經(jīng)過多少米和第10次的反彈高度。實現(xiàn)代碼為：

vark=100,

sum=100;

for(vari=1;i＜=10;i++){

k/=2;

sum+=k;

}

console.log("共經(jīng)過:",sum,"米,第10次反彈高:",k,"米");

程序的運行結(jié)果為：

共經(jīng)過:199.90234375米,第10次反彈高:0.09765625米[考點]經(jīng)典算法題

12.

一個數(shù)如果恰好等于它的因子之和，這個數(shù)就稱為“完數(shù)”，例如6=1+2+3。編程找出1000以內(nèi)的所有完數(shù)。正確答案：外層循環(huán)1000次，每次循環(huán)得到的i傳入下個循環(huán)內(nèi)，內(nèi)部循環(huán)求解出能夠整除i的數(shù)k，如果整除，即說明k是i的一個因子，再用sum累加k，直到sum+1=i的條件成立，說明i是一個完數(shù)。需要注意的是求解出的因子是不包括1的，所以還需要額外的加1到sum中，并且i的因子是不會大于i/2的，所以判斷內(nèi)部循環(huán)是否繼續(xù)的條件為不大于i/2。實現(xiàn)代碼為：

vari,sum,k,txt="";

for(i=2;i＜=1000;i++){

sum=0;

for(k=2;k＜=i/2;k++){

if(i%k==0){

sum+=k;

}

}

if(sum+1==i){

txt+=i+"";

}

}

console.log(txt);

//628496[考點]經(jīng)典算法題

13.

猴子第一天摘了若干個桃子，當即吃了一半，還不解饞，又多吃了一個；第二天，吃剩下桃子的一半，還不過癮，又多吃了一個；以后每天都吃前一天剩下的一半多一個，到第10天想再吃時，只剩下一個桃子了。問第一天共摘了多少個桃子?正確答案：采用逆向思維，從后往前推斷，發(fā)現(xiàn)其中有相同的地方，即出現(xiàn)遞推公式，因此，可以采用遞歸方法。令S10=1，可以得出S9=2(S10+1)，簡化羅列關(guān)系為：

S9=2S10+2

S8=2S9+2

…

Sn=2Sn+2

實現(xiàn)代碼為：

varS=0,

n=1;

//最后一天桃子的數(shù)量

for(vari=1;i＜10;1++){

s=(n+1)*2;

n=s;

}

console.log("第一天摘的桃子數(shù)量為",s);

//1534[考點]經(jīng)典算法題

14.

請談?wù)勀銓ε判虻睦斫狻Ｕ_答案：使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減排列起來的操作叫作排序。排序算法就是如何使得記錄按照要求進行排列的方法。排序算法在很多領(lǐng)域都得到了相當?shù)闹匾?，尤其是在大量?shù)據(jù)的處理方面。一個優(yōu)秀的算法可以節(jié)省大量的資源。在各個領(lǐng)域中考慮到數(shù)據(jù)的各種限制和規(guī)范，要得到一個符合實際的優(yōu)秀算法，需要經(jīng)過大量的推理和分析。

例如：隨機輸入一個包含n個數(shù)的序列：a1，a2，a3，…，an，通過算法輸出n個數(shù)的順序排列：a1'，a2'，a3'，…，an'，使得a1'≤a2'≤a3'≤…≤an'(也可以實現(xiàn)從大到小的排序，不唯一)。[考點]排序算法

15.

排序算法包含諸多術(shù)語，例如穩(wěn)定性、內(nèi)排序、時間復雜度等，請列舉出你所知的術(shù)語并加以說明。正確答案：術(shù)語如下所列。

(1)穩(wěn)定性：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。

(2)不穩(wěn)定性：如果a原本在b的前面，而a=b，排序之后a可能會出現(xiàn)在b的后面。

(3)內(nèi)排序：所有排序操作都在內(nèi)存中完成。

(4)外排序：由于數(shù)據(jù)太大，因此把數(shù)據(jù)放在磁盤中，而排序通過磁盤和內(nèi)存的數(shù)據(jù)傳輸才能進行。

(5)時間復雜度：一個算法執(zhí)行所耗費的時間。

(6)空間復雜度：運行完一個程序所需內(nèi)存的大小。[考點]排序算法

16.

請列舉出你所知的排序算法的平均時間復雜度、最好情況、最壞情況、空間復雜度和穩(wěn)定性。正確答案：排序算法的參數(shù)對比如下表所列。九種排序算法對比排序算法平均時間復雜度最好情況最壞情況空間復雜度排序方法穩(wěn)定性冒泡排序O(n2)O(n)O(n2)O(l)In-place穩(wěn)定插入排序O(n2)O(n)O(n2)O(l)In-place穩(wěn)定歸并排序O(nlogn)O(nlogn)O(nlogn)O(n)Out-pace穩(wěn)定快速排序O(nlogn)O(nlogn)O(n2)O(logn)In-place不穩(wěn)定選擇排序O(n2)O(n2)O(n2)O(l)In-place不穩(wěn)定希爾排序O(nlogn)O(nlog2n)O(nlog2n)O(l)In-place不穩(wěn)定堆排序O(nlogn)O(nlogn)O(nlogn)O(l)In-place不穩(wěn)定計數(shù)排序O(n+k)O(n+k)O(n+k)O(k)Out-place穩(wěn)定桶排序O(n+k)O(n+k)O(n2)O(n+k)Out-place穩(wěn)定

注釋：n表示數(shù)據(jù)規(guī)模；k表示“桶”的個數(shù)；In-place表示占用常數(shù)內(nèi)存，不占用額外內(nèi)存；Out-place表示占用額外內(nèi)存。[考點]排序算法

17.

請用JavaScript實現(xiàn)插入排序。正確答案：插入排序的基本思想是：對于給定的一組記錄，初始時假設(shè)第一個記錄自成一個有序序列，其余的記錄為無序序列；接著從第二個記錄開始，按照記錄的大小依次將當前處理的記錄插入之前的有序序列中，直至最后一個記錄插入有序序列中為止。算法原理如下：

(1)設(shè)置監(jiān)視哨r[0]，將待插入記錄的值賦值給r[0]。

(2)設(shè)置開始查找的位置j。

(3)在數(shù)組中進行搜索，搜索中將第j個記錄后移，直至r[0]≥r[j]為止。

(4)將r[0]插入r[i+1]的位置上。

以數(shù)組[38,65,97,76,13,27,49]為例，直接插入排序具體步驟如下所示。

第一步插入38以后：[38]659776132749

第二步插入65以后：[3865]9776132749

第三步插入97以后：[386597]76132749

第四步插入76以后：[38657697]132749

第五步插入13以后：[1338657697]2749

第六步插入27以后：[132738657697]49

第七步插入49以后：[13273849657697]

根據(jù)以上的實現(xiàn)原理，具體的實現(xiàn)代碼如下所示。

functioninsertSort(arr){

vartmp;

//已經(jīng)間接將數(shù)組分成了兩部分,下標小于當前位置的(左邊的)是排好序的序列

for(vari=1,len=arr.length;i＜len;i++){

//獲得當前需要比較的元素值

tmp=arr[i];

//內(nèi)層循環(huán),控制比較并插入

for(varj=i-1;j＞=0;j--){

if(tmp＜arr[j]){

arr[j+1]=arr[j];

arr[j]=tmp;

}else{

break;

}

}

}

returnarr;

}

可以對傳統(tǒng)的插入排序算法進行改進，在查找插入位置時使用二分查找的方式。改進后的插入排序算法如下所示。

functioninsertSort2(arr){

varkey,left,right,middle;

for(vari=1;i＜arr.length;i++){

key=arr[i];

left=0;

right=i-1;

whileleft＜=right){

middle=Math.floor((left+right)/2);

if(key＜arr[middle]){

right=middle-1;

}else{

left=middle+1;

}

}

for(varj=i-1;j＞=left;j--){

arr[j+1]=arr[j];

}

arr[left]=key;

}

returnarr;

}[考點]排序算法

18.

請用JavaScript實現(xiàn)選擇排序。正確答案：選擇排序是一種簡單直觀的排序算法，它的基本原理如下：對于給定的一組記錄，經(jīng)過第一輪比較后得到關(guān)鍵字最小的記錄，然后將該記錄與第一個記錄的位置進行交換；接著對不第一個記錄以外的其他記錄進行第二輪比較，得到關(guān)鍵字最小的記錄并將它與第二個記錄進行位置交換；重復該過程，直到需要比較的記錄只有一個時為止。算法原理如下。

每一輪在n-i+1(i=1，2，…，n-1)個記錄中選擇關(guān)鍵字最小的記錄作為有序序列中第i個記錄，其中最便捷的是簡單選擇排序，其過程如下：通過n-i次關(guān)鍵字間的比較，從(n-i+1)個記錄中選擇出關(guān)鍵字最小的記錄，并與第i個記錄交換位置。

以數(shù)組[38，65，97，76，13，27，49]為例，具體步驟如下。

第一輪排序后：13[659776382749]

第二輪排序后：1327[9776386549]

第三輪排序后：132738[76976549]

第四輪排序后：13273849[976576]

第五輪排序后：1327384965[9776]

第六輪排序后：132738496576[97]

最后排序結(jié)果：13273849657697

根據(jù)以上實現(xiàn)原理，具體的實現(xiàn)代碼如下所示。

functionselectSort(arr){

varlen=arr.length,

p,tmp,

//外層控制輪數(shù)

for(vari=0;i＜len-1;1++){

p=i;

//先假設(shè)最小值的位置

//內(nèi)層控制比較次數(shù),比較i后邊的元素

for(varj=i+1;j＜len;j++){

if(arr[p]＞arr[j]){

//arr[p]是當前已知的最小值

p=j;

//比較發(fā)現(xiàn)更小的值時,就記錄下最小值的位置

}

}

//如果發(fā)現(xiàn)最小值的位置與當前假設(shè)的位置i不同,則位置互換

if(p!=i){

tmp=arr[p];

arr[p]=arr[i];

arr[i]=tmp;

}

}

returnarr;

}[考點]排序算法

19.

請用JavaScript實現(xiàn)堆排序。正確答案：堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，其每個結(jié)點都有一個值，通常提到的堆都是指一棵完全二叉樹，其根結(jié)點的值小于(或大于)兩個子結(jié)點的值，同時，根結(jié)點的兩棵子樹也分別是一個堆。

堆排序是一種樹形選擇排序，在排序過程中，將R[1，…，n]看成一棵完全二叉樹順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選擇最小的元素。

堆一般分為大頂堆和小頂堆兩種不同的類型。對于給定n個記錄的序列(r1)，r(2)，…，r(n))，當且僅當滿足條件(r(i)≥r(2i)&&r(i)≥r(2i+1)，i=1，2，…，n)時稱之為大項堆，此時，堆頂元素必為最大值。對于給定n個記錄的序列(r(1)，r(2)，…，r(n))，當且僅當滿足條件(r(i)≤r(2i)&&r(i)≤r(2i+1)，i=1，2，…，n)時稱之為小頂堆，此時，堆頂元素必為最小值。

堆排序的思想是對于給定的n個記錄，初始時把這些記錄看作一棵順序存儲的二叉樹，然后將其調(diào)整為一個大頂堆，再將堆的最后一個元素與堆頂元素(即二叉樹的根結(jié)點)進行交換后，堆的最后一個元素即為最大記錄；接著將前(n-1)個元素(即不包括最大記錄)重新調(diào)整為一個大頂堆，再將堆頂元素與當前堆的最后一個元素進行交換后得到次大的記錄，重復該過程直到調(diào)整的堆中只剩一個元素時為止，該元素即為最小記錄，此時可得到一個有序序列。

堆排序主要包括兩個過程：一是構(gòu)建堆；二是交換堆頂元素與最后一個元素的位置。算法原理如下：

(1)將初始待排序關(guān)鍵字序列(R1，R2，…，Rn)構(gòu)建成大頂堆，此堆為初始的無序區(qū)。

(2)將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(qū)(R1，R2，…，Rn-1)和新的有序區(qū)(Rn)，且滿足R[1，2，…，n-1]≤R[n]。

(3)由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要將當前無序區(qū)(R1，R2，…，Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個元素交換，得到新的無序區(qū)(R1，R2，…，Rn-2)和新的有序區(qū)(Rn-1，Rn)。不斷重復此過程直到有序區(qū)的元素個數(shù)為(n-1)，則整個排序過程完成。

根據(jù)以上的實現(xiàn)原理，具體的實現(xiàn)代碼如下所示。

functionheapSort(arr){

varheapSize=arr.length,

temp;