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