整合營銷服務商

          電腦端+手機端+微信端=數據同步管理

          免費咨詢熱線:

          JavaScript快速排序遞歸版與非遞歸版實現

          速排序概述

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

          步驟是:

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

          快速排序執行過程分析

          圖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、遞歸新建數組版。無需交換,每個分區都是新數組。

          圖2 快速排序遞歸新建數組版

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

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

          2、標準遞歸版本。需要交換,無需新建數組。

          圖3 標準遞歸版本

          圖4 標準遞歸版本執行結果

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

          其排序過程為:

          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遍歷。

          圖5 快速排序非遞歸版本

          非遞歸版本基于標準遞歸版本,交換邏輯與排序規則完全一樣。所不同的是,將遞歸改為棧或隊列的循環。不同點是:

          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。


          主站蜘蛛池模板: 亚洲AV无码一区二区三区人| 国精产品一区一区三区MBA下载| 精品一区狼人国产在线| 成人精品一区二区激情| 在线观看国产一区亚洲bd| 视频一区二区三区在线观看| 日韩美女在线观看一区| 国产精品区AV一区二区| 亚洲无线码在线一区观看 | 无码人妻一区二区三区在线 | 无码aⅴ精品一区二区三区浪潮 | 九九久久99综合一区二区| 亚洲av成人一区二区三区| 国产福利电影一区二区三区久久久久成人精品综合 | 无码日韩人妻av一区免费| 亚洲日韩国产欧美一区二区三区| 中文字幕一区日韩精品| 精品3d动漫视频一区在线观看| 国产日韩综合一区二区性色AV| 夜夜爽一区二区三区精品| 久久久久人妻一区二区三区vr| 亚洲愉拍一区二区三区| 国产精品亚洲高清一区二区| 精品无码人妻一区二区免费蜜桃 | 日韩av片无码一区二区三区不卡| 日本成人一区二区| 99国产精品一区二区| 春暖花开亚洲性无区一区二区 | 亚洲一区二区三区四区视频 | 亚洲日韩一区二区三区| 久久人妻内射无码一区三区 | 亚洲一区二区三区日本久久九| 国产成人一区二区三区精品久久| 亚洲一区二区三区乱码在线欧洲| 欧洲精品无码一区二区三区在线播放| 人妻内射一区二区在线视频| 亚洲一区二区三区精品视频| 日韩电影一区二区三区| 骚片AV蜜桃精品一区| 蜜臀Av午夜一区二区三区| 91视频国产一区|