你需要知道的算法之排序算法

0 - 前言

实际生活中我们需要对很多数据进行处理，排序就是其中之一。而面试的时候一些排序算法、设计模式也是很多面试官的青睐，所以我们更需要理解这些常用的排序算法的思路（实现原理），排序的代码就不在文章内贴出来了（想看的各位请点相应的链接）。

Talk is cheap, show me the code.

1 - 测试数组数据生成

本文使用100个0~99的不重复的随机数组成的数组：

function notInArrNum(arr){
  var num = Math.floor(Math.random()*100);
  // 生成一个随机数
  // 如果存在于数组中 -> 递归调用
  // 否则将这个随机数返回
  if(arr.indexOf(num) != -1){
    num = notInArrNum(arr);
  } else {
    return num;
  }
}
// 生成随机数数组
function randomArr() {
  var count = 0;
  var arr = [];
  while(count < 100) {
    var a = notInArrNum(arr);
    arr.push(a);
    count++;
  }
  return arr;
}

2 - 快速排序

算法思路：

1. 从数组中去一个基准值
2. 将小于基准值的放在一个数组，大于放入另一个数组（相同的可以放在任意一侧）
3. 重复地进行第2步操作（递归）

效果图:

图上的灰色矩形代表着正在进行步骤2操作的区域，与深蓝色水平线持平的黑块所在的就是基准值。

快速排序的具体代码劳烦各位移步此处

复杂度：

一般情况下复杂度为O(nlogn)，最糟糕情况为O(n^2)

3 - 冒泡排序

算法思路：

比较相邻的两个数，如果前者比后者大，则将它们的位置互换。对所有元素持续递归。

效果图：

冒泡排序的具体代码劳烦各位移步此处

复杂度：

一般情况下的复杂度和最糟糕的复杂度都为O(n^2)

4 - 插入排序

算法思路：

1. 将第1个元素认为已排序
2. 取下一个元素，在已排序了的数列里面从后向前扫描
3. 如果在已排序数列中正在比较的这个元素大于从未排序数列中取出的元素，则比较已排序中的下一个元素
4. 重复第3步操作，如果找到已排序的元素小于或等于取出的元素的位置
5. 将新元素插入到该位置
6. 重复第2步操作

效果图：

暂无

插入排序的具体代码劳烦各位移步此处

复杂度：

同冒泡排序

5 - 选择排序

算法思路：

首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾，递归执行该操作。

效果图：

选择排序的具体代码劳烦各位移步此处

复杂度：

一般情况下和最糟糕情况的复杂度都为n^2

6 - 结语

其实这四个排序算法都是蛮简单的，不过之前都没有怎么去理解它们。另外还有一些在这些算法的基础上进行优化的排序算法例如shell排序、堆排序等等，有兴趣的各位也可以看看。

之后的算法系列可能是Codewars上的，也有可能是经常用上的。另外希望大家多多批评指正，Thanks！

原文地址：点击此处