摘要:排序算法學習筆記用于創建數組冒泡排序冒泡排序比較任何兩個相鄰的項,如果第一個比第二個大,則交換它們。歸并排序歸并排序是一種分治算法。完成下列操作的前提是數組均已經完成。
javaScript排序算法學習筆記
// 用于創建數組 function createNonSortedArray(size) { var array = new ArrayList(); for( var i = size; i>0; i--) { array.insert(i); } return array; } function ArrayList() { var array = []; this.insert = function(item) { console.log(item, "insert"); array.push(item); } this.toString = function() { console.log("tostring"); return array.join(); } /* * 冒泡排序 * 冒泡排序比較任何兩個相鄰的項,如果第一個比第二個大,則交換它們。 * 元素項向上移動至正確的順序,就好像氣泡升至表面一樣,冒泡排序因此得名。 * 第一輪比過之后最后一個就一定是最大的 無需再比較。所以下次要 - i */ this.bubbleSort = function() { var length = array.length; for(var i = 0;iarray[j + 1]) { swap(array, j, j+1); } } } } /* * 選擇排序 * 選擇排序算法是一種原址比較排序算法。選擇排序大致的思路是找到數據結構中的最小值 * 并將其放置在第一位,接著找到第二小的值并將其放在第二位,以此類推。比如,第一個 * 的時候,會遍歷后面所有想跟其比較,找到最小的更其交換。所以第一個此時一定是最小的。 * 隨意第二個的時候,只會循環后面的幾個。如果找到一個比第二個更小的,那么交換位置。 */ this.selectionSort = function() { var length = array.length, indexMin; for(var i = 0;i< length - 1;i++) { indexMin = i; for(var j = i;j array[j]) { indexMin = j; } } if (i !== indexMin) { swap(array, i, indexMin); } } } /* * 插入排序 * 插入排序每次排第一個數組項,以此方式構建最后的排序數組。假定第一項已經排序了,接著, * 它和第二項進行比較,第二項是應該待在原位還是插到第一項之前呢?這樣,頭兩項就已正確 * 排序,接著和第三項比較(它是該插入到第一、第二還是第三位置呢?),以此類推。 * 簡而言之,就是遍歷數組的每一項,拿這一項去跟前面的項比較,如果比他小就插入到它前面。 */ this.insertionSort = function() { var length = array.length, j,temp; for (var i = 1;i 0 && array[j-1] > temp) { array[j] = array[j - 1]; j--; } array[j] = temp; } } // 歸并排序 // 歸并排序是一種分治算法。其思想是將原始數組切分成較小的數組,直到每個 // 小數組只有一個位置,接著將小數組歸并成較大的數組,直到最后一個排序完畢的大數組。 this.mergeSort = function() { array = mergeSortRec(array); } var mergeSortRec = function(array) { var length = array.length; if (length === 1) { return array; } var mid = Math.floor(length / 2), left = array.slice(0, mid), right = array.slice(mid, length); return merge(mergeSortRec(left), mergeSortRec(right)); } var merge = function(left, right) { var result = [], il = 0, ir = 0; // 完成下列操作的前提是left、right數組均已經完成。所以采用遞歸的形式 // 在數組長度為1的時候先開始排序,然后在通過merge left與right數組 while(il < left.length && ir < right.length) { if (left[il] < right[ir]) { result.push(left[il++]); } else { result.push(right[ir++]); } } // 上面是將left與right數組排完序,那么其中之一數組必然為空, // 下面的操作就是將剩下的right或者left全部推入result數組中 while(il < left.length) { result.push(left[il++]); } while(ir < right.length) { result.push(right[ir++]); } return result; } // 快速排序 // 首先,從數組中選擇中間一項作為主元 // 創建兩個指針,左邊一個指向數組的第一項,右邊一個指向數組的最后一個項。 // 移動左指針直到我們找到一個比主元大的元素,接著,移動右指針直到找到一個 // 比主元小的元素,然后交換他們,重復這個過程,直到左指針超過右指針。這個 // 過程將使得比主元小的值都排在主元之前,而比主元大的值都排在主元之后。這一步 // 叫做劃分操作。 // 接著,算法對劃分后的小數組(較主元小的值組成的子數組,以及較主元大的值 // 組成的子數組)重復之前的兩個步驟,直到數組已完全排序。 // 簡而言之,先分治,不斷的細化下去,到最后一個數組無法再交換位置進行排序位置 this.quickSort = function() { quick(array, 0, array.length - 1); } var quick = function(array, left, right) { var index; if (array.length > 1) { index = partition(array, left, right); if (left < index - 1 ) { quick(array, left, index - 1); } if (index < right) { quick(array, index, right); } } } var partition = function(array, left, right) { var pivot = array[Math.floor((left + right) / 2)], i = left, j = right; while(i <= j) { while(array[i] < pivot) { i++; } while(array[j] > pivot) { j--; } if (i <= j) { swap(array, i, j); i++; j--; } } return i; } var swap = function(array, index1, index2) { var aux = array[index1]; array[index1] = array[index2]; array[index2] = aux; } } var array = createNonSortedArray(9); console.log(array.toString()); array.bubbleSort(); // array.selectionSort(); // array.insertionSort(); // array.mergeSort(); // array.quickSort(); console.log(array.toString());
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/109127.html
摘要:強烈推薦上值得前端學習的數據結構與算法項目,包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數據結構,提供進一步閱讀的解釋和鏈接。數據結構和算法必知必會的個代碼實現。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法為王。想學好前端,先練好內功,內功不行,就算招式練的再花哨,終究成不了高手;只有內功深厚者,前端之路才會走得...
摘要:本文記錄了我在學習前端上的筆記,方便以后的復習和鞏固。冒泡排序算法步驟比較相鄰的元素。這步做完后,最后的元素會是最大的數。重復第二步,直到所有元素均排序完畢。得到序列第二趟,,和進行交換。 本文記錄了我在學習前端上的筆記,方便以后的復習和鞏固。推薦大家去看看這一本gitBook上的書十大經典排序算法本文就是看這本書記錄的筆記。 冒泡排序 1.算法步驟 1.比較相鄰的元素。如果第一個比第...
摘要:排序算法主要針對的是數組,所以,在開始學習之前,我們先自己新建一種數據結構來方便我們的學習。統計執行次數冒泡排序比較相鄰兩個數的大小,如果前面的數大于后面,則交換這兩個數的位置。所以我們把數列分割成不超過兩個元素的數組,然后將其合并。 ??排序算法主要針對的是數組,所以,在開始學習之前,我們先自己新建一種數據結構來方便我們的學習。 function ArrayData () { l...
閱讀 782·2023-04-25 17:33
閱讀 3632·2021-07-29 14:49
閱讀 2485·2019-08-30 15:53
閱讀 3439·2019-08-29 16:27
閱讀 2004·2019-08-29 16:11
閱讀 1035·2019-08-29 14:17
閱讀 2439·2019-08-29 13:47
閱讀 2022·2019-08-29 13:28