摘要:優化當待排序序列長度時,使用插入排序,可以加速排序。插入排序原理通過構建有序序列,對于未排序元素,在已排序序列中從后向前掃描,找到相應位置并插入。堆排序可通過樹形結構保存部分比較結果,可減少比較次數。
前端學習:教程&開發模塊化/規范化/工程化/優化&工具/調試&值得關注的博客/Git&面試-前端資源匯總
歡迎提issues斧正:排序算法
JavaScript-排序算法及簡易優化 快速排序原理:在待排序序列中選一個分割元素,將待排序序列分隔成獨立的子序列,子序列1里的元素比分割元素元素都小(大),子序列2反之,遞歸進行此操作,以達到子序列都有序。最后將子序列用concat方法連接起來即是排序好的序列。
function quickSort(arr){ if(arr.length <= 1){ return arr; } var num = Math.floor(arr.length/2); var numValue = arr.splice(num,1); var left = []; var right = []; for(var i = 0;i優化:當待排序序列長度N < 10時,使用插入排序,可以加速排序。
function quickSort(arr){ if(arr.length <= 1){ return arr; } if(arr.length < 10){ insertSort(arr); } var num = Math.floor(arr.length/2); var numValue = arr.splice(num,1); var left = []; var right = []; for(var i = 0;i插入排序 原理:通過構建有序序列,對于未排序元素,在已排序序列中從后向前掃描,找到相應位置并插入。一般可以將第一個元素作為有序序列,用未排序的元素與之相比,插入,直到排序完畢。
function insertSort(arr){ var len = arr.length; if(len <= 1){ return arr; } for(var i = 1;itmp){ arr[j] = arr[j-1]; --j; } arr[j] = tmp; } return arr; } console.log(insertSort([1,45,43,4,56,7,20,1])); //[1, 1, 4, 7, 20, 43, 45, 56] 優化:二分插入排序,在有序序列中使用二分查找法查找一個插入位置,減少元素比較次數
function binaryInsertSort(arr){ var len = arr.length; if(len <= 1){ return arr; } for (var i = 1; i < len; i++) { var tmp = arr[i], left = 0, right = i - 1; while (left <= right) { var index = parseInt((left + right) / 2); if (tmp < arr[index]) { right = index - 1; } else { left = index + 1; } } for (var j = i - 1; j >= left; j--) { arr[j + 1] = arr[j]; } arr[left] = tmp; } return arr; } console.log(binaryInsertSort([1,45,43,4,56,7,20,1,2,3,4,56,3])); //[1, 1, 2, 3, 3, 4, 4, 7, 20, 43, 45, 56, 56]選擇排序原理:在待排序序列中找到最?。ù螅┰?,放在序列的起始位置,然后,再從剩余元素中尋找最?。ù螅┰?,然后放到已排序序列的末尾。重復,直到所有元素均排序完畢。
Array.prototype.selectionSort = Array.prototype.selectionSort || function(){ var len = this.length; if(len <= 1){ return this; } var min,tmp; for(var i = 0;i優化:堆排序,在直接選擇排序中,為了從序列中選出關鍵字最?。ㄗ畲螅┑挠涗?,必須進行n-1次比較,接著在剩下序列中選出最?。ㄗ畲螅┑脑兀中枰鰊-2次比較。但是,在n-2次比較中,有的比較可能在前面的n-1次比較中已經做過,但由于前一趟排序時未保留這些比較結果,所以后一趟排序時又重復執行了這些比較操作。堆積是一個近似完全二叉樹的結構,并同時滿足堆積的性質:即子結點的鍵值或索引總是小于(或者大于)它的父節點。堆排序可通過樹形結構保存部分比較結果,可減少比較次數。
function heapSort(arr) { function swap(arr, i, j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } function maxHeapify(arr, index, heapSize) { var iMax,iLeft,iRight; while (true) { iMax = index; iLeft = 2 * index + 1; iRight = 2 * (index + 1); if (iLeft < heapSize && arr[index] < arr[iLeft]) { iMax = iLeft; } if (iRight < heapSize && arr[iMax] < arr[iRight]) { iMax = iRight; } if (iMax != index) { swap(arr, iMax, index); index = iMax; } else { break; } } } function buildMaxHeap(arr) { var i,iParent = Math.floor(arr.length / 2) - 1; for (i = iParent; i >= 0; i--) { maxHeapify(arr, i, arr.length); } } function sort(arr) { buildMaxHeap(arr); for (var i = arr.length - 1; i > 0; i--) { swap(arr, 0, i); maxHeapify(arr, 0, i); } return arr; } return sort(arr); } console.log(heapSort([1,45,43,4,56,7,20,1,2,3,4,56,3])); //[1, 1, 2, 3, 3, 4, 4, 7, 20, 43, 45, 56, 56]冒泡排序原理:從第一個元素開始,一次比較兩個元素,如果arr[n]大于arr[n+1],就交換。重復遍歷直到沒有再需要交換,排序完成。
function bubbleSort(arr){ var len = arr.length; if(len <= 1){ return arr; } var tmp; for(var i = 0;i優化:上面代碼中,里面一層循環在某次掃描中沒有發生交換,說明此時數組已經全部排好序,后面的步驟就無需再執行了。因此,增加一個標記,每次發生交換,就標記,如果某次循環完沒有標記,則說明已經完成排序。
function bubbleSort(arr) { var len = arr.length; if(len <= 1){ return arr; } var bSwaped = true; for (var i = 0; i < len -1; i++) { // 每次先重置為false bSwaped = false; for (var j = len - 1; j > i ; j--) { if (arr[j-1] > arr[j]) { var temp = arr[j-1]; arr[j-1] = arr[j]; arr[j] = temp; bSwaped = true; } } // 如果上一次掃描沒有發生交換,則說明數組已經全部有序,退出循環 if (!bSwaped){ break; } } return arr; } console.log(bubbleSort([1,45,43,4,56,7,20,1])); //[1, 1, 4, 7, 20, 43, 45, 56]在上一步優化的基礎上進一步思考:如果R[0..i]已是有序區間,上次的掃描區間是R[i..n],記上次掃描時最后一次發生交換的位置是lastSwapPos,那么lastSwapPos會在在i與n之間,所以R[i..lastSwapPos]區間是有序的,否則這個區間也會發生交換;所以下次掃描區間就可以由R[i..n]縮減到[lastSwapPos..n] :
function bubbleSort(arr){ var len = arr.length; if(len <= 1){ return arr; } var lastSwapPos = 0, lastSwapPosTemp = 0; for (var i = 0; i < len - 1; i++){ lastSwapPos = lastSwapPosTemp; for (var j = len - 1; j > lastSwapPos; j--){ if (arr[j - 1] > arr[j]){ var temp = arr[j - 1]; arr[j - 1] = arr[j]; arr[j] = temp; lastSwapPosTemp = j; } } if (lastSwapPos == lastSwapPosTemp){ break; } } return arr; } console.log(bubbleSort([1,45,43,4,56,7,20,1])); //[1, 1, 4, 7, 20, 43, 45, 56]這一些列優化都需要測速才知道有沒有優化成功,只是簡單的測試一兩個數組是不容易看出來的。我們可以造一些很大的數據去測試,再用一個比較簡單的測試時間的方法,隨機創建10萬個數:
var arr = []; var num = 0; for(var i = 0; i < 100000; i++){ num = Math.floor(Math.random()*100000); arr.push(num); } console.time("testTime"); bubbleSort(arr); console.timeEnd("testTime"); ==> testTime: 21900.684ms (比較數目越多,差距越大,更好對比)
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/79911.html
摘要:在上面的三種排序中,它們的效率為用大表示法來表示都是,但實際上按比較的次數和交換的次數來考慮,插入排序效率高于選擇排序,選擇排序效率高于冒泡排序。大表示法常見的基于的走勢圖如下圖所示 大O表示法初體驗 身在斯洛文尼亞的阿拉里克得到斯提里科被殺的消息后,仰天大笑:終于沒有人能阻止我去羅馬了。當他手下的將軍問:不知大王打算走哪條路去羅馬?西哥特王哈哈大笑,說出了那句千古名言:All roa...
摘要:創建數組數組字面量數組構造函數參數為數組建議使用數組字面量方式,性能好,代碼少,簡潔,畢竟代碼少。數組判斷方法用來判斷某個值是否為。的這是最簡潔最直接的遍歷數組元素的語法。把數組轉換為本地數組,并返回結果。 前端學習:前端教程&開發模塊化/規范化/工程化/優化&工具/調試&值得關注的博客/Git&面試-前端資源匯總 歡迎提issues斧正:數組&數組方法使用詳解 Array對象 之前一...
摘要:今天同學去面試,做了兩道面試題全部做錯了,發過來給道典型的面試題前端掘金在界中,開發人員的需求量一直居高不下。 排序算法 -- JavaScript 標準參考教程(alpha) - 前端 - 掘金來自《JavaScript 標準參考教程(alpha)》,by 阮一峰 目錄 冒泡排序 簡介 算法實現 選擇排序 簡介 算法實現 ... 圖例詳解那道 setTimeout 與循環閉包的經典面...
摘要:特意對前端學習資源做一個匯總,方便自己學習查閱參考,和好友們共同進步。 特意對前端學習資源做一個匯總,方便自己學習查閱參考,和好友們共同進步。 本以為自己收藏的站點多,可以很快搞定,沒想到一入匯總深似海。還有很多不足&遺漏的地方,歡迎補充。有錯誤的地方,還請斧正... 托管: welcome to git,歡迎交流,感謝star 有好友反應和斧正,會及時更新,平時業務工作時也會不定期更...
Llama3-8B-Chinese-Chat 是基于 Meta-Llama-3-8B-Instruct 模型通過 ORPO進行微調的中文聊天模型。與原始的 Meta-Llama-3-8B-Instruct 模型相比,此模型顯著減少了中文問題英文回答"和混合中英文回答的問題。此外,相較于原模型,新模型在回答中大量減少了表情符號的使用,使得回應更加正式。與 Llama-3-8B-nsturc...
閱讀 1980·2021-09-26 10:19
閱讀 3249·2021-09-24 10:25
閱讀 1623·2019-12-27 11:39
閱讀 1919·2019-08-30 15:43
閱讀 663·2019-08-29 16:08
閱讀 3504·2019-08-29 16:07
閱讀 902·2019-08-26 11:30
閱讀 1270·2019-08-26 10:41