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

速排序概述

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

步驟是：

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

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

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

從上圖可以看出：

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

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

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

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

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

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

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

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

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

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

其排序過程為：

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

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

圖5 快速排序非遞歸版本

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

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

總結(jié)

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

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

擇排序概述

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

步驟是：

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

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

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

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

選擇排序過程

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

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

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

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

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

入排序概述

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

步驟是：

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

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

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

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

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

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

插入排序通俗說明

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

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

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

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

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

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

在線咨詢

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

您的項(xiàng)目需求

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

整合營銷服務(wù)商