這篇文章主要講解了“JavaScript十大排序的算法是什么”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“JavaScript十大排序的算法是什么”吧！

曲沃網(wǎng)站制作公司哪家好，找成都創(chuàng)新互聯(lián)！從網(wǎng)頁設計、網(wǎng)站建設、微信開發(fā)、APP開發(fā)、響應式網(wǎng)站開發(fā)等網(wǎng)站項目制作，到程序開發(fā)，運營維護。成都創(chuàng)新互聯(lián)自2013年創(chuàng)立以來到現(xiàn)在10年的時間，我們擁有了豐富的建站經(jīng)驗和運維經(jīng)驗，來保證我們的工作的順利進行。專注于網(wǎng)站建設就選成都創(chuàng)新互聯(lián)。

冒泡排序

通過相鄰元素的比較和交換，使得每一趟循環(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.  // 如果一輪比較中沒有需要交換的數(shù)據(jù)，則說明數(shù)組已經(jīng)有序。主要是對[5,1,2,3,4]之類的數(shù)組進行優(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.  }

一個人學習會有迷茫，動力不足。這里推薦一下我的前端學習交流群：731771211 ，里面都是學習前端的，如果你想制作酷炫的網(wǎng)頁，想學習編程。自己整理了一份2019最全面前端學習資料，從最基礎的HTML+CSS+JS【炫酷特效，游戲，插件封裝，設計模式】到移動端HTML5的項目實戰(zhàn)的學習資料都有整理，送給每一位前端小伙伴，有想學習web前端的，或是轉(zhuǎn)行，或是大學生，還有工作中想提升自己能力的，正在學習的小伙伴歡迎加入學習。

雙向冒泡

普通的冒泡排序在一趟循環(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ū)別在于選擇排序是將每一個元素和它后面的元素進行比較和交換。

最好：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.  }

插入排序

以第一個元素作為有序數(shù)組，其后的元素通過在這個已有序的數(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.  }

快速排序

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

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

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

平均：O(n * logn)

快速排序之填坑

從右邊向中間推進的時候，遇到小于基數(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.  }

快速排序之交換

從左右兩邊向中間推進的時候，遇到不符合的數(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.  // 交換值后兩邊各向中間推進一位  
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)

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ù)組的大值和最小值確認每個桶存放的數(shù)的區(qū)間，將數(shù)組元素插入到相應的桶里，最后再合并各個桶。

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

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

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

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.  // 計算元素應該分布在哪個桶  
12.  let index = parseInt((val - min) / range);  
13.  // 防止index越界，例如當[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ù)放到相應的桶里，以此循環(huán)大值的位數(shù)次。但只能排列正整數(shù)，因為遇到負號和小數(shù)點無法進行比較。

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

最壞：O(n * k)

平均：O(n * k)

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ù)放到相應的桶里  
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ù)當前的位數(shù)i把桶里的數(shù)放到相應的桶里  
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ù)為值存進一個臨時數(shù)組，最后再遍歷這個臨時數(shù)組還原回原數(shù)組。因為 JavaScript 的數(shù)組下標是以字符串形式存儲的，所以計數(shù)排序可以用來排列負數(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)整大堆，再交換堆頂元素和堆底元素，重復 n-1 次后就能得到一個升序的數(shù)組。

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

最壞：O(n * logn)

平均：O(n * logn)

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é)點大于當前的結(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，將整個序列分給若干組，從后往前進行組內(nèi)成員的比較和交換，隨后逐步縮小增量至 1。希爾排序類似于插入排序，只是一開始向前移動的步數(shù)從 1 變成了 gap。

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

最壞：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個元素開始遍歷  
8.  for(let i=gap; i<len; i++) {  
9.  // 逐步其和前面其他的組成員進行比較和交換  
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)過本文的學習后，相信大家對JavaScript十大排序的算法是什么這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關知識點的文章，歡迎關注！

網(wǎng)頁名稱：JavaScript十大排序的算法是什么-創(chuàng)新互聯(lián)
網(wǎng)站路徑：http://chinadenli.net/article8/deecip.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、網(wǎng)站建設、響應式網(wǎng)站、網(wǎng)站制作、靜態(tài)網(wǎng)站、手機網(wǎng)站建設

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)