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

h9911 发布于2019-08-21 12:04 / 2639人阅读

摘要：基础构造函数以下几种排序算法做为方法放在构造函数里。代码图解选择排序选择排序算法是一种原址比较排序算法。它的性能通常比其他的复杂度为的排序算法要好。代码划分过程图解排序没有定义用哪个排序算法，所以浏览器厂商可以自行去实现算法。

基础构造函数

以下几种排序算法做为方法放在构造函数里。

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

私有云 idc机房托管 sort排序算法排序算法图解 javascript排序 javascript随机排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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