快捷導(dǎo)航

JS實(shí)現(xiàn)的冒泡排序，快速排序，插入排序算法示例

更新時(shí)間：2019年03月02日 11:20:06 作者：huangpb0624

這篇文章主要介紹了JS實(shí)現(xiàn)的冒泡排序，快速排序，插入排序算法,結(jié)合實(shí)例形式分析了javascript冒泡排序，快速排序，插入排序算法的相關(guān)原理及實(shí)現(xiàn)方法,需要的朋友可以參考下

本文實(shí)例講述了JS實(shí)現(xiàn)的冒泡排序，快速排序，插入排序算法。分享給大家供大家參考，具體如下：

一、冒泡排序

大致分兩步：

1、依次對(duì)比相鄰2個(gè)數(shù)字，前者比后者大就調(diào)換位置

2、重復(fù)第一步操作，直到所有數(shù)字都按順序排列

function bubbleSort(arr){
  for(var i=1; i<arr.length; i++){
   for(var j=0; j<arr.length-i; j++){
    if(arr[j]>arr[j+1]){
     arr[j]=[arr[j+1],arr[j+1]=arr[j]][0];
    }
   }
  }
  return arr;
}

二、快速排序

大致分三步：

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=[], 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));
}

三、插入排序（對(duì)于少量元素比較有效）

原理：像排序一手撲克牌，開始時(shí)，我們的左手為空并且桌子上的牌面向下。然后，我們每次從桌子上拿走一張牌并將它插入左手中正確的

位置。為了找到一張牌的正確位置，我們從右到左將它與已在手中的每張牌進(jìn)行比較，如圖2-1所示。拿在左手上的牌總是排序好的，原來(lái)這些牌是桌子上牌堆中頂部的牌。

手上的牌是有序數(shù)列，桌子上的牌是無(wú)序數(shù)列。

function insertSort(arr){
  //從第二個(gè)數(shù)開始，依次插入
  for(var i=1; i<arr.length; i++){
   //判斷目標(biāo)元素是否小于前一個(gè)元素
   if(arr[i]<arr[i-1]){
    var current=arr[i];
    var j=i-1;
    //從有序數(shù)列從后往前對(duì)比，如果目標(biāo)元素小于與之對(duì)比的當(dāng)前元素，當(dāng)前元素位置往后挪一位
    while(j>=0 && current<arr[j]) {
     arr[j+1]=arr[j];
     j--;
    }
    //插入
    arr[j+1]=current;
   }
  }
  return arr;
}

插入排序另一種寫法（個(gè)人感覺還是這種效率快）

function insertSort(arr) {
  for(let i=1; i<arr.length; i++) {
    if(arr[i] < arr[0]) {
      arr.unshift(arr.splice(i,1)[0]);
    }else {
      for(let j=i-1; j>=0; j--) {
        if(arr[i] > arr[j]) {
          let current = arr.splice(i,1)[0];
          arr.splice(j+1,0,current);
          break;
        }
      }
    }
  }
  return arr;
}

感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運(yùn)行工具：http://tools.jb51.net/code/HtmlJsRun測(cè)試上述代碼運(yùn)行效果。

PS：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：

在線動(dòng)畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》

希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: