找回密碼
 立即注冊(cè)

QQ登錄

只需一步，快速開(kāi)始

搜索
查看: 2143|回復(fù): 0
打印 上一主題 下一主題
收起左側(cè)

js算法之最常用的排序

[復(fù)制鏈接]
跳轉(zhuǎn)到指定樓層
樓主
ID:140343 發(fā)表于 2016-9-25 11:38 | 只看該作者 回帖獎(jiǎng)勵(lì) |倒序?yàn)g覽 |閱讀模式
引入
　　大學(xué)學(xué)習(xí)計(jì)算機(jī)語(yǔ)言的那幾年，從c語(yǔ)言，到c++，再到數(shù)據(jù)結(jié)構(gòu)JAVA..讓我印象最深刻的還是最開(kāi)始老師講冒泡算法的時(shí)候，直到現(xiàn)在大四快畢業(yè)了我才漸漸通竅了。剛學(xué)前端的時(shí)候以為前端就是做出好看很炫的頁(yè)面就行了，后來(lái)才漸漸懂得前端不只是頁(yè)面仔。一次美團(tuán)面試，面試官說(shuō)他們要的不僅是前端，他們要的是“工程師”，從面試開(kāi)始到結(jié)束問(wèn)都是算法，頓時(shí)把我給打擊了。二叉樹(shù)、基本算法還有時(shí)間復(fù)雜度都是很重要的東西，不僅體現(xiàn)了一個(gè)前端的學(xué)習(xí)深度，還體現(xiàn)了一名計(jì)算機(jī)學(xué)生的專(zhuān)業(yè)水平。所以，為了查缺補(bǔ)漏，我決定開(kāi)始研究一下程序猿最?lèi)?ài)提的算法,今天聊聊最常用的排序算法。魷魚(yú)看過(guò)很多資料覺(jué)得都太專(zhuān)業(yè)化了，根本看不懂，所以以下我都盡量用能讓自己（別人）看懂的介紹來(lái)描述啦~
  1. 常用排序算法
  2. 冒泡排序（Bubble sort）
  3. 　　　　大白話(huà)介紹：比較相鄰的兩個(gè)數(shù)，如果后面的比前面的小，把小的放在前面。
  4. 　　　　時(shí)間復(fù)雜度:  O(n2)
  5. 　　　   動(dòng)畫(huà)演示：冒泡排序
  6. 　　　　實(shí)際代碼：
  7. 方法一：function bubbleSort(arr){
  8.     for(var i=0;i<arr.length-1;i++){
  9.         for(var j=0;j<arr.length-1;j++){
  10.             if(arr[j+1]<arr[j]){  
  11.                 temp = arr[j+1];
  12.                 arr[j+1] = arr[j];
  13.                 arr[j] = temp;
  14.             }
  15.         }
  16.     }
  17.     return arr;
  18. }//對(duì)比arr中的第j+1項(xiàng)和第j項(xiàng)，如果第j+1項(xiàng)小于第j項(xiàng)，就把第j+1項(xiàng)和第j項(xiàng)調(diào)換位置。如果沒(méi)達(dá)到最終的順序（從小到大），就繼續(xù)找，繼續(xù)換，直到達(dá)到最終效果但是上面的方法并不完美，如果數(shù)組已經(jīng)是有序了，就沒(méi)必要再比較了，所以下面有一種優(yōu)化冒泡排序算法：

  20. 優(yōu)化冒泡排序算法
  21. 方法二（優(yōu)化算法）：function bubbleSort(arr){
  22.     var flag = false;  // 定義一個(gè)變量為false，未交換位置
  23.     for(var i=0;i<arr.length-1;i++){
  24.         for(var j=0;j<arr.length-1;j++){
  25.             if(arr[j+1]<arr[j]){
  26.                 temp = arr[j+1];
  27.                 arr[j+1] = arr[j];
  28.                 arr[j] = temp;
  29.                 flag = true; //true，已交換位置
  30.             }
  31.         }
  32.         if(flag){
  33.             flag = false; //如果交換了位置，將flag重新設(shè)為false
  34.         }else{
  35.              break;       //如果未交換，則跳出循環(huán)
  36.         }
  37.     }
  38.     return arr;
  39. }或者寫(xiě)成這樣~function bubbleSort(arr){
  40.     var flag;
  41.     for(var i=0;i<arr.length-1;i++){
  42.         flag =false;
  43.         for(var j=0;j<arr.length-1;j++){
  44.             if(arr[j+1]<arr[j]){
  45.                 temp = arr[j+1];
  46.                 arr[j+1] = arr[j];
  47.                 arr[j] = temp;
  48.                 flag = true;
  49.             }
  50.         }
  51.         if(!flag){
  52.             return arr;
  53.         }
  54.     }
  55.     return arr;
  56. }
  57. 選擇排序（selection Sort）
  58. 　　　　大白話(huà)介紹：在亂序的數(shù)組中選擇最小的值，然后和每次循環(huán)后的數(shù)組的第一位進(jìn)行交換
  59. 　　　　時(shí)間復(fù)雜度：O(n2)
  60.   　　　 動(dòng)畫(huà)演示：選擇排序
  61. 　　　　實(shí)際代碼：  
  62. var arr=[5,3,2,4,1,0];function findMin(arr,first){
  63.         var minindex = first;  //定義最小下標(biāo)
  64.         var minNum = arr[first]; //定義數(shù)組中的最小值
  65.         for(var i=first+1;i<arr.length;i++){ //循環(huán)找到最小值和最小下標(biāo)
  66.             if(arr[i]<minNum){
  67.                 minNum = arr[i];
  68.                 minindex = i;
  69.             }
  70.         }
  71.         return minindex;//返回最小值下標(biāo)  一共查找了六次，最小值下標(biāo)分別為 ：5,4,2,4,4,5
  72.     }
  73.     function selectionSort(arr){
  74.         for(var i=0;i<arr.length;i++){
  75.             var min =var temp = arr[min];     
  76.             arr[min] = arr[i];         //eg.第一次循環(huán) ：將最小值5和arr[0]進(jìn)行交換
  77.             arr[i] = temp;             // 剩下幾次同第一次
  78.         }
  79.         return arr;
  80.     }
  81.     document.write(selectionSort(arr));  //0,1,2,3,4,5, 　　　　排序過(guò)程：(自己畫(huà)的一個(gè)粗糙的框框表嫌棄)

  83.       

  85. 歸并排序（mergeSort）
  86. 　　　　大白話(huà)介紹：   把一個(gè)數(shù)組分為兩個(gè)數(shù)組，左邊排好序，右邊排好序，然后合并到一起排序
  87. 　　　   專(zhuān)業(yè)性介紹：   歸并排序是分治法的典型實(shí)例，指的是將兩個(gè)已經(jīng)排序的序列合并成一個(gè)序列的操作
  88. 　　　　時(shí)間復(fù)雜度：   O(nlogn)
  89. 　　　　動(dòng)畫(huà)演示：歸并排序
  90. 　　　　實(shí)際代碼：
  91.      var arr=[-11,17,12,19,0,-222];
  92.      function mergeSort(arr,s,e){
  93.          if(s>e){   //起始位置大于終點(diǎn)位置，返回空數(shù)組
  94.              return [];
  95.          }else if(s==e){
  96.              return [arr[s]]; //起始位置等于終點(diǎn)位置，說(shuō)明數(shù)組里只有一個(gè)數(shù)字，返回只含一個(gè)數(shù)字的數(shù)組   
  97.          }
  98.          var mIndex = Math.floor((s+e)/2); //中間位置的Index
  99.          var arrL = mergeSort(arr,s,mIndex); //將左邊的數(shù)組排序
  100.          var arrR = mergeSort(arr,mIndex+1,e); //將右邊的數(shù)組排序
  101.         
  102.          var resultArr = []; //結(jié)果數(shù)組
  103.          while(arrL.length>0 || arrR.length>0){ //當(dāng)左右兩個(gè)數(shù)組都不為空時(shí)
  104.              if(arrL[0]<arrR[0]){
  105.                  resultArr.push(arrL.shift());
  106.              }else{
  107.                  resultArr.push(arrR.shift());
  108.              }
  109.              if(arrL.length==0){  //當(dāng)左邊的數(shù)組為空時(shí)
  110.                  resultArr = resultArr.concat(arrR);
  111.                  break;
  112.              }else if(arrR.length==0){
  113.                  resultArr = resultArr.concat(arrL);
  114.                  break;
  115.              }
  116.          }
  117.          return resultArr;
  118.      }
  119.      document.write(mergeSort(arr,0,arr.length-1));　　排序過(guò)程:
  120.    

  122. 快速排序（quickSort）
  123. 　　大白話(huà)介紹：引用阮一峰老師的一句話(huà)，感覺(jué)是極好理解的~（我的目標(biāo)也是成為像阮一峰老師這樣的）
  124. �。�1）在數(shù)據(jù)集之中，選擇一個(gè)元素作為"基準(zhǔn)"（pivot）。
  125. �。�2）所有小于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的左邊；所有大于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的右邊。
  126. �。�3）對(duì)"基準(zhǔn)"左邊和右邊的兩個(gè)子集，不斷重復(fù)第一步和第二步，直到所有子集只剩下一個(gè)元素為止。      實(shí)際代碼：
  127.     var arr=[77,-33,22,32,0,2,11];
  128.     function quickSort(arr){
  129.         if(arr.length<=1){ //如果數(shù)組中只有一位數(shù)，返回?cái)?shù)組
  130.             return arr;
  131.         }
  132.         var mNumIndex = Math.floor(arr.length/2); //取基準(zhǔn)值的下標(biāo)
  133.         var mNum = arr.splice([mNumIndex],1)[0];  //取基準(zhǔn)值
  134.         var left = [];  //左邊數(shù)組
  135.         var right = []; //右邊數(shù)組
  136.       
  137.         for(var i=0;i<arr.length;i++){
  138.             if(arr[i]<mNum){  //如果數(shù)組小于基準(zhǔn)值，放在左邊數(shù)組
  139.                 left.push(arr[i]);
  140.             }else{            ///否則
  141.                 right.push(arr[i]);
  142.             }
  143.         }      
  144.         return quickSort(left).concat([mNum],quickSort(right)); //返回左邊數(shù)組+基準(zhǔn)值+右邊數(shù)組
  145.     }
  146.     document.write(quickSort(arr));　　排序過(guò)程：
復(fù)制代碼



  　　  以上就是一些常見(jiàn)的排序了，但是還有很多常見(jiàn)的排序沒(méi)有提到~~ 后期還會(huì)寫(xiě)一個(gè)常用排序二~敬請(qǐng)期待噢 ~希望我學(xué)到的東西也能幫助到大家~有說(shuō)錯(cuò)的地方歡迎批評(píng)指正~

分享到:  QQ好友和群QQ好友和群 QQ空間QQ空間 騰訊微博騰訊微博 騰訊朋友騰訊朋友
收藏收藏 分享淘帖 頂頂 踩踩
回復(fù)

使用道具 舉報(bào)

本版積分規(guī)則

手機(jī)版|小黑屋|51黑電子論壇 |51黑電子論壇6群 QQ 管理員QQ:125739409;技術(shù)交流QQ群281945664

Powered by 單片機(jī)教程網(wǎng)

快速回復(fù) 返回頂部 返回列表