速排序概述

快速排序(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。