JavaScript 版各大排序算法

FrozenMap 發布于2019-08-20 13:47 / 2381人閱讀

摘要：推薦一下，，這里還有個可視化的排序博客，各大排序算法的實現都栩栩如生。堆排序堆排序是指利用堆這種數據結構所設計的一種排序算法。共勉參考維基百科排序搜索聊一聊排序算法秒殺種排序算法版排序圖解排序算法實現歡迎來我的博客交流

最近看到了很多公司都在準備明年的實習校招，雖然離三月份還有一段時間，感覺已經可以準備了。在網上看了一些排序算法和數組去重操作，感覺都寫的很好，心血來潮，也來寫一寫。

排序算法的設計和實現

說到排序，之前在做百度前端學院的題目的時候，也碰到過，并把它整理到 github 上。這是一個可視化的排序展示，支持冒泡、插入和選擇排序，具體使用先隨機添加 40 個，然后點排序，就可以看到可視化的效果。

推薦一下，HTML5 Canvas Demo: Sorting Algorithms，這里還有個可視化的排序博客，各大排序算法的實現都栩栩如生。

javascript 寫排序算法也比較奇葩，主要是參數的問題，比如 javascript 算法函數可以扔給 Array 原型：Array.prototype.sort = function，也可以直接寫個函數帶參數：function sort(array){}，在我看來，哪種方法都一樣，需要注意的是兼容性的問題，如果可以考慮對所有可遍歷對象都能排序（比如 arguments），才大法好。

好了，直接入主題了（下面的排序均是從小到大的順序）。

插入排序

插入排序是一種基本排序，它的基本思路是構建有序序列，對于未排序的數據，在已排序的基礎上，從右向左（或者二分查找）選擇位置插入，維基百科-插入排序。

function insert_sort(input){
  var i, j, temp;
  for(i = 1; i < input.length; i++){
    temp = input[i];
    for(j = i-1; j >= 0 && input[j] > temp; j--)
      input[j+1] = input[j];
    input[j+1] = temp;
  }
  return input;
}

如果以比較次數和移動次數來衡量算法的效率，最好情況下，比較 n-1 次，移動 0 次，最壞情況，比較 n*(n-1)/2 次，移動 n*(n-1)/2 次。

二分插入排序

思路基本同上，只是在查找插入位置的時候，不是依次查找，而是采用二分法：

function bin_insert_sort(input){
  var i, j, low, high, mid, temp;
  for(i = 1; i < input.length; i++){
    temp = input[i];
    high = i - 1;
    low = 0;
    while(low <= high){
      mid = parseInt((low + high) / 2);
      if(temp < input[mid]){
        high = mid - 1;
      }else{
        low = mid + 1;
      }
    }
    // low 位置就是要插入的位置
    for(j = i-1; j >= low; j--)
      input[j+1] = input[j];
    input[low] = temp;
  }
  return input;
}

希爾排序

希爾排序其實是加強版的插入排序，就是在原先插入排序的基礎上，加入了步長，原先插入排序的步長是 1，而且步長不同，效率也有差異，選擇一個合適的步長也很重要。而且，希爾排序的最后一步，也必定是步長為 1 的插入排序，只不過此時整個排序已經基本穩定。維基百科-希爾排序。

function shell_sort(input){
  var gap, i, j, temp;
  gap = input.length >> 1;
  while(gap > 0){
    for (i = gap; i < input.length; i++) {
      temp = input[i];
      for (j = i - gap; j >= 0 && input[j] > temp; j -= gap)
        input[j + gap] = input[j];
      input[j + gap] = temp;
    }
    gap = gap >> 1;
  }
  return input;
}

選擇排序

選擇排序的工作原理：首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。維基百科-冒泡排序。

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

選擇排序在最好情況下，也要比較 n*(n-1)/2，移動 n-1 次（這里可以加個判斷，移動 0 次），最差情況下，比較 n*(n-1)/2 次，移動 n-1 次。所有最好，最壞情況下，比較次數是一樣的。

冒泡排序

冒泡排序的基本原理：對于帶排序列，它會多次遍歷序列，每次都會比較相鄰的兩個元素，若順序相反，即交換它們，維基百科-冒泡排序。

function bubble_sort(input){
  var i, j, temp, flag;
  for(i = 0; i < input.length - 1; i++){
    flag = true;
    for(j = 0; j < input.length - i; j++){
      if(input[j] > input[j + 1]){
        temp = input[j];
        input[j] = input[j + 1];
        input[j + 1] = temp;
        flag = false;
      }
    }
    if(flag)
      // 提前結束
      break;
  }
  return input;
}

有 flag 時，最好情況比較 n-1 次，移動 0 次，最壞情況，比較 n*(n-1)/2 次，交換 n*(n-1)/2。

快排

記得我一個同學去百度面試，百度面試官上來就讓他手寫了一個快排，可見對快排的掌握很重要呀，而且快排理解起來也不容易。

維基百科-快排。快排的基本思路就是選擇一個元素，然后按照與這個元素的比較，將大于這個元素的都拿到右邊，小于這個元素的都拿到左邊，并找到這個元素的位置，這個元素的左右兩邊遞歸。

function quick_sort(input){
  function sort(start, end){
    if(start >= end){
      return;
    }
    var mid = partition(start, end);
    sort(start, mid - 1);
    sort(mid + 1, end);
  }
  function partition(start, end){
    var left = start, right = end, key = input[start], temp;
    while(left < right){
      while(left < right && input[right] >= key){
        right --;
      }
      input[left] = input[right];
      while(left < right && input[left] <= key){
        left ++;
      }
      input[right] = input[left];
    }
    input[left] = key;
    return left;
  }
  // main here
  sort(0, input.length - 1);
  return input;
}

partition 函數就是來找對應的 mid，sort 函數用來排序。

關于快排的優化，可以從以下幾個方面來考慮：

partition 函數的哨兵（比較值）除了 start 以外，用其他位置（比如中位數）是否可行；

當 start 和 end 間距很小的時候，改用其他高效算法

還有就是優化遞歸。

其實呢，上面的這個算法，并不屬于 JavaScript 版本，而更像 C 版本的，重在讓人理解快排，下面是 JS 版的快排，來體驗下 JS 的迷人特性吧：

// javascript 版
function quick_sort(input) {
  var len = input.length;
  if (len <= 1)
    return input.slice(0);
  var left = [];
  var right = [];
  // 基準函數
  var mid = [input[0]];
  for (var i = 1; i < len; i++)
    if (input[i] < mid[0])
      left.push(input[i]);
    else
      right.push(input[i]);
  return quick_sort(left).concat(mid.concat(quick_sort(right)));
};

這個 JS 版快排也比較好懂，找到那個基準（這里是第一個元素 input[0]）之后，遍歷，把小于基準的放到左邊，大于基準的放到右邊，然后返回拼接數組。

歸并排序

在學習分治算法時，典型的一個例子就是歸并。維基百科-歸并排序。思路就是先分后和，依舊是遞歸。

function merge_sort(input){
  function merge(left, right){
    var temp = [];
    var i = 0, j = 0;
    while(i < left.length && j < right.length){
      if(left[i] < right[j]){
        temp.push(left[i]);
        i++;
      }else{
        temp.push(right[j]);
        j++;
      }
    }
    if(i < left.length){
      temp = temp.concat(left.slice(i));
    }
    if(j < right.length){
      temp = temp.concat(right.slice(j));
    }
    return temp;
  }
  if(input.length <=1){
    return input;
  }
  var mid = parseInt(input.length / 2);
  return merge(merge_sort(input.slice(0, mid)), merge_sort(input.slice(mid)))
}

同樣，以上歸并仍然是類似 C 語言版本，JavaScript 版本如下：

// javascript 版
function merge_sort(input) {
  var merge = function(left, right) {
    var final = [];
    while (left.length && right.length)
      final.push(left[0] <= right[0] ? left.shift() : right.shift());
    return final.concat(left.concat(right));
  };
  var len = input.length;
  if (len < 2) return input;
  var mid = len / 2;
  return merge(merge_sort(input.slice(0, parseInt(mid))), merge_sort(input.slice(parseInt(mid))));
};

數組的一系列操作大大優化排序的過程。

堆排序

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。維基百科-堆排序。

其實，對于堆排序，只要牢記幾個操作就可以，比如找到最后一個父節點，如何找到子節點（初始為 0），如何建立一個最大堆。

function heap_sort(input){
  var arr = input.slice(0);
  function swap(i, j) {
    var tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
  // 上推操作
  function max_heapify(start, end) {
    var dad = start;
    var son = dad * 2 + 1;
    if (son >= end)
      return;
    if (son + 1 < end && arr[son] < arr[son + 1])
      son++;
    if (arr[dad] <= arr[son]) {
      swap(dad, son);
      max_heapify(son, end);
    }
  }

  var len = arr.length;
  // 建立一個最大堆
  for (var i = Math.floor(len / 2) - 1; i >= 0; i--)
    max_heapify(i, len);
  for (var i = len - 1; i > 0; i--) {
    swap(0, i);
    max_heapify(0, i);
  }

  return arr;
};

堆排序的過程大致如下：先生成一個最大堆，然后將根節點（最大元素）與最后一個元素交換，然后把剩下的 n-1 元素再次生成最大堆，交換，生成...

總結

那么問題來了，到底這些算法寫的對不對，不然寫個測試腳本來試試：

// 兩種排序算法
var test = function(sort1, sort2){
  var arr1 = [], arr2 = [];
  // 隨機生成 100 個 1～100 隨機數
  function random_arr(a1, a2){
    var tmp;
    for(var i = 0; i < 100; i++){
      tmp = parseInt(Math.random()*100) + 1;
      a1.push(tmp);
      a2.push(tmp);
    }
  }

  var flag = true;
  for(var i = 0; i < 100; i++){
    random_arr(arr1, arr2);
    // 比較排序算法的結果
    if(sort1(arr1).toString() != sort2(arr2).toString()){
      flag = false;
      break;
    }
    arr1 = arr2 = [];
  }
  return flag ? "Ok!" : "Error!"
}

console.log(test(insert_sort, merge_sort)); //"Ok!"

如果已知插入排序是正確的情況下，就可以驗證歸并排序是否正確了。共勉！

參考

維基百科排序搜索
聊一聊排序算法
秒殺9種排序算法(JavaScript版)
排序圖解：js排序算法實現

歡迎來我的博客交流

云服務器 GPU云服務器排序算法圖解排序算法總結桶排序算法學習排序算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/81238.html

你不能錯過的前端面試題合集

摘要：收集的一些前端面試題從面試題發現不足，進而查漏補缺，比通過面試更難得及各大互聯網公司前端筆試面試題篇及各大互聯網公司前端筆試面試題篇面試題個和個經典面試題前端開發面試題如何面試前端工程師很重要個變態題解析如何通過餓了么面試輕收集的一些前端面試題從面試題發現不足，進而查漏補缺，比通過面試更難得 1 BAT及各大互聯網公司2014前端筆試面試題--Html,Css篇 2 BAT...

ninefive 2019-08-21 16:18 評論0 收藏0
你不能錯過的前端面試題合集

摘要：收集的一些前端面試題從面試題發現不足，進而查漏補缺，比通過面試更難得及各大互聯網公司前端筆試面試題篇及各大互聯網公司前端筆試面試題篇面試題個和個經典面試題前端開發面試題如何面試前端工程師很重要個變態題解析如何通過餓了么面試輕收集的一些前端面試題從面試題發現不足，進而查漏補缺，比通過面試更難得 1 BAT及各大互聯網公司2014前端筆試面試題--Html,Css篇 2 BAT...

darkbaby123 2019-07-30 14:38 評論0 收藏0
前端文檔收集

摘要：系列種優化頁面加載速度的方法隨筆分類中個最重要的技術點常用整理網頁性能管理詳解離線緩存簡介系列編寫高性能有趣的原生數組函數數據訪問性能優化方案實現的大排序算法一怪對象常用方法函數收集數組的操作面向對象和原型繼承中關鍵詞的優雅解釋淺談系列 H5系列 10種優化頁面加載速度的方法隨筆分類 - HTML5 HTML5中40個最重要的技術點常用meta整理網頁性能管理詳解 HTML5 ...

jsbintask 2019-08-21 12:05 評論0 收藏0
前端文檔收集

摘要：系列種優化頁面加載速度的方法隨筆分類中個最重要的技術點常用整理網頁性能管理詳解離線緩存簡介系列編寫高性能有趣的原生數組函數數據訪問性能優化方案實現的大排序算法一怪對象常用方法函數收集數組的操作面向對象和原型繼承中關鍵詞的優雅解釋淺談系列 H5系列 10種優化頁面加載速度的方法隨筆分類 - HTML5 HTML5中40個最重要的技術點常用meta整理網頁性能管理詳解 HTML5 ...

muddyway 2019-08-29 13:21 評論0 收藏0

發表評論

登陸后可評論

0條評論

FrozenMap

男|高級講師

我要關注我要私信

TA的文章

spinservers：圣何塞10Gbps帶寬服務器$109/月起,達拉斯10Gbps服務器$89/

閱讀 1349·2021-09-28 09:43
C語言指針+二維數組詳解（應付期末、考研的最強筆記，建議收藏）

閱讀 4115·2021-09-04 16:41
你所不知道的 CSS 負值技巧與細節

閱讀 1917·2019-08-30 15:44
「車來了公交線路規劃」小程序，實現公交出行服務信息精準可視化

閱讀 3728·2019-08-30 15:43
使用Excel消費C4C的OData service

閱讀 775·2019-08-30 14:21
學不動了，來點有趣的吧

閱讀 2037·2019-08-30 11:00
css3 漸變

閱讀 3319·2019-08-29 16:20
CSS相關文章

閱讀 1923·2019-08-29 14:21

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！

JavaScript 版各大排序算法

相關文章

你不能錯過的前端面試題合集

你不能錯過的前端面試題合集

前端文檔收集

前端文檔收集

發表評論

0條評論

FrozenMap

男|高級講師

TA的文章

spinservers：圣何塞10Gbps帶寬服務器$109/月起,達拉斯10Gbps服務器$89/

C語言指針+二維數組詳解（應付期末、考研的最強筆記，建議收藏）

你所不知道的 CSS 負值技巧與細節

「車來了公交線路規劃」小程序，實現公交出行服務信息精準可視化

使用Excel消費C4C的OData service

學不動了，來點有趣的吧

css3 漸變

CSS相關文章

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！

JavaScript 版各大排序算法

相關文章

發表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！