資訊專欄INFORMATION COLUMN
摘要：最近看了一道如何給阿里兩萬多名員工按照年齡排序的面試題后，很想記錄下來自己的解題思路，下面綜合考慮到基數(shù)較大和穩(wěn)定性，我們采取歸并排序的算法歸并算法分為兩個(gè)兩個(gè)靈魂步驟，即拆分歸并我們先把兩萬多名員工的基數(shù)縮小至六名員工的基數(shù)，他們的年齡數(shù)
最近看了一道“如何給阿里兩萬多名員工按照年齡排序”的面試題后，很想記錄下來自己的解題思路，下面：
綜合考慮到基數(shù)較大和穩(wěn)定性，我們采取歸并排序的算法；
歸并算法分為兩個(gè)兩個(gè)靈魂步驟，即：拆分=>歸并；
我們先把兩萬多名員工的基數(shù)縮小至六名員工的基數(shù)，他們的年齡數(shù)組未排序前為[25,18,17,31,25,30],我們實(shí)現(xiàn)第一個(gè)靈魂操作，拆分:
歸并算法的拆分思想是將一個(gè)數(shù)組一分為二，然后將分出來的數(shù)組繼續(xù)一分為二，直至出現(xiàn)單個(gè)數(shù)組的長度為1，不可再分為止；
如上圖，一個(gè)長度為6的數(shù)組按照左右結(jié)構(gòu)一直拆分至6個(gè)長度為1的數(shù)組，拆分就完畢了，這時(shí)我們由下往上回溯，將數(shù)組歸并，圖解：
六個(gè)長度為一的數(shù)組歸并之后又變成了一個(gè)長度為6的數(shù)組，但是排序發(fā)生了改變，這就是歸并算法，下面是代碼實(shí)現(xiàn)：
我們一步一步來，第一步先來實(shí)現(xiàn)拆分的部分：
// 拆分
function mergeSort(arr){
console.log(`arr=${arr}`)
if(arr.length==1){//如果數(shù)組長度為1則返回?cái)?shù)組
return arr
}
var mid=Math.floor(arr.length/2);//將數(shù)組一拆分為二
var left=arr.slice(0,mid);
var right=arr.slice(mid);
mergeSort(left);//如果數(shù)組長度不為1，則繼續(xù)遞歸拆分，（由控制臺(tái)可以看出遞歸會(huì)先將left執(zhí)行完后再去執(zhí)行right）
mergeSort(right)
}
console.log(mergeSort([25,18,17,31,25,30]))
控制臺(tái)打印出結(jié)果：
這個(gè)時(shí)候我們可以看到，我們已經(jīng)采用遞歸的方式將數(shù)組拆分為六個(gè)長度為一的數(shù)組了，接下來走第二步的合并，合并的思想是左右兩個(gè)數(shù)組的第一個(gè)元素比較大小，然后將大的數(shù)（或者小的數(shù)）提取出來存放在一個(gè)第三方數(shù)組，直接上代碼：
// 合并
function merge(left,right){
var arr=new Array;//新建一個(gè)第三方數(shù)組
if(left[0]<=right[0]){//比較left的第一位和right的第一位誰小，小的提取出來push進(jìn)第三方數(shù)組
arr.push(left.shift())
}else{
arr.push(right.shift())
}
return arr.concat(left).concat(right)//將提取出來的數(shù)組和原數(shù)組歸并成一個(gè)數(shù)組
};
console.log(merge([25],[30]))//代碼到這一步只是展示了合并的原理和思路，并不完整，我們不急，先用簡(jiǎn)單的單元素?cái)?shù)組進(jìn)行排序合并，這也是合并的第一層合并
控制臺(tái)打印出[25,30],說明我們的歸并和排序都是成功的，下面我們將升級(jí)兩個(gè)函數(shù)，使其能夠正式地操作復(fù)雜的歸并排序：
// 合并
function merge(left,right){
var arr=new Array;//新建一個(gè)第三方數(shù)組
while(left.length>0&&right.length>0){////比較left的第一位和right的第一位誰小，小的提取出來push進(jìn)第三方數(shù)組
if(left[0]<=right[0]){
arr.push(left.shift())
}else{
arr.push(right.shift())
}
};
return arr.concat(left).concat(right)//將提取出來的數(shù)組和原數(shù)組歸并成一個(gè)數(shù)組
};
// 拆分
function mergeSort(arr){
console.log(`arr=${arr}`)
if(arr.length==1){//如果數(shù)組長度為1則返回?cái)?shù)組
return arr
};
var mid=Math.floor(arr.length/2);//將數(shù)組一拆分為二
var left=arr.slice(0,mid);
var right=arr.slice(mid);
return merge(mergeSort(left),mergeSort(right))
};
console.log(mergeSort([25,18,17,31,25,30]))
控住臺(tái)打印：
至此，我們的歸并排序成功！
歡迎各位大小神同行予以指正和探討
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/104068.html
摘要：下面會(huì)介紹的一種排序算法快速排序甚至被譽(yù)為世紀(jì)科學(xué)和工程領(lǐng)域的十大算法之一。我們將討論比較排序算法的理論基礎(chǔ)并中借若干排序算法和優(yōu)先隊(duì)列的應(yīng)用。為了展示初級(jí)排序算法性質(zhì)的價(jià)值，我們來看一下基于插入排序的快速的排序算法希爾排序。 前言 排序就是將一組對(duì)象按照某種邏輯順序重新排列的過程。比如信用卡賬單中的交易是按照日期排序的——這種排序很可能使用了某種排序算法。在計(jì)算時(shí)代早期，大家普遍...
摘要：棧被稱為一種后入先出的數(shù)據(jù)結(jié)構(gòu)。散列使用的數(shù)據(jù)結(jié)構(gòu)叫做散列表。這些操作需要求助于其他數(shù)據(jù)結(jié)構(gòu)，比如下面介紹的二叉查找樹。 前言 在過去的幾年中，得益于Node.js的興起，JavaScript越來越廣泛地用于服務(wù)器端編程。鑒于JavaScript語言已經(jīng)走出了瀏覽器，程序員發(fā)現(xiàn)他們需要更多傳統(tǒng)語言（比如C++和Java）提供的工具。這些工具包括傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)（如鏈表，棧，隊(duì)列，圖等），...
摘要：本篇主要實(shí)現(xiàn)九八大排序算法，分別是冒泡排序，插入排序，選擇排序，希爾排序，歸并排序，快速排序，堆排序計(jì)數(shù)排序。希爾排序是非穩(wěn)定排序算法。歸并排序算法依賴歸并操作。但是，計(jì)數(shù)排序可以用在基數(shù)排序算法中，能夠更有效的排序數(shù)據(jù)范圍很大的數(shù)組。 本篇主要實(shí)現(xiàn)九(八）大排序算法，分別是冒泡排序，插入排序，選擇排序，希爾排序，歸并排序，快速排序，堆排序,計(jì)數(shù)排序。希望大家回顧知識(shí)的時(shí)候也能從我的這...
摘要：歸并排序就這么簡(jiǎn)單從前面已經(jīng)講解了冒泡排序選擇排序插入排序快速排序了，本章主要講解的是歸并排序，希望大家看完能夠理解并手寫出歸并排序快速排序的代碼，然后就通過面試了如果我寫得有錯(cuò)誤的地方也請(qǐng)大家在評(píng)論下指出。 歸并排序就這么簡(jiǎn)單 從前面已經(jīng)講解了冒泡排序、選擇排序、插入排序,快速排序了，本章主要講解的是歸并排序，希望大家看完能夠理解并手寫出歸并排序快速排序的代碼，然后就通過面試了！如果...
閱讀 789·2021-11-09 09:47
閱讀 1581·2019-08-30 15:44
閱讀 1149·2019-08-26 13:46
閱讀 2114·2019-08-26 13:41
閱讀 1279·2019-08-26 13:32
閱讀 3783·2019-08-26 10:35
閱讀 3532·2019-08-23 17:16
閱讀 462·2019-08-23 17:07
