速排序概述

快速排序(Quiksort)是一种通过基准划分区块并不断交换左右项的排序方式，其采用了分治法，减少了交换的次数。平均算法复杂度：O(NlogN)。

步骤是：

1. 先找到一个基准点(pivot)，为了便于理解一般是位于数组中间的那一项。
2. 逐个循环数组将小于基准的项放左侧，将大于基准的数放右侧。一般通过交换的方式来实现。
3. 将基点左侧全部项和基点右侧全部项分别通过递归(或遍历)形式重复第1项，直到所有数组都交换完成。

快速排序执行过程分析

从上图可以看出：

1. 先找到基准项。比如是中间项(根据left与right之和除以2), 得到基准值arr[2] = 3。
2. 再将基准项左侧大于3的项挪到右侧，将右侧小于3的项挪至左侧。得到 [2,1,3,5,4]
3. 开始新的分区。基准项左侧2,1为新的分区，右侧5,4为新的分区。将它们分别按照1、2步骤进行处理。
4. 2,1位于数组的第0,1项,得到中间项0，基准值为2，交换后得到1,2
5. 5,4位于数组的第3,4项,中间项(3+4)/2取整得到3，基准值为5，交换后得到4,5
6. 全部分区都按照1，2步骤完成后，得到最后的排序结果

快速排序实现

1、递归新建数组版。无需交换，每个分区都是新数组。

这个版本最容易理解，先找准基准项(用中间项表示)，把小于基准项的全添加到左侧新数组，大于等于基准项的放在右侧新数组，然后分别递归调用左、右新数组，再重复第一步找基准项，再据此一分为二。直到把数组项拆分为一个个length为1的数组。最后自左往右将最小值与中间项和最大值连接起来。这里利用到JS语法中的concat，可以有效地连接数组。

这个版本好处是代码简单，非常容易理解，除了要注意基准项不要放入到left和right，而是concat到结果即可。但是带来的问题是要新建很多数组，所以这个方式并不是很优的方式。

2、标准递归版本。需要交换，无需新建数组。

这个版本好处是无需新建数组，而整个排序过程都是基于原数组的位置交换。其机制和排序过程与上一个方案基本类似(不同在于新方案的基准项可交换会，因此递归有时需要带上基准项)，直到把所有分区都比较过后就表示已经排序完成。

其排序过程为：

1. 先找到基准项，这里以中间项表示，pivot=3。left表示最左侧位置，i一开始取值left，right表示最右侧位置,j取值为j, 因此i = 0, j = 4。
2. 自左往右逐个查找大于基准项的数，同时自右往左逐个查找小于基准项的数，类似两边收拢朝中间查找，到基准项停止。当左侧遇到大的数，右侧遇到小的数字，将左右两项交换，同时i增1位，j减1位，缩小范围继续查找，直到将全部小的数移到左侧，大的数字移到右侧。
3. 上一趟交换完成之后，左侧全部小于基准项，右侧全部大于基准项。这时，将基准左侧第1位到基准项-1项放入递归按照步骤1、2进行交换排序，再将基准右侧第1项到最后项放入递归按照步骤1、2进行交换排序。在递归时，有时左侧或者右侧没有可交换的项，这时就与基准项进行了交换，那需要将基准项位置一并传入递归。
4. 分区递归完成后排序完成。

3、非递归版本。需要交换，无需新建数组，利用stack或queue遍历。

非递归版本基于标准递归版本，交换逻辑与排序规则完全一样。所不同的是，将递归改为栈或队列的循环。不同点是：

1. 首先在交换排序的外循环加入一个stack，将初始的left,right添加进去
2. 如果stack不为空，则将left与right取出，分别赋值给i和j。数组方法pop()表示从后开始取,shift()从前开始取。
3. 在之前递归调用处，分别用push成员来替换。也就是当需要递归时说明要继续交换循环，则给stack添加成员，让循环继续即可。中止条件是stack为空，也就是无需递归时结束。

总结

快速排序是一种相对巧妙的排序方式，相对选择、插入、冒泡来讲效率要高，也要稍微复杂一些。其交换过程也有点类似冒泡，但是不像冒泡两两逐个交换，而是根据基准值比较大小按需要来交换，然后递归分区排序，这样以来交换就减少了。但快排并不稳定，如果遇到已排过序或全一样的数字这种最坏情况那跟冒泡等一样了。

PS：请对比之前关于选择、插入、冒泡三种冒泡排序的文章。

择排序概述

选择排序(Selection Sort)是从待排序数列中取出最小(或最大)的1位，与第一个位置交换，再从待排序数列中找出最小的跟整个数列的第二个交换。以此类推遍历完待排序数列。平均算法复杂度：O(n^2)

步骤是：

1. 先建立两个循环，外循环用于逐个交换数据，内循环用来遍历找到最小(或最大)值。
2. 设第1项为最小值，在内循环中将其逐个与后项进行比较，如果遇到更小的值，则更新最小值，并记录下最小值的下标。
3. 在外循环中将第1项与最小值进行交换，然后以第2项作为最小值，再重复执行步骤2，直到遍历完全部待排序区间。

选择排序执行过程分析

例如数列： 4, 1, 3, 5, 2

从待排序区间中每次找到最小的项目，将其与第一项交换。

选择排序实现

• 标准实现

• 新建数组法与移除法，这种方式会多建立一个数组，但无需交换。

入排序概述

插入排序是将数组分为待排序和已排序两个区间。依次从待排序区间中取出一项，用该项跟已排序区间项逐个对比，通过位移来实现插入到对应位置的排序方式。插入排序平均时间复杂度是：O(n^2)

步骤是：

1. 先建立两个循环，外循环用于遍历待排序区间，内循环用来遍历已排序区间。
2. 从待排序中按顺序取出一项暂存起来，将该项自右往左与已排序项逐个对比，当遇到比自己大的项(表示升序)时，将该位置右移1位。
3. 再将待排序区间里右移后空出来的位置赋值为暂存项。此时已排序区间增加了一项，待排序区间减少了一项，继续第2步直到待排序遍历完成。

插入排序实现

插入排序有多种实现方式，这里介绍常见的3种：

1、通用实现方式，自左往右遍历待排序数组，再从当前的左侧位置开始自右往左循环已排序数组，再逐个比较和移动被比较项，最后将当前项填入到空缺位置上。

2、利用数组splice方法，类似打扑克牌，先拿出要排序的牌，然后找准位置插入。这种方式利用了原生API，减少了数组反复移动位置的操作。性能上之前差不多。

3、新建数组法与splice结合法，这种方式会多建立一个数组，也就会多占用一个空间，但理解起来最容易，也利用了JS语言的特性。

插入排序通俗说明

插入排序与冒泡、选择都是比较简单好懂的排序方式，性能上也差不多。插入排序通俗来讲就像打扑克牌排序，你抓了一手牌之后。假如是：2、1、5、3、4，你会：

1、先把牌分成两组，假定左侧第一张牌为一组(标识A，这时只有2)，其他牌为另外一组(标识B，包括1、5、3、4)。

2、从B组里面从左起选择第一张牌（位置空出等待填充），也就是1，拿这张牌与A组里面从右往左挨个对比，当遇到比这张牌还小时就在这个位置停留下来(如果A组全部比这张牌都大那就在A组最前面停留下来，如果A组里没有比这张牌大的就在当前位置停留)。

3、然后将A组里比这张牌(也就是1)大的牌逐个往右移动1位，原B组空出位置被填充，此时刚才停留的位置空出，将1这张牌插入在这里。这时候A组增加一个数字，变为：1、2，B组减少1个，变为：5、3、4。

4、移动指针，继续指向B组的第一个，也就是5。用5这张牌重复第二部，即拿5去跟A组自右往左逐个比较，然后插入到A组。此时A组：1、2、5，B组：3、4。

5、将B组里数字按照第二部重复操作，直到B组为空时整个循环结束。此时A组为：1、2、3、4、5。