您好,登錄后才能下訂單哦!
這篇文章主要講解了“JavaScript十大排序的算法是什么”,文中的講解內(nèi)容簡(jiǎn)單清晰,易于學(xué)習(xí)與理解,下面請(qǐng)大家跟著小編的思路慢慢深入,一起來(lái)研究和學(xué)習(xí)“JavaScript十大排序的算法是什么”吧!
冒泡排序
通過(guò)相鄰元素的比較和交換,使得每一趟循環(huán)都能找到未有序數(shù)組的最大值或最小值。
最好:O(n),只需要冒泡一次數(shù)組就有序了。
最壞:O(n2)
平均:O(n2)
單向冒泡
1. function bubbleSort(nums) { 2. for(let i=0, len=nums.length; i<len-1; i++) { 3. // 如果一輪比較中沒(méi)有需要交換的數(shù)據(jù),則說(shuō)明數(shù)組已經(jīng)有序。主要是對(duì)[5,1,2,3,4]之類的數(shù)組進(jìn)行優(yōu)化 4. let mark = true; 5. for(let j=0; j<len-i-1; j++) { 6. if(nums[j] > nums[j+1]) { 7. [nums[j], nums[j+1]] = [nums[j+1], nums[j]]; 8. mark = false; 9. } 10. } 11. if(mark) return; 12. } 13. }
一個(gè)人學(xué)習(xí)會(huì)有迷茫,動(dòng)力不足。這里推薦一下我的前端學(xué)習(xí)交流群:731771211 ,里面都是學(xué)習(xí)前端的,如果你想制作酷炫的網(wǎng)頁(yè),想學(xué)習(xí)編程。自己整理了一份2019最全面前端學(xué)習(xí)資料,從最基礎(chǔ)的HTML+CSS+JS【炫酷特效,游戲,插件封裝,設(shè)計(jì)模式】到移動(dòng)端HTML5的項(xiàng)目實(shí)戰(zhàn)的學(xué)習(xí)資料都有整理,送給每一位前端小伙伴,有想學(xué)習(xí)web前端的,或是轉(zhuǎn)行,或是大學(xué)生,還有工作中想提升自己能力的,正在學(xué)習(xí)的小伙伴歡迎加入學(xué)習(xí)。
雙向冒泡
普通的冒泡排序在一趟循環(huán)中只能找出一個(gè)最大值或最小值,雙向冒泡則是多一輪循環(huán)既找出最大值也找出最小值。
1. function bubbleSort_twoWays(nums) { 2. let low = 0; 3. let high = nums.length - 1; 4. while(low < high) { 5. let mark = true; 6. // 找到最大值放到右邊 7. for(let i=low; i<high; i++) { 8. if(nums[i] > nums[i+1]) { 9. [nums[i], nums[i+1]] = [nums[i+1], nums[i]]; 10. mark = false; 11. } 12. } 13. high--; 14. // 找到最小值放到左邊 15. for(let j=high; j>low; j--) { 16. if(nums[j] < nums[j-1]) { 17. [nums[j], nums[j-1]] = [nums[j-1], nums[j]]; 18. mark = false; 19. } 20. } 21. low++; 22. if(mark) return; 23. } 24. }
選擇排序
和冒泡排序相似,區(qū)別在于選擇排序是將每一個(gè)元素和它后面的元素進(jìn)行比較和交換。
最好:O(n2)
最壞:O(n2)
平均:O(n2)
1. function selectSort(nums) { 2. for(let i=0, len=nums.length; i<len; i++) { 3. for(let j=i+1; j<len; j++) { 4. if(nums[i] > nums[j]) { 5. [nums[i], nums[j]] = [nums[j], nums[i]]; 6. } 7. } 8. } 9. }
插入排序
以第一個(gè)元素作為有序數(shù)組,其后的元素通過(guò)在這個(gè)已有序的數(shù)組中找到合適的位置并插入。
最好:O(n),原數(shù)組已經(jīng)是升序的。
最壞:O(n2)
平均:O(n2)
1. function insertSort(nums) { 2. for(let i=1, len=nums.length; i<len; i++) { 3. let temp = nums[i]; 4. let j = i; 5. while(j >= 0 && temp < nums[j-1]) { 6. nums[j] = nums[j-1]; 7. j--; 8. } 9. nums[j] = temp; 10. } 11. }
快速排序
選擇一個(gè)元素作為基數(shù)(通常是第一個(gè)元素),把比基數(shù)小的元素放到它左邊,比基數(shù)大的元素放到它右邊(相當(dāng)于二分),再不斷遞歸基數(shù)左右兩邊的序列。
最好:O(n * logn),所有數(shù)均勻分布在基數(shù)的兩邊,此時(shí)的遞歸就是不斷地二分左右序列。
最壞:O(n2),所有數(shù)都分布在基數(shù)的一邊,此時(shí)劃分左右序列就相當(dāng)于是插入排序。
平均:O(n * logn)
快速排序之填坑
從右邊向中間推進(jìn)的時(shí)候,遇到小于基數(shù)的數(shù)就賦給左邊(一開(kāi)始是基數(shù)的位置),右邊保留原先的值等之后被左邊的值填上。
1. function quickSort(nums) { 2. // 遞歸排序基數(shù)左右兩邊的序列 3. function recursive(arr, left, right) { 4. if(left >= right) return; 5. let index = partition(arr, left, right); 6. recursive(arr, left, index - 1); 7. recursive(arr, index + 1, right); 8. return arr; 9. } 10. // 將小于基數(shù)的數(shù)放到基數(shù)左邊,大于基數(shù)的數(shù)放到基數(shù)右邊,并返回基數(shù)的位置 11. function partition(arr, left, right) { 12. // 取第一個(gè)數(shù)為基數(shù) 13. let temp = arr[left]; 14. while(left < right) { 15. while(left < right && arr[right] >= temp) right--; 16. arr[left] = arr[right]; 17. while(left < right && arr[left] < temp) left++; 18. arr[right] = arr[left]; 19. } 20. // 修改基數(shù)的位置 21. arr[left] = temp; 22. return left; 23. } 24. recursive(nums, 0, nums.length-1); 25. }
快速排序之交換
從左右兩邊向中間推進(jìn)的時(shí)候,遇到不符合的數(shù)就兩邊交換值。
1. function quickSort1(nums) { 2. function recursive(arr, left, right) { 3. if(left >= right) return; 4. let index = partition(arr, left, right); 5. recursive(arr, left, index - 1); 6. recursive(arr, index + 1, right); 7. return arr; 8. } 9. function partition(arr, left, right) { 10. let temp = arr[left]; 11. let p = left + 1; 12. let q = right; 13. while(p <= q) { 14. while(p <= q && arr[p] < temp) p++; 15. while(p <= q && arr[q] > temp) q--; 16. if(p <= q) { 17. [arr[p], arr[q]] = [arr[q], arr[p]]; 18. // 交換值后兩邊各向中間推進(jìn)一位 19. p++; 20. q--; 21. } 22. } 23. // 修改基數(shù)的位置 24. [arr[left], arr[q]] = [arr[q], arr[left]]; 25. return q; 26. } 27. recursive(nums, 0, nums.length-1); 28. }
歸并排序
遞歸將數(shù)組分為兩個(gè)序列,有序合并這兩個(gè)序列。
最好:O(n * logn)
最壞:O(n * logn)
平均:O(n * logn)
1. function mergeSort(nums) { 2. // 有序合并兩個(gè)數(shù)組 3. function merge(l1, r1, l2, r2) { 4. let arr = []; 5. let index = 0; 6. let i = l1, j = l2; 7. while(i <= r1 && j <= r2) { 8. arr[index++] = nums[i] < nums[j] ? nums[i++] : nums[j++]; 9. } 10. while(i <= r1) arr[index++] = nums[i++]; 11. while(j <= r2) arr[index++] = nums[j++]; 12. // 將有序合并后的數(shù)組修改回原數(shù)組 13. for(let t=0; t<index; t++) { 14. nums[l1 + t] = arr[t]; 15. } 16. } 17. // 遞歸將數(shù)組分為兩個(gè)序列 18. function recursive(left, right) { 19. if(left >= right) return; 20. // 比起(left+right)/2,更推薦下面這種寫法,可以避免數(shù)溢出 21. let mid = parseInt((right - left) / 2) + left; 22. recursive(left, mid); 23. recursive(mid+1, right); 24. merge(left, mid, mid+1, right); 25. return nums; 26. } 27. recursive(0, nums.length-1); 28. }
桶排序
取 n 個(gè)桶,根據(jù)數(shù)組的最大值和最小值確認(rèn)每個(gè)桶存放的數(shù)的區(qū)間,將數(shù)組元素插入到相應(yīng)的桶里,最后再合并各個(gè)桶。
最好:O(n),每個(gè)數(shù)都在分布在一個(gè)桶里,這樣就不用將數(shù)插入排序到桶里了(類似于計(jì)數(shù)排序以空間換時(shí)間)。
最壞:O(n2),所有的數(shù)都分布在一個(gè)桶里。
平均:O(n + k),k表示桶的個(gè)數(shù)。
1. function bucketSort(nums) { 2. // 桶的個(gè)數(shù),只要是正數(shù)即可 3. let num = 5; 4. let max = Math.max(...nums); 5. let min = Math.min(...nums); 6. // 計(jì)算每個(gè)桶存放的數(shù)值范圍,至少為1, 7. let range = Math.ceil((max - min) / num) || 1; 8. // 創(chuàng)建二維數(shù)組,第一維表示第幾個(gè)桶,第二維表示該桶里存放的數(shù) 9. let arr = Array.from(Array(num)).map(() => Array().fill(0)); 10. nums.forEach(val => { 11. // 計(jì)算元素應(yīng)該分布在哪個(gè)桶 12. let index = parseInt((val - min) / range); 13. // 防止index越界,例如當(dāng)[5,1,1,2,0,0]時(shí)index會(huì)出現(xiàn)5 14. indexindex = index >= num ? num - 1 : index; 15. let temp = arr[index]; 16. // 插入排序,將元素有序插入到桶中 17. let j = temp.length - 1; 18. while(j >= 0 && val < temp[j]) { 19. temp[j+1] = temp[j]; 20. j--; 21. } 22. temp[j+1] = val; 23. }) 24. // 修改回原數(shù)組 25. let res = [].concat.apply([], arr); 26. nums.forEach((val, i) => { 27. nums[i] = res[i]; 28. }) 29. }
基數(shù)排序
使用十個(gè)桶 0-9,把每個(gè)數(shù)從低位到高位根據(jù)位數(shù)放到相應(yīng)的桶里,以此循環(huán)最大值的位數(shù)次。但只能排列正整數(shù),因?yàn)橛龅截?fù)號(hào)和小數(shù)點(diǎn)無(wú)法進(jìn)行比較。
最好:O(n * k),k表示最大值的位數(shù)。
最壞:O(n * k)
平均:O(n * k)
1. function radixSort(nums) { 2. // 計(jì)算位數(shù) 3. function getDigits(n) { 4. let sum = 0; 5. while(n) { 6. sum++; 7. n = parseInt(n / 10); 8. } 9. return sum; 10. } 11. // 第一維表示位數(shù)即0-9,第二維表示里面存放的值 12. let arr = Array.from(Array(10)).map(() => Array()); 13. let max = Math.max(...nums); 14. let maxDigits = getDigits(max); 15. for(let i=0, len=nums.length; i<len; i++) { 16. // 用0把每一個(gè)數(shù)都填充成相同的位數(shù) 17. nums[i] = (nums[i] + '').padStart(maxDigits, 0); 18. // 先根據(jù)個(gè)位數(shù)把每一個(gè)數(shù)放到相應(yīng)的桶里 19. let temp = nums[i][nums[i].length-1]; 20. arr[temp].push(nums[i]); 21. } 22. // 循環(huán)判斷每個(gè)位數(shù) 23. for(let i=maxDigits-2; i>=0; i--) { 24. // 循環(huán)每一個(gè)桶 25. for(let j=0; j<=9; j++) { 26. let temp = arr[j] 27. let len = temp.length; 28. // 根據(jù)當(dāng)前的位數(shù)i把桶里的數(shù)放到相應(yīng)的桶里 29. while(len--) { 30. let str = temp[0]; 31. temp.shift(); 32. arr[str[i]].push(str); 33. } 34. } 35. } 36. // 修改回原數(shù)組 37. let res = [].concat.apply([], arr); 38. nums.forEach((val, index) => { 39. nums[index] = +res[index]; 40. }) 41. }
計(jì)數(shù)排序
以數(shù)組元素值為鍵,出現(xiàn)次數(shù)為值存進(jìn)一個(gè)臨時(shí)數(shù)組,最后再遍歷這個(gè)臨時(shí)數(shù)組還原回原數(shù)組。因?yàn)?JavaScript 的數(shù)組下標(biāo)是以字符串形式存儲(chǔ)的,所以計(jì)數(shù)排序可以用來(lái)排列負(fù)數(shù),但不可以排列小數(shù)。
最好:O(n + k),k是最大值和最小值的差。
最壞:O(n + k)
平均:O(n + k)
1. function countingSort(nums) { 2. let arr = []; 3. let max = Math.max(...nums); 4. let min = Math.min(...nums); 5. // 裝桶 6. for(let i=0, len=nums.length; i<len; i++) { 7. let temp = nums[i]; 8. arr[temp] = arr[temp] + 1 || 1; 9. } 10. let index = 0; 11. // 還原原數(shù)組 12. for(let i=min; i<=max; i++) { 13. while(arr[i] > 0) { 14. nums[index++] = i; 15. arr[i]--; 16. } 17. } 18. }
計(jì)數(shù)排序優(yōu)化
把每一個(gè)數(shù)組元素都加上 min 的相反數(shù),來(lái)避免特殊情況下的空間浪費(fèi),通過(guò)這種優(yōu)化可以把所開(kāi)的空間大小從 max+1 降低為 max-min+1,max 和 min 分別為數(shù)組中的最大值和最小值。
比如數(shù)組 [103, 102, 101, 100],普通的計(jì)數(shù)排序需要開(kāi)一個(gè)長(zhǎng)度為 104 的數(shù)組,而且前面 100 個(gè)值都是 undefined,使用該優(yōu)化方法后可以只開(kāi)一個(gè)長(zhǎng)度為 4 的數(shù)組。
1. function countingSort(nums) { 2. let arr = []; 3. let max = Math.max(...nums); 4. let min = Math.min(...nums); 5. // 加上最小值的相反數(shù)來(lái)縮小數(shù)組范圍 6. let add = -min; 7. for(let i=0, len=nums.length; i<len; i++) { 8. let temp = nums[i]; 9. temp += add; 10. arr[temp] = arr[temp] + 1 || 1; 11. } 12. let index = 0; 13. for(let i=min; i<=max; i++) { 14. let temp = arr[i+add]; 15. while(temp > 0) { 16. nums[index++] = i; 17. temp--; 18. } 19. } 20. }
堆排序
根據(jù)數(shù)組建立一個(gè)堆(類似完全二叉樹(shù)),每個(gè)結(jié)點(diǎn)的值都大于左右結(jié)點(diǎn)(最大堆,通常用于升序),或小于左右結(jié)點(diǎn)(最小堆,通常用于降序)。對(duì)于升序排序,先構(gòu)建最大堆后,交換堆頂元素(表示最大值)和堆底元素,每一次交換都能得到未有序序列的最大值。重新調(diào)整最大堆,再交換堆頂元素和堆底元素,重復(fù) n-1 次后就能得到一個(gè)升序的數(shù)組。
最好:O(n * logn),logn是調(diào)整最大堆所花的時(shí)間。
最壞:O(n * logn)
平均:O(n * logn)
1. function heapSort(nums) { 2. // 調(diào)整最大堆,使index的值大于左右節(jié)點(diǎn) 3. function adjustHeap(nums, index, size) { 4. // 交換后可能會(huì)破壞堆結(jié)構(gòu),需要循環(huán)使得每一個(gè)父節(jié)點(diǎn)都大于左右結(jié)點(diǎn) 5. while(true) { 6. let max = index; 7. let left = index * 2 + 1; // 左節(jié)點(diǎn) 8. let right = index * 2 + 2; // 右節(jié)點(diǎn) 9. if(left < size && nums[max] < nums[left]) max = left; 10. if(right < size && nums[max] < nums[right]) max = right; 11. // 如果左右結(jié)點(diǎn)大于當(dāng)前的結(jié)點(diǎn)則交換,并再循環(huán)一遍判斷交換后的左右結(jié)點(diǎn)位置是否破壞了堆結(jié)構(gòu)(比左右結(jié)點(diǎn)小了) 12. if(index !== max) { 13. [nums[index], nums[max]] = [nums[max], nums[index]]; 14. index = max; 15. } 16. else { 17. break; 18. } 19. } 20. } 21. // 建立最大堆 22. function buildHeap(nums) { 23. // 注意這里的頭節(jié)點(diǎn)是從0開(kāi)始的,所以最后一個(gè)非葉子結(jié)點(diǎn)是 parseInt(nums.length/2)-1 24. let start = parseInt(nums.length / 2) - 1; 25. let size = nums.length; 26. // 從最后一個(gè)非葉子結(jié)點(diǎn)開(kāi)始調(diào)整,直至堆頂。 27. for(let i=start; i>=0; i--) { 28. adjustHeap(nums, i, size); 29. } 30. } 31. buildHeap(nums); 32. // 循環(huán)n-1次,每次循環(huán)后交換堆頂元素和堆底元素并重新調(diào)整堆結(jié)構(gòu) 33. for(let i=nums.length-1; i>0; i--) { 34. [nums[i], nums[0]] = [nums[0], nums[i]]; 35. adjustHeap(nums, 0, i); 36. } 37. }
希爾排序
通過(guò)某個(gè)增量 gap,將整個(gè)序列分給若干組,從后往前進(jìn)行組內(nèi)成員的比較和交換,隨后逐步縮小增量至 1。希爾排序類似于插入排序,只是一開(kāi)始向前移動(dòng)的步數(shù)從 1 變成了 gap。
最好:O(n * logn),步長(zhǎng)不斷二分。
最壞:O(n * logn)
平均:O(n * logn)
1. function shellSort(nums) { 2. let len = nums.length; 3. // 初始步數(shù) 4. let gap = parseInt(len / 2); 5. // 逐漸縮小步數(shù) 6. while(gap) { 7. // 從第gap個(gè)元素開(kāi)始遍歷 8. for(let i=gap; i<len; i++) { 9. // 逐步其和前面其他的組成員進(jìn)行比較和交換 10. for(let j=i-gap; j>=0; j-=gap) { 11. if(nums[j] > nums[j+gap]) { 12. [nums[j], nums[j+gap]] = [nums[j+gap], nums[j]]; 13. } 14. else { 15. break; 16. } 17. } 18. } 19. gap = parseInt(gap / 2); 20. } 21. }
感謝各位的閱讀,以上就是“JavaScript十大排序的算法是什么”的內(nèi)容了,經(jīng)過(guò)本文的學(xué)習(xí)后,相信大家對(duì)JavaScript十大排序的算法是什么這一問(wèn)題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。