自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

JavaScript：十大排序的算法思路和代碼實現(xiàn)

作者：DangoSky
開發(fā) 前端 算法
本文內(nèi)容包括：(雙向)冒泡排序、選擇排序、插入排序、快速排序(填坑和交換)、歸并排序、桶排序、基數(shù)排序、計數(shù)排序(優(yōu)化)、堆排序、希爾排序。大家可以在這里測試代碼。更多 leetcode 的 JavaScript 解法也可以在我的算法倉庫中找到，歡迎查看。

 本文內(nèi)容包括：(雙向)冒泡排序、選擇排序、插入排序、快速排序(填坑和交換)、歸并排序、桶排序、基數(shù)排序、計數(shù)排序(優(yōu)化)、堆排序、希爾排序。大家可以在這里測試代碼。更多 leetcode 的 JavaScript 解法也可以在我的算法倉庫中找到，歡迎查看~

另外附上十大排序的 C++版本，因為寫慣了JavaScript，所以這個 C++版本寫得有些丑，請不要介意呀。

如果你覺得有幫助的話，就點個 star 鼓勵鼓勵我吧，蟹蟹😊

先推薦一個數(shù)據(jù)結(jié)構(gòu)和算法動態(tài)可視化工具，可以查看各種算法的動畫演示。下面開始正文。

冒泡排序

通過相鄰元素的比較和交換，使得每一趟循環(huán)都能找到未有序數(shù)組的***值或最小值。

***：O(n)，只需要冒泡一次數(shù)組就有序了。 

最壞：O(n²) 

平均：O(n²)

單向冒泡 

  1. function bubbleSort(nums) {  
  2.   for(let i=0, len=nums.length; i<len-1; i++) {  
  3.     // 如果一輪比較中沒有需要交換的數(shù)據(jù)，則說明數(shù)組已經(jīng)有序。主要是對[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. }  

雙向冒泡

普通的冒泡排序在一趟循環(huán)中只能找出一個***值或最小值，雙向冒泡則是多一輪循環(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ū)別在于選擇排序是將每一個元素和它后面的元素進(jìn)行比較和交換。

***：O(n²) 

最壞：O(n²) 

平均：O(n²) 

  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. }  

插入排序

以***個元素作為有序數(shù)組，其后的元素通過在這個已有序的數(shù)組中找到合適的位置并插入。

***：O(n)，原數(shù)組已經(jīng)是升序的。 

最壞：O(n²) 

平均：O(n²) 

  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. }  

快速排序

選擇一個元素作為基數(shù)（通常是***個元素），把比基數(shù)小的元素放到它左邊，比基數(shù)大的元素放到它右邊（相當(dāng)于二分），再不斷遞歸基數(shù)左右兩邊的序列。

***：O(n * logn)，所有數(shù)均勻分布在基數(shù)的兩邊，此時的遞歸就是不斷地二分左右序列。 

最壞：O(n²)，所有數(shù)都分布在基數(shù)的一邊，此時劃分左右序列就相當(dāng)于是插入排序。 

平均：O(n * logn)

參考學(xué)習(xí)鏈接： 

算法 3：最常用的排序——快速排序 

三種快速排序以及快速排序的優(yōu)化

快速排序之填坑

從右邊向中間推進(jìn)的時候，遇到小于基數(shù)的數(shù)就賦給左邊（一開始是基數(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.     // 取***個數(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ù)就兩邊交換值。 

  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ù)組分為兩個序列，有序合并這兩個序列。

***：O(n * logn) 

最壞：O(n * logn) 

平均：O(n * logn)

參考學(xué)習(xí)鏈接： 

圖解排序算法(四)之歸并排序 

  1. function mergeSort(nums) {  
  2.   // 有序合并兩個數(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ù)組分為兩個序列  
  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 個桶，根據(jù)數(shù)組的***值和最小值確認(rèn)每個桶存放的數(shù)的區(qū)間，將數(shù)組元素插入到相應(yīng)的桶里，***再合并各個桶。

***：O(n)，每個數(shù)都在分布在一個桶里，這樣就不用將數(shù)插入排序到桶里了(類似于計數(shù)排序以空間換時間)。 

最壞：O(n²)，所有的數(shù)都分布在一個桶里。 

平均：O(n + k)，k表示桶的個數(shù)。

參考學(xué)習(xí)鏈接： 

拜托，面試別再問我桶排序了?。?！ 

  1. function bucketSort(nums) {  
  2.   // 桶的個數(shù)，只要是正數(shù)即可  
  3.   let num = 5;  
  4.   let max = Math.max(...nums);  
  5.   let min = Math.min(...nums);  
  6.   // 計算每個桶存放的數(shù)值范圍，至少為1，  
  7.   let range = Math.ceil((max - min) / num) || 1;  
  8.   // 創(chuàng)建二維數(shù)組，***維表示第幾個桶，第二維表示該桶里存放的數(shù)  
  9.   let arr = Array.from(Array(num)).map(() => Array().fill(0));  
  10.   nums.forEach(val => {  
  11.     // 計算元素應(yīng)該分布在哪個桶  
  12.     let index = parseInt((val - min) / range);  
  13.     // 防止index越界，例如當(dāng)[5,1,1,2,0,0]時index會出現(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ù)排序

使用十個桶 0-9，把每個數(shù)從低位到高位根據(jù)位數(shù)放到相應(yīng)的桶里，以此循環(huán)***值的位數(shù)次。但只能排列正整數(shù)，因為遇到負(fù)號和小數(shù)點無法進(jìn)行比較。

***：O(n * k)，k表示***值的位數(shù)。 

最壞：O(n * k) 

平均：O(n * k)

參考學(xué)習(xí)鏈接： 

算法總結(jié)系列之五: 基數(shù)排序(Radix Sort) 

  1. function radixSort(nums) {  
  2.   // 計算位數(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把每一個數(shù)都填充成相同的位數(shù)  
  17.     nums[i] = (nums[i] + '').padStart(maxDigits, 0);  
  18.     // 先根據(jù)個位數(shù)把每一個數(shù)放到相應(yīng)的桶里  
  19.     let temp = nums[i][nums[i].length-1];  
  20.     arr[temp].push(nums[i]);  
  21.   }  
  22.   // 循環(huán)判斷每個位數(shù)  
  23.   for(let i=maxDigits-2; i>=0; i--) {  
  24.     // 循環(huán)每一個桶  
  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. }  

計數(shù)排序

以數(shù)組元素值為鍵，出現(xiàn)次數(shù)為值存進(jìn)一個臨時數(shù)組，***再遍歷這個臨時數(shù)組還原回原數(shù)組。因為 JavaScript 的數(shù)組下標(biāo)是以字符串形式存儲的，所以計數(shù)排序可以用來排列負(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. }  

計數(shù)排序優(yōu)化

把每一個數(shù)組元素都加上 min 的相反數(shù)，來避免特殊情況下的空間浪費，通過這種優(yōu)化可以把所開的空間大小從 max+1 降低為 max-min+1，max 和 min 分別為數(shù)組中的***值和最小值。

比如數(shù)組 [103, 102, 101, 100]，普通的計數(shù)排序需要開一個長度為 104 的數(shù)組，而且前面 100 個值都是 undefined，使用該優(yōu)化方法后可以只開一個長度為 4 的數(shù)組。 

  1. function countingSort(nums) {  
  2.   let arr = [];  
  3.   let max = Math.max(...nums);  
  4.   let min = Math.min(...nums);  
  5.   // 加上最小值的相反數(shù)來縮小數(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ù)組建立一個堆（類似完全二叉樹），每個結(jié)點的值都大于左右結(jié)點（***堆，通常用于升序），或小于左右結(jié)點（最小堆，通常用于降序）。對于升序排序，先構(gòu)建***堆后，交換堆頂元素（表示***值）和堆底元素，每一次交換都能得到未有序序列的***值。重新調(diào)整***堆，再交換堆頂元素和堆底元素，重復(fù) n-1 次后就能得到一個升序的數(shù)組。

***：O(n * logn)，logn是調(diào)整***堆所花的時間。 

最壞：O(n * logn) 

平均：O(n * logn)

參考學(xué)習(xí)鏈接： 

常見排序算法 - 堆排序 (Heap Sort) 

圖解排序算法(三)之堆排序 

  1. function heapSort(nums) {  
  2.   // 調(diào)整***堆，使index的值大于左右節(jié)點  
  3.   function adjustHeap(nums, index, size) {  
  4.     // 交換后可能會破壞堆結(jié)構(gòu)，需要循環(huán)使得每一個父節(jié)點都大于左右結(jié)點  
  5.     while(true) {  
  6.       let max = index;  
  7.       let left = index * 2 + 1;   // 左節(jié)點  
  8.       let right = index * 2 + 2;  // 右節(jié)點  
  9.       if(left < size && nums[max] < nums[left])  max = left;  
  10.       if(right < size && nums[max] < nums[right])  max = right;  
  11.       // 如果左右結(jié)點大于當(dāng)前的結(jié)點則交換，并再循環(huán)一遍判斷交換后的左右結(jié)點位置是否破壞了堆結(jié)構(gòu)（比左右結(jié)點小了）  
  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é)點是從0開始的，所以***一個非葉子結(jié)點是 parseInt(nums.length/2)-1  
  24.     let start = parseInt(nums.length / 2) - 1;  
  25.     let size = nums.length;  
  26.     // 從***一個非葉子結(jié)點開始調(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. }  

希爾排序

通過某個增量 gap，將整個序列分給若干組，從后往前進(jìn)行組內(nèi)成員的比較和交換，隨后逐步縮小增量至 1。希爾排序類似于插入排序，只是一開始向前移動的步數(shù)從 1 變成了 gap。

***：O(n * logn)，步長不斷二分。 

最壞：O(n * logn) 

平均：O(n * logn)

參考學(xué)習(xí)鏈接： 

圖解排序算法(二)之希爾排序 

  1. function shellSort(nums) {  
  2.   let len = nums.length;  
  3.   // 初始步數(shù)  
  4.   let gap = parseInt(len / 2);  
  5.   // 逐漸縮小步數(shù)  
  6.   while(gap) {  
  7.     // 從第gap個元素開始遍歷  
  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. }  

看完后如果大家有什么疑問或發(fā)現(xiàn)一些錯誤，可以在下方留言呀，或者在我的倉庫里 提issues，我們一起討論討論😊 

責(zé)任編輯：龐桂玉 來源： segmentfault
JavaScript算法思路代碼實現(xiàn)
相關(guān)推薦

2021-08-25 09:59:00

開發(fā)排序代碼

2020-11-25 10:40:58

程序員技能開發(fā)者

2018-10-10 14:03:00

Java開發(fā)代碼

2019-08-28 11:08:51

排序算法Java

2020-09-14 14:47:13

排序算法

2015-10-08 09:08:50

Python實現(xiàn)

2022-03-10 12:03:33

Python算法代碼

2018-11-14 09:40:05

排序算法Java編程語言

2017-07-18 10:50:38

前端JavaScript排序算法

2021-10-31 07:38:37

排序算法代碼

2015-11-12 11:05:07

java排序算法

2019-08-08 16:54:08

GitHubJavaScript編程語言

2021-04-05 14:48:51

JavaScriptjQuery函數(shù)

2025-04-08 01:11:00

算法FFT排序

2020-08-16 11:37:27

Python開發(fā)工具

2009-02-23 10:17:36

Javascript框架應(yīng)用

2021-01-21 05:22:36

排序算法選擇

2021-01-26 05:33:07

排序算法快速

2021-11-08 15:12:48

排序算法面試

2022-05-11 15:20:31

機(jī)器學(xué)習(xí)算法預(yù)測
點贊
收藏

51CTO技術(shù)棧公眾號