快捷導(dǎo)航

JS前端面試必備——基本排序算法原理與實(shí)現(xiàn)方法詳解【插入/選擇/歸并/冒泡/快速排序】

更新時間：2020年02月24日 11:16:41 作者：owen1190

這篇文章主要介紹了JS前端面試基本排序算法原理與實(shí)現(xiàn)方法,結(jié)合實(shí)例形式詳細(xì)分析了JS常見的基本排序算法相關(guān)原理、實(shí)現(xiàn)方法、時間復(fù)雜度及操作注意事項,需要的朋友可以參考下

本文實(shí)例講述了JS前端面試必備——基本排序算法原理與實(shí)現(xiàn)方法。分享給大家供大家參考，具體如下：

排序算法是面試及筆試中必考點(diǎn)，本文通過動畫方式演示，通過實(shí)例講解，最后給出JavaScript版的排序算法

插入排序

算法描述：
1. 從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序
2. 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置
4. 重復(fù)步驟 3，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到該位置后
6. 重復(fù)步驟 2~5

現(xiàn)有一組數(shù)組 arr = [5, 6, 3, 1, 8, 7, 2, 4]

[5] 6 3 1 8 7 2 4 //第一個元素被認(rèn)為已經(jīng)被排序

[5,6] 3 1 8 7 2 4 //6與5比較，放在5的右邊

[3，5，6] 1 8 7 2 4 //3與6和5比較，都小，則放入數(shù)組頭部

[1,3,5,6]  8 7 2 4 //1與3,5,6比較，則放入頭部

[1,3，5，6，8]  7 2 4

[1,3，5，6,7，8] 2 4

[1，2,3，5，6,7，8] 4

[1，2,3，4，5，6,7，8]

編程思路：雙層循環(huán)，外循環(huán)控制未排序的元素，內(nèi)循環(huán)控制已排序的元素，將未排序元素設(shè)為標(biāo)桿，與已排序的元素進(jìn)行比較，小于則交換位置，大于則位置不動

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

時間復(fù)雜度O(n^2)

選擇排序

算法描述：直接從待排序數(shù)組中選擇一個最?。ɑ蜃畲螅?shù)字，放入新數(shù)組中。

[1] 5 6 3 8 7 2 4 
[1,2] 5 6 3 8 7 4 
[1,2,3] 5 6 8 7 2 4 
[1,2,3,4] 5 6 8 7
[1,2,3,4,5] 6 8 7 
[1,2,3,4,5,6] 8 7 
[1,2,3,4,5,6,7] 8 
[1,2,3,4,5,6,7,8]

編程思路：先假設(shè)第一個元素為最小的，然后通過循環(huán)找出最小元素，然后同第一個元素交換，接著假設(shè)第二個元素，重復(fù)上述操作即可

function selectSort(array) {
 var length = array.length,
   i,
   j,
   minIndex,
   minValue,
   temp;
 for (i = 0; i < length - 1; i++) {
  minIndex = i;
  minValue = array[minIndex];
  for (j = i + 1; j < length; j++) {//通過循環(huán)選出最小的
   if (array[j] < minValue) {
    minIndex = j;
    minValue = array[minIndex];
   }
  }
  // 交換位置
  temp = array[i];
  array[i] = minValue;
  array[minIndex] = temp;
 }
 return array
}

時間復(fù)雜度O(n^2)

歸并排序

算法描述：
1. 把 n 個記錄看成 n 個長度為 l 的有序子表
2. 進(jìn)行兩兩歸并使記錄關(guān)鍵字有序，得到 n/2 個長度為 2 的有序子表
3. 重復(fù)第 2 步直到所有記錄歸并成一個長度為 n 的有序表為止。

5 6 3 1 8 7 2 4

[5,6] [3,1] [8,7] [2,4]

[5,6] [1,3] [7,8] [2,4]

[5,6,1,3] [7,8,2,4]

[1,3,5,6] [2,4,7,8]

[1,2,3,4,5,6,7,8]

編程思路：將數(shù)組一直等分，然后合并

function merge(left, right) {
 var tmp = [];

 while (left.length && right.length) {
  if (left[0] < right[0])
   tmp.push(left.shift());
  else
   tmp.push(right.shift());
 }

 return tmp.concat(left, right);
}

function mergeSort(a) {
 if (a.length === 1) 
  return a;

 var mid = Math.floor(a.length / 2)
  , left = a.slice(0, mid)
  , right = a.slice(mid);

 return merge(mergeSort(left), mergeSort(right));
}

時間復(fù)雜度O(nlogn)

快速排序

算法描述：

在數(shù)據(jù)集之中，選擇一個元素作為”基準(zhǔn)”（pivot）。
所有小于”基準(zhǔn)”的元素，都移到”基準(zhǔn)”的左邊；所有大于”基準(zhǔn)”的元素，都移到”基準(zhǔn)”的右邊。這個操作稱為分區(qū) (partition)操作，分區(qū)操作結(jié)束后，基準(zhǔn)元素所處的位置就是最終排序后它的位置。
對”基準(zhǔn)”左邊和右邊的兩個子集，不斷重復(fù)第一步和第二步，直到所有子集只剩下一個元素為止。

5 6 3 1 8 7 2 4

pivot
|
5 6 3 1 9 7 2 4
|
storeIndex

5 6 3 1 9 7 2 4//將5同6比較，大于則不更換
|
storeIndex

3 6 5 1 9 7 2 4//將5同3比較，小于則更換
 |
 storeIndex

3 6 1 5 9 7 2 4//將5同1比較，小于則不更換
  |
  storeIndex
...

3 6 1 4 9 7 2 5//將5同4比較，小于則更換
   |
   storeIndex

3 6 1 4 5 7 2 9//將標(biāo)準(zhǔn)元素放到正確位置
   |
storeIndex pivot

上述講解了分區(qū)的過程，然后就是對每個子區(qū)進(jìn)行同樣做法

function quickSort(arr){
  if(arr.length<=1) return arr;
  var partitionIndex=Math.floor(arr.length/2);
  var tmp=arr[partitionIndex];
  var left=[];
  var right=[];
  for(var i=0;i<arr.length;i++){
    if(arr[i]<tmp){
      left.push(arr[i])
    }else{
      right.push(arr[i])
    }
  }
  return quickSort(left).concat([tmp],quickSort(right))
}

上述版本會造成堆棧溢出，所以建議使用下面版本

原地分區(qū)版：主要區(qū)別在于先進(jìn)行分區(qū)處理，將數(shù)組分為左小右大

function quickSort(arr){
  function swap(arr,right,left){
    var tmp = arr[right];
    arr[right]=arr[left];
    arr[left]=tmp;
  }
  function partition(arr,left,right){//分區(qū)操作，
    var pivotValue=arr[right]//最右面設(shè)為標(biāo)準(zhǔn)
    var storeIndex=left;
    for(var i=left;i<right;i++){
      if(arr[i]<=pivotValue){
        swap(arr,storeIndex,i);
        storeIndex++;
      }
    }
    swap(arr,right,storeIndex);
    return storeIndex//返回標(biāo)桿元素的索引值
  }
  function sort(arr,left,right){
    if(left>right) return;
    var storeIndex=partition(arr,left,right);
    sort(arr,left,storeIndex-1);
    sort(arr,storeIndex+1,right);
  }
  sort(arr,0,arr.length-1);
  return arr;
}

時間復(fù)雜度O(nlogn)

冒泡排序

算法描述：
1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點(diǎn)，最后的元素應(yīng)該會是最大的數(shù)。
3. 針對所有的元素重復(fù)以上的步驟，除了最后一個。
4. 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。5.

5 6 3 1 8 7 2 4

[5 6] 3 1 8 7 2 4 //比較5和6

5 [6 3] 1 8 7 2 4

5 3 [6 1] 8 7 2 4

5 3 1 [6 8] 7 2 4

5 3 1 6 [8 7] 2 4

5 3 1 6 7 [8 2] 4

5 3 1 6 7 2 [8 4]

5 3 1 6 7 2 4 8 // 這樣最后一個元素已經(jīng)在正確位置，所以下一次開始時候就不需要再比較最后一個

編程思路：外循環(huán)控制需要比較的元素，比如第一次排序后，最后一個元素就不需要比較了，內(nèi)循環(huán)則負(fù)責(zé)兩兩元素比較，將元素放到正確位置上

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

時間復(fù)雜度O(n^2)

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

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

在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
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錯誤與調(diào)試技巧總結(jié)》

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

您可能感興趣的文章: