JavaScript 排序算法圖解（JavaScript sorting algorithms）

h9911 發布于2019-08-21 12:04 / 2737人閱讀

摘要：基礎構造函數以下幾種排序算法做為方法放在構造函數里。代碼圖解選擇排序選擇排序算法是一種原址比較排序算法。它的性能通常比其他的復雜度為的排序算法要好。代碼劃分過程圖解排序沒有定義用哪個排序算法，所以瀏覽器廠商可以自行去實現算法。

基礎構造函數

以下幾種排序算法做為方法放在構造函數里。

function ArrayList () {
  var array = [];

  // 交換位置
  var swap = function (index1, index2) {
    var aux = array[index1];
    array[index1] = array[index2];
    array[index2] = aux;
  }

  this.insert = function (item) {
    array.push(item);
  };

  this.toString = function () {
    return array.join();
  };

  this.val = function () {
    return array;
  }

  // 冒泡排序
  this.bubbleSort = function () {
    //etc
  }
}

1. 冒泡排序

冒泡排序比較任何兩個相鄰的項，如果第一個比第二個大，則交換它們。
復雜度 O(n^2)。

代碼

this.bubbleSort = function () {
  console.time("Bubble Sort");
  var length = array.length;
  for (var i = 0; i < length; i++) {
    for (var j = 0; j < length - 1 - i; j++) {
      if (array[j] > array[j+1]) {
        swap(j, j + 1);
      }
    }
  }
  console.timeEnd("Bubble Sort");
}

圖解

2. 選擇排序

選擇排序算法是一種原址比較排序算法。選擇排序大致的思路是找到數據結構中的最小值并將其放置在第一位，接著找到第二小的值并將其放在第二位，以此類推。

復雜度：O(n^2)。

代碼

this.selectionSort = function () {
  console.time("selectionSort");
  var length = array.length,
      indexMin;

  for (var i = 0; i < length - 1; i++) {
    indexMin = i;
    for (var j = i; j < length; j++) {
      if (array[indexMin] > array[j]) {
        indexMin = j;
      }
    }

    if (i !== indexMin) {
      swap(i, indexMin);
    }
  }
  console.timeEnd("selectionSort");
}

圖解

3. 插入排序

插入排序每次排一個數組項，以此方式構建最后的排序數組。假定第一項已經排序了，接著，它和第二項進行比較，第二項是應該待在原位還是插到第一項之前呢？這樣，頭兩項就已正確排序，接著和第三項比較（它是該插入到第一、第二還是第三的位置呢？），以此類推。

排序小型數組時，此算法比選擇排序和冒泡排序性能要好。

代碼

this.insertionSort = function () {
  console.time("insertionSort");
  var length = array.length,
      j, temp;

  for (var i = 1; i < length; i++) {
    j = i;
    temp = array[i];
    while (j > 0 && array[j-1] > temp) {
      array[j] = array[j-1];
      j--;
    }
    array[j] = temp;
  }
  console.timeEnd("insertionSort");
}

圖解

4. 歸并排序

歸并排序是一種分治算法。其思想是將原始數組切分成較小的數組，直到每個小數組只有一個位置，接著將小數組歸并成較大的數組，直到最后只有一個排序完畢的大數組。

復雜度：O(n log^n)。

代碼

this.mergeSort = function () {
  console.time("mergeSort");
  array = mergeSortRec(array);
  console.timeEnd("mergeSort");
}
var mergeSortRec  = function (array) {
  var length = array.length;
  if (length === 1) {
    return array;
  }

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

  return merge(mergeSortRec(left), mergeSortRec(right));
}
var merge = function (left, right) {
  var result = [],
      il = 0,
      ir = 0;

  while (il < left.length && ir < right.length) {
    if (left[il] < right[ir]) {
      result.push(left[il++]);
    } else {
      result.push(right[ir++]);
    }
  }

  while (il < left.length) {
    result.push(left[il++]);
  }

  while (ir < right.length) {
    result.push(right[ir++]);
  }

  return result;
}

圖解

5. 快速排序

歸并排序一樣，快速排序也使用分治的方法，將原始數組分為較小的數組（但它沒有像歸并排序那樣將它們分割開）。

它的性能通常比其他的復雜度為O(n log^n)的排序算法要好。

復雜度：O(n log^n)。

代碼

this.quickSort = function () {
  console.time("quickSort");
  quick(array, 0, array.length - 1);
  console.timeEnd("quickSort");
}

var quick = function (array, left, right) {
  var index;
  if (array.length > 1) {
    index = partition(array, left, right);

    if (left < index - 1) {
      quick(array, left, index - 1);
    }

    if (index < right) {
      quick(array, index, right);
    }
  }
};

// 劃分過程
var partition = function (array, left, right) {
  var pivot = array[Math.floor((right + left) / 2)],
      i = left,
      j = right;

  while (i < j) {
    while (array[i] < pivot) {
      i++;
    }

    while (array[j] > pivot) {
      j--;
    }

    if (i <= j) {
      swapQuickSort(array, i, j);
      i++;
      j--;
    }
  }
  return i;
}

var swapQuickSort = function (array, index1, index2) {
  var aux = array[index1];
  array[index1] = array[index2];
  array[index2] = aux;
}

圖解

6. ECMAScript 排序

ECMAScript沒有定義用哪個排序算法，所以瀏覽器廠商可以自行去實現算法。例如，Mozilla Firefox使用歸并排序作為Array.prototype.sort的實現，而Chrome使用了一個快速排序（下面我們會學習的）的變體。

this.esSort = function () {
  console.time("esSort");
  var tempArray = [];
  tempArray = array.sort(function (a, b) {
    return a - b;
  });
  console.timeEnd("esSort");
  return tempArray;
}

性能測試 環境

OS：WIN10 64位

瀏覽器：Google Chrome 60.0.3112.78

代碼

/**
* 創建隨機數組
* @param  {[type]} size [description]
* @return {[type]}      [description]
*/
function createNonSortedArray (size) {
  var array = new ArrayList();
  for (var i = size; i > 0; i--) {
    var tempNum = Math.random() * i >>> 0;
    array.insert(tempNum);
  }
  return array;
}

// 冒泡排序
(function () {
  var array = createNonSortedArray(500);
  array.bubbleSort(); // Bubble Sort: 2.625ms
  console.log(array.val());
}());


// 選擇排序
(function () {
  var array = createNonSortedArray(500);
  array.selectionSort(); // selectionSort: 1.986083984375ms
  console.log(array.val());
}());

// 插入排序
(function () {
  var array = createNonSortedArray(500);
  array.insertionSort(); // insertionSort: 1.825927734375ms
  console.log(array.val());
}());

// 歸并排序
(function () {
  var array = createNonSortedArray(500);
  array.mergeSort(); // mergeSort: 0.76416015625ms
  console.log(array.val());
}());


// 快速排序
(function () {
  var array = createNonSortedArray(500);
  array.quickSort(); // quickSort: 0.39111328125ms
  console.log(array.val());
}());


// ES排序
(function () {
  var array = createNonSortedArray(500);
  array.esSort(); // esSort: 0.34130859375ms
  console.log(array.val());
}());

由此可見，一般情況我們只需要使用JavaScript 提供的 Array.prototype.sort() 方法即可，瀏覽器（或宿主環境）會在底層采用最優算法幫我們實現排序。

來源/參考

《學習 javascript 數據結構》

About the #sorting-algorithms series

https://github.com/benoitvallon/computer-science-in-javascript/tree/master/sorting-algorithms-in-javascript

轉載請注明出處： http://blog.givebest.cn/javascript/2017/08/02/javascript-sorting-algorithms.html

GPU云服務器云服務器 sort排序算法排序算法圖解 javascript排序 javascript隨機排序

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

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

幾種常見排序算法

摘要：本文介紹幾種常見排序算法選擇排序，插入排序，希爾排序，歸并排序，快速排序，堆排序，對算法的思路性質特點具體步驟實現以及圖解進行了全面的說明。最后對幾種排序算法進行了比較和總結。本文介紹幾種常見排序算法（選擇排序，插入排序，希爾排序，歸并排序，快速排序，堆排序），對算法的思路、性質、特點、具體步驟、java實現以及trace圖解進行了全面的說明。最后對幾種排序算法進行了比較和總結。寫...

ChristmasBoy 2019-08-14 15:37 評論0 收藏0
深入淺出 JavaScript 的 Array.prototype.sort 排序算法

摘要：快速排序是不穩定的排序算法。瀏覽器的實現不同有什么影響排序算法不穩定有什么影響舉個例子某市的機動車牌照拍賣系統，最終中標的規則為按價格進行倒排序相同價格則按照競標順位即價格提交時間進行正排序。本文要解決的問題 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一種直觀的方式展示 Array.prototype.sort 的時間復雜度，看看它有多快？ 3、...

itvincent 2019-08-21 11:55 評論0 收藏0
數據結構與算法:常見排序算法

摘要：這是一個簡單的遞歸函數，你可以使用它來生成數列中指定序號的數值這個函數的問題在于它的執行效率非常低有太多值在遞歸調用中被重新計算。本章內容銜接上一章　數據結構與算法：二分查找內容提要兩種基本數據結構：數組常見操作: 數組降維、數組去重鏈表遞歸：遞歸是很多算法都使用的一種編程方法　　- 如何將問題分成基線條件和遞歸條件　　- 分而治之策略解決棘手問題 ...

wuyumin 2019-07-30 15:33 評論0 收藏0
數據結構與算法:常見排序算法

摘要：這是一個簡單的遞歸函數，你可以使用它來生成數列中指定序號的數值這個函數的問題在于它的執行效率非常低有太多值在遞歸調用中被重新計算。本章內容銜接上一章　數據結構與算法：二分查找內容提要兩種基本數據結構：數組常見操作: 數組降維、數組去重鏈表遞歸：遞歸是很多算法都使用的一種編程方法　　- 如何將問題分成基線條件和遞歸條件　　- 分而治之策略解決棘手問題 ...

Carson 2019-08-26 11:32 評論0 收藏0
JavaScript 版各大排序算法

摘要：推薦一下，，這里還有個可視化的排序博客，各大排序算法的實現都栩栩如生。堆排序堆排序是指利用堆這種數據結構所設計的一種排序算法。共勉參考維基百科排序搜索聊一聊排序算法秒殺種排序算法版排序圖解排序算法實現歡迎來我的博客交流最近看到了很多公司都在準備明年的實習校招，雖然離三月份還有一段時間，感覺已經可以準備了。在網上看了一些排序算法和數組去重操作，感覺都寫的很好，心血來潮，也來寫一寫。 s...

FrozenMap 2019-08-20 13:47 評論0 收藏0