閱讀目錄

• 冒泡排序
• 插入排序
• 希爾排序
• 歸并排序
• 快速排序
• 選擇排序
• 奇偶排序

總結(jié)

前言：在前端大全中看到這句話，以此共勉?；A(chǔ)決定你可能達(dá)到的高度， 而業(yè)務(wù)決定了你的最低瓶頸

其實(shí)javascript算法在平時(shí)的編碼中用處不大，不過(guò)不妨礙我們學(xué)習(xí)它，學(xué)習(xí)一下這些算法的思想，鍛煉一下自己的思維模式。

本文不會(huì)每種方法都介紹一下，只介紹一下七種，純屬為了學(xué)習(xí)而學(xué)習(xí)，如果覺(jué)得代碼不是很好理解，可以將數(shù)組里面的內(nèi)容代入函數(shù)里面。

不過(guò)剛開始理解的時(shí)候確實(shí)挺頭疼的。廢話少說(shuō)，搞起來(lái)?。?/p>

冒泡排序

原理：

從第一個(gè)元素開始，往后比較，遇到比自己小的元素就交換位置

（來(lái)源于百度圖片）

特點(diǎn)：

交換的次數(shù)最多，所以它的性能是最差的

代碼實(shí)現(xiàn)：

function bubbleSort(arr){
 var len=arr.length;
 for(var i=0;i<len;i++){
 for(var j=0;j<len-1-i;j++){ 
  if(arr[j]>arr[j+1]){ //相鄰元素兩兩對(duì)比
  var temp=arr[j+1]; //交互位置,所以大的都放到了最后面
  arr[j+1]=arr[j];
  arr[j]=temp;

  }
 }
 }
 return arr;
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(bubbleSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

插入排序

原理：

插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)

如圖所示

在插入排序中，數(shù)組會(huì)被劃分為兩種，“有序數(shù)組塊”和“無(wú)序數(shù)組塊”，

   第一遍的時(shí)候從”無(wú)序數(shù)組塊“中提取一個(gè)數(shù)20作為有序數(shù)組塊。

   第二遍的時(shí)候從”無(wú)序數(shù)組塊“中提取一個(gè)數(shù)60有序的放到”有序數(shù)組塊中“，也就是20，60。

   第三遍的時(shí)候同理，不同的是發(fā)現(xiàn)10比有序數(shù)組的值都小，因此20，60位置后移，騰出一個(gè)位置讓10插入。

   然后按照這種規(guī)律就可以全部插入完畢。

下面是一張gif圖

特點(diǎn)：

插入算法把要排序的數(shù)組分成兩部分：

第一部分包含了這個(gè)數(shù)組的所有元素，但將第一個(gè)元素除外（讓數(shù)組多一個(gè)空間才有插入的位置）.

第二部分就只包含這一個(gè)元素（即待插入元素）。在第一部分排序完成后，再將這個(gè)最后元素插入到已排好序的第一部分中

比冒泡排序快一點(diǎn)

代碼實(shí)現(xiàn)：

//插入排序
//假定當(dāng)前元素之前的元素已經(jīng)排好序，先把自己的位置空出來(lái)，
//然后前面比自己大的元素依次向后移，直到空出一個(gè)"坑"，
//然后把目標(biāo)元素插入"坑"中
function insertSort(arr){
 // 從第二個(gè)元素開始，因?yàn)橐舫鲆粋€(gè)坑
 for(var i=1;i<arr.length;i++){
 var x=arr[i]; 
 for(var j=i-1;arr[j]>x;j--){ //后挪空出位置 .
  arr[j+1]=arr[j];
 }
 if(arr[j+1]!=x){
  arr[j+1]=x;
 }
 }
 return arr;
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(insertSort(arr,2)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

希爾排序

原理：

希爾排序也叫 遞減增量排序算法，是插入排序的一種神龜進(jìn)化版。

什么叫遞減增量呢，就是定義一個(gè)間隔序列，例如是5，3，1。第一次處理，會(huì)處理所有間隔為5的，

下一次會(huì)處理間隔為3的，最后一次處理間隔為1的元素。也就是相鄰元素執(zhí)行標(biāo)準(zhǔn)插入排序。

 步驟如下：

    1、先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組。

    2、所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中，在各組內(nèi)進(jìn)行直接插入排序。

    3、取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，

    4、直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?/p>

這里增量的取法如下：

    第一次增量的取法為： d=count/2;

    第二次增量的取法為:  d=(count/2)/2;

    最后一直到: d=1;

看上圖觀測(cè)的現(xiàn)象為：

    d=3時(shí)：將40跟50比，因50大，不交換。

                 將20跟30比，因30大，不交換。

                 將80跟60比，因60小，交換。

    d=2時(shí)：將40跟60比，不交換，拿60跟30比交換，此時(shí)交換后的30又比前面的40小，又要將40和30交換，如上圖。

                 將20跟50比，不交換，繼續(xù)將50跟80比，不交換。

    d=1時(shí)：這時(shí)就是前面講的插入排序了，不過(guò)此時(shí)的序列已經(jīng)差不多有序了，所以給插入排序帶來(lái)了很大的性能提高。

特點(diǎn)：

　由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序，但在不同的插入排序過(guò)程中，

  相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂，所以shell排序是不穩(wěn)定的。

　打個(gè)比方，我原來(lái)的數(shù)組是[5,4,3,2,1]的，這樣一打亂就全部重新排了。

代碼實(shí)現(xiàn)：

 function shellSort(arr){
 var gap=Math.floor(arr.length/2);
 while(gap>0){
 for(var i=gap;i<arr.length;i++){
  temp=arr[i];
  for(var j=i;j>=gap&&arr[j-gap]>temp;j-=gap){
  arr[j]=arr[j-gap];
  }
  arr[j]=temp;
 }
 gap=Math.floor(gap/2);
 }
 return arr;
}
var arr = [2,3,6,4,2,1,90,100,20,5];
console.log(shellSort(arr)); //[1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

歸并排序

原理：

歸并排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。

有以下幾個(gè)步驟：

  1、把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列;

  2、對(duì)這兩個(gè)子序列繼續(xù)分為m/2的子序列，一直分下去

  3、將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。

再來(lái)一張靜態(tài)圖，比較好理解

這里需要補(bǔ)充是，歸并中對(duì)數(shù)組的分割是從上往下的，歸并中數(shù)組的比較是從下往上的。

特點(diǎn)：

速度僅次于快速排序，為穩(wěn)定排序算法，一般用于對(duì)總體無(wú)序，但是各子項(xiàng)相對(duì)有序的數(shù)列.

屬于分治思想，遞歸歸并

代碼實(shí)現(xiàn)：

/* 排序并合并*/
function merge(left, right) {
 var re = [];
 while(left.length > 0 && right.length > 0) {
 if(left[0] < right[0]) {
　　　　　　// 如果左邊的數(shù)據(jù)小于右邊的數(shù)據(jù)，將左邊的數(shù)據(jù)取出，放到新數(shù)組那里
  re.push(left.shift());
 } else {
  re.push(right.shift());
 }
 }
 /* 當(dāng)左右數(shù)組長(zhǎng)度不等.將比較完后剩下的數(shù)組項(xiàng)鏈接起來(lái)即可 */
 return re.concat(left).concat(right);
}
function mergeSort(arr) {
 if(arr.length == 1){
 return arr;
 }
 /* 首先將無(wú)序數(shù)組劃分為兩個(gè)數(shù)組 */
 var mid = Math.floor(arr.length / 2);
 var left = arr.slice(0, mid);
 var right = arr.slice(mid);
 /* 遞歸分別對(duì)左右兩部分?jǐn)?shù)組進(jìn)行排序合并 */
 return merge(mergeSort(left), mergeSort(right));
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(mergeSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

快速排序

原理：

1、在數(shù)據(jù)集之中，選擇一個(gè)元素作為"基準(zhǔn)"（pivot）。比如選擇下面數(shù)字45

2、所有小于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的左邊；所有大于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的右邊。

3、對(duì)"基準(zhǔn)"左邊和右邊的兩個(gè)子集，不斷重復(fù)第一步和第二步，直到所有子集只剩下一個(gè)元素為止。

特點(diǎn)：速度最快。和歸并排序不同的是，歸并排序是先分為兩組再繼續(xù)排，而快速排序是邊分邊排

代碼實(shí)現(xiàn)：

// 大致分三步：
 // 1、找基準(zhǔn)（一般是以中間項(xiàng)為基準(zhǔn)）
 // 2、遍歷數(shù)組，小于基準(zhǔn)的放在left，大于基準(zhǔn)的放在right
 // 3、遞歸
 function quickSort(arr){
 //如果數(shù)組<=1,則直接返回
 if(arr.length<=1){
  return arr;
 }
 var pivotIndex=Math.floor(arr.length/2);
 //找基準(zhǔn)，并把基準(zhǔn)從原數(shù)組刪除
 var pivot=arr.splice(pivotIndex,1)[0];
 //定義左右數(shù)組
 var left=[];
 var right=[];

 //比基準(zhǔn)小的放在left，比基準(zhǔn)大的放在right
 for(var i=0;i<arr.length;i++){
  if(arr[i]<=pivot){
  left.push(arr[i]);
  }else{
  right.push(arr[i]);
  }
 }
 //遞歸
 return quickSort(left).concat([pivot],quickSort(right));
 }
 var arr=[2,3,6,4,2,1,90,100,20,5];
 console.log(quickSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

選擇排序

原理：在要排序的一組數(shù)中，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換，然后剩下的數(shù)當(dāng)中找出最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)直到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)為止。

靜態(tài)圖：

特點(diǎn)：可以說(shuō)是冒泡排序的衍生品，效率比較一般般

代碼實(shí)現(xiàn)：

// 在無(wú)序區(qū)中選出最小的元素，然后將它和無(wú)序區(qū)的第一個(gè)元素交換位置。
function selectSort(arr){
 length = arr.length;
 for (var i = 0; i < length; i++){ // 循環(huán)數(shù)組
 var _min = arr[i]; // 把每一次的 數(shù)組里面的數(shù)字記錄下來(lái)
 var k = i;   // 記錄下來(lái)索引
 for (var j = i + 1; j < length; j++){ // 當(dāng)前的數(shù)字與后一個(gè)數(shù)字相比較
  if (_min > arr[j]){ //當(dāng)前的數(shù) 大于 后面一個(gè)數(shù)的話
  _min = arr[j]; // 就講后面 的數(shù)值 保存下來(lái)
  k = j;  /// 保存索引
  }
 }
 arr[k] = arr[i]; // 進(jìn)行交換位置
 arr[i] = _min;
 }
 return arr;
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(selectSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

奇偶排序

原理：

選取所有奇數(shù)列的元素與其右側(cè)相鄰的元素進(jìn)行比較，將較小的元素排序在前面；

選取所有偶數(shù)列的元素與其右側(cè)相鄰的元素進(jìn)行比較，將較小的元素排序在前面；

重復(fù)前面兩步，直到所有序列有序?yàn)橹埂?/p>

如下圖所示：

gif圖：

特點(diǎn)：奇數(shù)和偶數(shù)序列交替比較

代碼實(shí)現(xiàn)：

function oddEvenSort(arr){
 //swaped用來(lái)控制循環(huán)是否要繼續(xù)，如果左邊的都比右邊的小，則退出循環(huán)，返回排好的數(shù)組
 var swaped=true; 
 var k=0;
 while(swaped){
 if(k>0){
  swaped=false; 
 }
 for(var i=k;i<arr.length-1;i+=2){
  if(arr[i]>arr[i+1]){
  // 如果左邊的數(shù)字比右邊的大，兩者交換位置
  arr[i]=[ arr[i+1], arr[i+1]=arr[i] ][0]; 
  swaped=true;
  }
 }
 k=[1,0][k]; //奇數(shù)和偶數(shù)之間的轉(zhuǎn)行
 }
 return arr;
} 
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(oddEvenSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

總結(jié)

本文只是總結(jié)了算法中的一部分，算法的精髓就在于他們的思想，在js中用處應(yīng)該不是很大。如果第一遍看不太懂那些代碼，可以試著自己敲一遍，我在總結(jié)的時(shí)候，遇到理解不了的代碼，自己敲完理解程度就會(huì)加深一些。

理解完，確實(shí)這些算法的實(shí)現(xiàn)思想博大精深，不得不感慨一下前輩們思想的深度。

以上就是本文的全部?jī)?nèi)容，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助，同時(shí)也希望多多支持腳本之家！

最新評(píng)論