JavaScript快速排序遞歸版與非遞歸版實現(xiàn)

速排序概述

快速排序(Quiksort)是一種通過基準(zhǔn)劃分區(qū)塊并不斷交換左右項的排序方式，其采用了分治法，減少了交換的次數(shù)。平均算法復(fù)雜度：O(NlogN)。

步驟是：

先找到一個基準(zhǔn)點(pivot)，為了便于理解一般是位于數(shù)組中間的那一項。
逐個循環(huán)數(shù)組將小于基準(zhǔn)的項放左側(cè)，將大于基準(zhǔn)的數(shù)放右側(cè)。一般通過交換的方式來實現(xiàn)。
將基點左側(cè)全部項和基點右側(cè)全部項分別通過遞歸(或遍歷)形式重復(fù)第1項，直到所有數(shù)組都交換完成。

快速排序執(zhí)行過程分析

圖1 快速排序執(zhí)行過程

從上圖可以看出：

先找到基準(zhǔn)項。比如是中間項(根據(jù)left與right之和除以2), 得到基準(zhǔn)值arr[2] = 3。
再將基準(zhǔn)項左側(cè)大于3的項挪到右側(cè)，將右側(cè)小于3的項挪至左側(cè)。得到 [2,1,3,5,4]
開始新的分區(qū)。基準(zhǔn)項左側(cè)2,1為新的分區(qū)，右側(cè)5,4為新的分區(qū)。將它們分別按照1、2步驟進行處理。
2,1位于數(shù)組的第0,1項,得到中間項0，基準(zhǔn)值為2，交換后得到1,2
5,4位于數(shù)組的第3,4項,中間項(3+4)/2取整得到3，基準(zhǔn)值為5，交換后得到4,5
全部分區(qū)都按照1，2步驟完成后，得到最后的排序結(jié)果

快速排序?qū)崿F(xiàn)

1、遞歸新建數(shù)組版。無需交換，每個分區(qū)都是新數(shù)組。

圖2 快速排序遞歸新建數(shù)組版

這個版本最容易理解，先找準(zhǔn)基準(zhǔn)項(用中間項表示)，把小于基準(zhǔn)項的全添加到左側(cè)新數(shù)組，大于等于基準(zhǔn)項的放在右側(cè)新數(shù)組，然后分別遞歸調(diào)用左、右新數(shù)組，再重復(fù)第一步找基準(zhǔn)項，再據(jù)此一分為二。直到把數(shù)組項拆分為一個個length為1的數(shù)組。最后自左往右將最小值與中間項和最大值連接起來。這里利用到JS語法中的concat，可以有效地連接數(shù)組。

這個版本好處是代碼簡單，非常容易理解，除了要注意基準(zhǔn)項不要放入到left和right，而是concat到結(jié)果即可。但是帶來的問題是要新建很多數(shù)組，所以這個方式并不是很優(yōu)的方式。

2、標(biāo)準(zhǔn)遞歸版本。需要交換，無需新建數(shù)組。

圖3 標(biāo)準(zhǔn)遞歸版本

圖4 標(biāo)準(zhǔn)遞歸版本執(zhí)行結(jié)果

這個版本好處是無需新建數(shù)組，而整個排序過程都是基于原數(shù)組的位置交換。其機制和排序過程與上一個方案基本類似(不同在于新方案的基準(zhǔn)項可交換會，因此遞歸有時需要帶上基準(zhǔn)項)，直到把所有分區(qū)都比較過后就表示已經(jīng)排序完成。

其排序過程為：

先找到基準(zhǔn)項，這里以中間項表示，pivot=3。left表示最左側(cè)位置，i一開始取值left，right表示最右側(cè)位置,j取值為j, 因此i = 0, j = 4。
自左往右逐個查找大于基準(zhǔn)項的數(shù)，同時自右往左逐個查找小于基準(zhǔn)項的數(shù)，類似兩邊收攏朝中間查找，到基準(zhǔn)項停止。當(dāng)左側(cè)遇到大的數(shù)，右側(cè)遇到小的數(shù)字，將左右兩項交換，同時i增1位，j減1位，縮小范圍繼續(xù)查找，直到將全部小的數(shù)移到左側(cè)，大的數(shù)字移到右側(cè)。
上一趟交換完成之后，左側(cè)全部小于基準(zhǔn)項，右側(cè)全部大于基準(zhǔn)項。這時，將基準(zhǔn)左側(cè)第1位到基準(zhǔn)項-1項放入遞歸按照步驟1、2進行交換排序，再將基準(zhǔn)右側(cè)第1項到最后項放入遞歸按照步驟1、2進行交換排序。在遞歸時，有時左側(cè)或者右側(cè)沒有可交換的項，這時就與基準(zhǔn)項進行了交換，那需要將基準(zhǔn)項位置一并傳入遞歸。
分區(qū)遞歸完成后排序完成。

3、非遞歸版本。需要交換，無需新建數(shù)組，利用stack或queue遍歷。

圖5 快速排序非遞歸版本

非遞歸版本基于標(biāo)準(zhǔn)遞歸版本，交換邏輯與排序規(guī)則完全一樣。所不同的是，將遞歸改為棧或隊列的循環(huán)。不同點是：

首先在交換排序的外循環(huán)加入一個stack，將初始的left,right添加進去
如果stack不為空，則將left與right取出，分別賦值給i和j。數(shù)組方法pop()表示從后開始取,shift()從前開始取。
在之前遞歸調(diào)用處，分別用push成員來替換。也就是當(dāng)需要遞歸時說明要繼續(xù)交換循環(huán)，則給stack添加成員，讓循環(huán)繼續(xù)即可。中止條件是stack為空，也就是無需遞歸時結(jié)束。

總結(jié)

快速排序是一種相對巧妙的排序方式，相對選擇、插入、冒泡來講效率要高，也要稍微復(fù)雜一些。其交換過程也有點類似冒泡，但是不像冒泡兩兩逐個交換，而是根據(jù)基準(zhǔn)值比較大小按需要來交換，然后遞歸分區(qū)排序，這樣以來交換就減少了。但快排并不穩(wěn)定，如果遇到已排過序或全一樣的數(shù)字這種最壞情況那跟冒泡等一樣了。

PS：請對比之前關(guān)于選擇、插入、冒泡三種冒泡排序的文章。

擇排序概述

選擇排序(Selection Sort)是從待排序數(shù)列中取出最小(或最大)的1位，與第一個位置交換，再從待排序數(shù)列中找出最小的跟整個數(shù)列的第二個交換。以此類推遍歷完待排序數(shù)列。平均算法復(fù)雜度：O(n^2)

步驟是：

先建立兩個循環(huán)，外循環(huán)用于逐個交換數(shù)據(jù)，內(nèi)循環(huán)用來遍歷找到最小(或最大)值。
設(shè)第1項為最小值，在內(nèi)循環(huán)中將其逐個與后項進行比較，如果遇到更小的值，則更新最小值，并記錄下最小值的下標(biāo)。
在外循環(huán)中將第1項與最小值進行交換，然后以第2項作為最小值，再重復(fù)執(zhí)行步驟2，直到遍歷完全部待排序區(qū)間。

選擇排序執(zhí)行過程分析

例如數(shù)列： 4, 1, 3, 5, 2

從待排序區(qū)間中每次找到最小的項目，將其與第一項交換。

選擇排序過程

選擇排序?qū)崿F(xiàn)

標(biāo)準(zhǔn)實現(xiàn)

選擇排序的標(biāo)準(zhǔn)實現(xiàn)

新建數(shù)組法與移除法，這種方式會多建立一個數(shù)組，但無需交換。

選擇排序新建數(shù)組

入排序概述

插入排序是將數(shù)組分為待排序和已排序兩個區(qū)間。依次從待排序區(qū)間中取出一項，用該項跟已排序區(qū)間項逐個對比，通過位移來實現(xiàn)插入到對應(yīng)位置的排序方式。插入排序平均時間復(fù)雜度是：O(n^2)

步驟是：

先建立兩個循環(huán)，外循環(huán)用于遍歷待排序區(qū)間，內(nèi)循環(huán)用來遍歷已排序區(qū)間。
從待排序中按順序取出一項暫存起來，將該項自右往左與已排序項逐個對比，當(dāng)遇到比自己大的項(表示升序)時，將該位置右移1位。
再將待排序區(qū)間里右移后空出來的位置賦值為暫存項。此時已排序區(qū)間增加了一項，待排序區(qū)間減少了一項，繼續(xù)第2步直到待排序遍歷完成。

插入排序?qū)崿F(xiàn)

插入排序有多種實現(xiàn)方式，這里介紹常見的3種：

1、通用實現(xiàn)方式，自左往右遍歷待排序數(shù)組，再從當(dāng)前的左側(cè)位置開始自右往左循環(huán)已排序數(shù)組，再逐個比較和移動被比較項，最后將當(dāng)前項填入到空缺位置上。

2、利用數(shù)組splice方法，類似打撲克牌，先拿出要排序的牌，然后找準(zhǔn)位置插入。這種方式利用了原生API，減少了數(shù)組反復(fù)移動位置的操作。性能上之前差不多。

3、新建數(shù)組法與splice結(jié)合法，這種方式會多建立一個數(shù)組，也就會多占用一個空間，但理解起來最容易，也利用了JS語言的特性。

插入排序通俗說明

插入排序與冒泡、選擇都是比較簡單好懂的排序方式，性能上也差不多。插入排序通俗來講就像打撲克牌排序，你抓了一手牌之后。假如是：2、1、5、3、4，你會：

1、先把牌分成兩組，假定左側(cè)第一張牌為一組(標(biāo)識A，這時只有2)，其他牌為另外一組(標(biāo)識B，包括1、5、3、4)。

2、從B組里面從左起選擇第一張牌（位置空出等待填充），也就是1，拿這張牌與A組里面從右往左挨個對比，當(dāng)遇到比這張牌還小時就在這個位置停留下來(如果A組全部比這張牌都大那就在A組最前面停留下來，如果A組里沒有比這張牌大的就在當(dāng)前位置停留)。

3、然后將A組里比這張牌(也就是1)大的牌逐個往右移動1位，原B組空出位置被填充，此時剛才停留的位置空出，將1這張牌插入在這里。這時候A組增加一個數(shù)字，變?yōu)椋?、2，B組減少1個，變?yōu)椋?、3、4。

4、移動指針，繼續(xù)指向B組的第一個，也就是5。用5這張牌重復(fù)第二部，即拿5去跟A組自右往左逐個比較，然后插入到A組。此時A組：1、2、5，B組：3、4。

5、將B組里數(shù)字按照第二部重復(fù)操作，直到B組為空時整個循環(huán)結(jié)束。此時A組為：1、2、3、4、5。

在線咨詢

上一篇：HTML表單及其Input輸入類型
下一篇：html教程入門的a標(biāo)簽使用方法，幫你理清邏輯，入門就是快

您的項目需求

*請認真填寫需求信息，我們會在24小時內(nèi)與您取得聯(lián)系。

整合營銷服務(wù)商