首頁猿問 javascript中快速穩(wěn)定的排...

javascript中快速穩(wěn)定的排序算法實(shí)現(xiàn)

JavaScript 算法

忽然笑 2019-07-30 14:32:42

javascript中快速穩(wěn)定的排序算法實(shí)現(xiàn)我正在尋找一個(gè)大約200-300個(gè)對(duì)象的數(shù)組，對(duì)特定的鍵和給定的順序（asc / desc）進(jìn)行排序。結(jié)果的順序必須一致且穩(wěn)定。什么是最好的算法，你能提供一個(gè)在javascript中實(shí)現(xiàn)它的例子嗎？謝謝！

查看完整描述

3 回答

米脂

TA貢獻(xiàn)1836條經(jīng)驗(yàn) 獲得超3個(gè)贊

我知道這個(gè)問題已經(jīng)回答了一段時(shí)間，但我碰巧在我的剪貼板中有一個(gè)很好的穩(wěn)定合并排序?qū)崿F(xiàn)Array和jQuery，所以我將分享它，希望未來的一些搜索者可能會(huì)覺得它很有用。

它允許您像正常Array.sort實(shí)現(xiàn)一樣指定自己的比較函數(shù)。

履行

// Add stable merge sort to Array and jQuery prototypes// Note: We wrap it in a closure so it doesn't pollute the global//       namespace, but we don't put it in $(document).ready, since it's//       not dependent on the DOM(function() {

  // expose to Array and jQuery
  Array.prototype.mergeSort = jQuery.fn.mergeSort = mergeSort;

  function mergeSort(compare) {

    var length = this.length,
        middle = Math.floor(length / 2);

    if (!compare) {
      compare = function(left, right) {
        if (left < right)
          return -1;
        if (left == right)
          return 0;
        else
          return 1;
      };
    }

    if (length < 2)
      return this;

    return merge(
      this.slice(0, middle).mergeSort(compare),
      this.slice(middle, length).mergeSort(compare),
      compare    );
  }

  function merge(left, right, compare) {

    var result = [];

    while (left.length > 0 || right.length > 0) {
      if (left.length > 0 && right.length > 0) {
        if (compare(left[0], right[0]) <= 0) {
          result.push(left[0]);
          left = left.slice(1);
        }
        else {
          result.push(right[0]);
          right = right.slice(1);
        }
      }
      else if (left.length > 0) {
        result.push(left[0]);
        left = left.slice(1);
      }
      else if (right.length > 0) {
        result.push(right[0]);
        right = right.slice(1);
      }
    }
    return result;
  }})();

示例用法

var sorted = [
  'Finger',
  'Sandwich',
  'sandwich',
  '5 pork rinds',
  'a guy named Steve',
  'some noodles',
  'mops and brooms',
  'Potato Chip Brand? chips'].mergeSort(function(left, right) {
  lval = left.toLowerCase();
  rval = right.toLowerCase();

  console.log(lval, rval);
  if (lval < rval)
    return -1;
  else if (lval == rval)
    return 0;
  else
    return 1;});sorted == ["5 pork rinds", "a guy named Steve", "Finger", "mops and brooms", "Potato Chip Brand? chips", "Sandwich", "sandwich", "some noodles"];

反對(duì) 回復(fù) 2019-07-30