摘要:假設要對數組進行歸并排序,步驟是先將劃分為兩個數組和即把數組從中間分開再分別對數組重復步驟的操作,逐步劃分,直到不能再劃分為止每個子數組只剩下一個元素,這樣,劃分的過程就結束了。
插入排序
算法描述:
從第一個元素開始,該元素可以認為已經被排序
取出下一個元素,在已經排序的元素序列中從后向前掃描
如果該元素(已排序)大于新元素,將該元素移到下一位置
重復步驟 3,直到找到已排序的元素小于或者等于新元素的位置
將新元素插入到該位置后
重復步驟 2~5
var arr = [5, 6, 3, 1, 8, 7, 2, 4]; for(let i = 1;i= 0 ; j -- ){ console.log("單次比較數據:"+arr[myIndex]+"---"+arr[j]) if(arr[myIndex] < arr[j]){ [arr[myIndex],arr[j]] = [arr[j],arr[myIndex]]; myIndex = j; }else{ break; } console.log("數組"+arr); } }
時間復雜度 O(n^2)
運行過程
算法描述
直接從待排序數組中選擇一個最小(或最大)數字,放入新數組中。
假定第一個數字是最小的,然后依次和后面的比較,哪個小哪個就記錄當前那個的下標。
記錄完下標了之后替換第一個和那個最小數字的位置
依次執行上述步驟,只不過最小的位置依次累加
var arr = [5, 6, 3, 1, 8, 7, 2, 4]; for(let i = 0; i < arr.length - 1;i++){ console.log("次數"+Number(i+1)) let minIndex = i; for(let j = i ;j < arr.length - 1; j++){ console.log("單次比較數據:"+arr[minIndex]+"---"+arr[j+1]) if(arr[minIndex] > arr[j+1]){ minIndex = j+1; } } [arr[minIndex],arr[i]] = [arr[i],arr[minIndex]]; console.log("數組"+arr); }
時間復雜度 O(n^2)
運行過程
就幾種算法來看,感覺冒泡是比較慢的
算法描述:
比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。
對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最后一對。在這一點,最后的元素應該會是最大的數。
針對所有的元素重復以上的步驟,除了最后一個。
持續每次對越來越少的元素重復上面的步驟,直到沒有任何一對數字需要比較。
var arr = [5, 6, 3, 1, 8, 7, 2, 4]; let count = 0; for(let i = arr.length ; i > 0; i --){ console.log("次數"+i); for(let j = 1; j < i; j ++){ console.log("單次比較數據:"+arr[j]+"----"+arr[j-1]) if(arr[j] < arr[j-1]){ [arr[j],arr[j-1]] = [arr[j-1],arr[j]] } } console.log(arr); }
時間復雜度 O(n^2)
運行過程
歸并排序的圖可能一下看不懂,是因為圖代表的是運行的過程,主要看算法描述
歸并排序:其基本思想是分治策略,先進行劃分,然后再進行合并。
假設要對數組C進行歸并排序,步驟是:
1.先將C劃分為兩個數組A和B(即把數組C從中間分開)
2.再分別對數組A、B重復步驟1的操作,逐步劃分,直到不能再劃分為止(每個子數組只剩下一個元素),這樣,劃分的過程就結束了。
如: [12 20 30 21 15 33 26 19 40 25]
劃分為: [12 20 30 21 15] [33 26 19 40 25]
[12 20] [30 21 15] [33 26] [19 40 25] [12] [20] [30] [21 15] [33] [26] [19] [40 25] [12] [20] [30] [21] [15] [33] [26] [19] [40] [25]
3.然后從下層往上層不斷合并數組,每一層合并相鄰的兩個子數組,合并的過程是每次從待合并的兩個子數組中選取一個最小的元素,然后把這個元素放到合并后的數組中,不斷重復直到把兩個子數組的元素都放到合并后的數組為止。
4.依次類推,直到合并到最上層結束,這時數據的排序已經完成了。
var arr = [5, 6, 3, 1, 8, 7, 2, 4,9]; function mergeSort(arr){ if(arr.length === 1){ return arr; } let midIndex = Math.floor(arr.length / 2); let leftArr = arr.slice(0,midIndex); let rightArr = arr.slice(midIndex); console.log("拆分數組"+leftArr+"------"+rightArr) return mergeFn(mergeSort(leftArr),mergeSort(rightArr)); }. function mergeFn(left,right){ let tmp = []; console.log(left + "----" + right); while (left.length && right.length) { console.log("單次比較數據:"+left[0]+"和"+right[0]+"誰小誰所在的數組就被shift掉一個") if (left[0] < right[0]){ tmp.push(left.shift()); } else{ tmp.push(right.shift()); } console.log(tmp); } let arra = tmp.concat(left, right); console.log("本次比較完畢:"+arra); return arra; } mergeSort(arr);
時間復雜度 O(nlogn)
運行過程,看了運行過程就能看懂圖了,也知道js函數里的參數有函數的情況下的執行順序是自左向右
圖上的運行方式是按照基準是第0號位算的,看起來稍微有點亂,不過只要知道快排是怎么算的就好了
算法描述:
在數據集之中,選擇一個元素作為”基準”(pivot)。
所有小于”基準”的元素,都移到”基準”的左邊;所有大于”基準”的元素,都移到”基準”的右邊。這個操作稱為分區 (partition)操作,分區操作結束后,基準元素所處的位置就是最終排序后它的位置。
對”基準”左邊和右邊的兩個子集,不斷重復第一步和第二步,直到所有子集只剩下一個元素為止。
var arr = [5, 6, 3, 1, 8, 7, 2, 4]; function quickSort(arr){ if(arr.length <= 1){ return arr; } //找基準 let midIndex = Math.floor(arr.length/2); //剔除基準值 let midNum = arr.splice(midIndex,1)[0]; console.log("基準值:"+midNum); let leftArr = [],rightArr=[]; for(let i = 0 ; i < arr.length; i++){ //小于基準的進左邊,大于的進右邊 arr[i] < midNum ? leftArr.push(arr[i]) : rightArr.push(arr[i]) } console.log("小于基準值的數組:"+leftArr); console.log("大于基準值的數組:"+rightArr); return quickSort(leftArr).concat(midNum,quickSort(rightArr)); } quickSort(arr);
時間復雜度 O(nlogn)
運行過程
這個運行過程是按照基準為0號位算的;
可以看到,快速排序和歸并排序是比較快。而且快排更容易理解更好寫一些。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/94704.html
摘要:算法之最常用的排序參加百度前端的課程真的是好多知識點不知道。快速排序也是在實際中最常用的一種排序算法,速度快,效率高。插入排序的思路很簡單,很清晰,是一種最常見最簡單的排序方法。 js算法之最常用的排序 參加百度前端的課程真的是好多知識點不知道。邊學邊做題,在問題中學習,知識點從點到面,但是要善于總結記錄才行。加油吧,騷年! 可視化排序網站 時間復雜度是衡量一個算法效率的基本方法我們把...
摘要:冒泡排序每次對比相鄰兩個數據的大小升序小的拍前面,若前一個數比后一個數大,則交換兩數位置。 冒泡排序:每次對比相鄰兩個數據的大小,升序小的拍前面,若前一個數比后一個數大,則交換兩數位置。需要兩次for循環遍歷. 優點:簡單 缺點:時間復雜度高,運行效率低下 function sortArr(arr){ var temp; for(var i=0;i
摘要:上一篇數據結構與算法樹寫在前面這是學習數據結構與算法的最后一篇博客,也是在面試中常常會被問到的一部分內容排序和搜索。 上一篇:JS數據結構與算法_樹 寫在前面 這是《學習JavaScript數據結構與算法》的最后一篇博客,也是在面試中常常會被問到的一部分內容:排序和搜索。在這篇博客之前,我每每看到排序頭就是大的,心里想著類似冒泡排序,兩層遍歷啪啪啪就完事了,然后再也無心去深入研究排序相...
摘要:今天同學去面試,做了兩道面試題全部做錯了,發過來給道典型的面試題前端掘金在界中,開發人員的需求量一直居高不下。 排序算法 -- JavaScript 標準參考教程(alpha) - 前端 - 掘金來自《JavaScript 標準參考教程(alpha)》,by 阮一峰 目錄 冒泡排序 簡介 算法實現 選擇排序 簡介 算法實現 ... 圖例詳解那道 setTimeout 與循環閉包的經典面...
閱讀 798·2021-09-06 15:02
閱讀 2439·2019-08-30 15:43
閱讀 2164·2019-08-30 11:26
閱讀 2372·2019-08-26 12:12
閱讀 3538·2019-08-23 18:24
閱讀 3254·2019-08-23 18:16
閱讀 695·2019-08-23 17:02
閱讀 2241·2019-08-23 15:34