摘要:上一篇中已經介紹了幾個簡單的排序算法,這一篇文章我將繼續向大家介紹排序算法相關的內容,本篇的會介紹希爾排序快速排序歸并排序以及分治算法的思想,希望通過本文章能夠加深大家對排序算法的理解。
上一篇中已經介紹了幾個簡單的排序算法,這一篇文章我將繼續向大家介紹排序算法相關的內容,本篇的會介紹希爾排序、快速排序、歸并排序以及分治算法的思想,希望通過本文章能夠加深大家對排序算法的理解。
希爾排序希爾排序又叫縮小增量排序,希爾排序的主要思想是使數組中任意相隔h的元素都是有序的,h就是希爾增量,實現的希爾排序的方法就是:對相隔h的元素進行分組,對每組進行使用插入排序,使子序列變成有序序列,增量逐漸遞減一直到1為止,在例子中我將h增量設為array.length/2,遞減的過程就是不斷除以2,是不是被我的解釋弄的有點暈,讓我們先來看一個演示過程理解一下:
如圖所示,一共15個元素,增量就是15/2為7,第一輪的分組即為[2, 26, 48],[44, 26],[38, 2],[5, 46],[47, 4],[15, 19],[36, 50],然后進行插入排序,得到新的序列[ 3, 27, 2, 5, 4, 15, 36, 26, 44, 38, 46, 47, 19, 50, 48 ],然后在進行分組,增量為7/2為3:
第二輪分組[3, 5, 36, 2, 19],[44, 47, 26, 46, 50], [38, 15, 27, 4, 48],然后進行插入排序,得到序列[ 3, 4, 2, 5, 26, 15, 19, 27, 44, 36, 46, 47, 38, 50, 48 ],然后再進行分組,增量為3/2為1,再插入排序得到的就是一個有序序列了,最好讓我們來看具體的代碼實現:
function shellSort(arr) { var n = arr.length for (var gap = parseInt(n/2); gap > 0; gap=parseInt(gap/2)) { for (var i=gap; itemp) { arr[j+gap] = arr[j] j = j - gap } arr[j+gap] = temp } } console.log(arr) } shellSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])
其實希爾排序也不難,只要按照上面的分解圖示一步一步的理解去編寫,相信大家都能寫得出來,上面這種形式的增量設置就是二分的形式設置,然后插入排序,還有一種希爾排序的寫法就是自定義增量,然后子序列里的元素兩兩比較,來看具體代碼:
function shellSort(arr) { var n = arr.length, gap = 1 while (gap < n / 3) { gap = gap * 3 + 1 } for (gap; gap > 0; gap=parseInt(gap/3)) { for (var i=gap; i= 0; j-=gap) { if (arr[j] > arr[j+gap]) { var temp = arr[j+gap] arr[j+gap] = arr[j] arr[j] = temp } } } } console.log(arr) } shellSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])
希爾排序更高效的原因在于它權衡了子數組的規模和有序性,各個子數組都很短,排序之后的子數組都是部分有序的,因此在希爾排序的效率要比插入排序高。
分治法在介紹歸并排序和快速排序有必要先介紹一下分治法相關的內容,為什么呢?因為歸并排序和快速排序都是分治法的典型應用。
分治法的設計思路就是:將一個大問題分解成若干個規模嬌小的相同子問題,這些子問題互相獨立且與原問題形式相同,遞歸地解決這些子問題,然后將各個子問題的解合并得到原問題的解
分治法所能解決的問題一般有如下幾個特點:
把該問題縮小到一定規模就可以容易解決
該問題可以被分解為若干個規模較小的相同問題
利用該問題的子問題的解向上合并可以得到該問題的解
該問題分解出的子問題是相互獨立的
歸并排序歸并排序就是分治法的典型應用之一,歸并排序的實現有兩種,一種是自頂向下的歸并排序,另一種就是自底向上的歸并排序。
自頂向下的歸并排序向來看第一種,自頂向下的歸并排序的實現思路是不斷二分,然后對二分后的最小序列分別進行排序后,再將排序后的結果向上合并得到最終的有序數組,讓我們先通過一個樹結構來理解歸并排序的過程:
從圖中可以看到將一個數組0-14的元素不斷二分,分到最后一層,然后互相比較,得到新的有序序列,然后向上合并,在進行比較,不斷反復,合并出最終的有序序列,這就是自頂向下的歸并排序的思路,通過這個思路你是否能自己寫出排序的方法呢?
好了,接下來就讓我們看看具體的代碼實現:
function sort(arr) { var n = arr.length if (n < 2) return arr var mid = Math.ceil(n / 2) var left = arr.slice(0, mid) var right = arr.slice(mid) return merge(sort(left), sort(right)); } function merge(left, right){ var result = [] while (left.length && right.length) { if (left[0] < right[0]) { result.push(left.shift()) } else { result.push(right.shift()) } } while (left.length) { result.push(left.shift()) } while (right.length) { result.push(right.shift()) } return result; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(sort(arr))
代碼實現是不是很容易理解呢?相信大家經過仔細的思考過后都能看得懂,為了方便更好的理解,來看一下動圖的排序過程:
自底向上的歸并排序思路是將長度為n的數組看成n個長度為1的數組,然后兩兩向上歸并排序,得到新的數組,不斷向上歸并排序,直到得到長度為n的數組,這樣的排序比之前自頂向下的排序代碼要少,下面來看具體的代碼實現:
function merge(arr, start, mid, end){ var i = start, j= mid + 1, copy = [] for (var k = start; k <= end; k++) { copy[k] = arr[k] } for (var k = start; k <= end; k++) { if (i > mid) { // 左邊取完取右邊的元素 arr[k] = copy[j] j++ } else if (j > end) { // 右邊取完取左邊的元素 arr[k] = copy[i] i++ } else if (copy[j] < copy[i]) { // 右邊的元素小于左邊的元素,取右邊的元素 arr[k] = copy[j] j++ } else { // 左邊的元素小于右邊的元素,取左邊的元素 arr[k] = copy[i] i++ } } console.log(arr) } function sort(arr) { var n = arr.length for (var i = 1; i < n; i = i + i) { // i子數組的大小 for (var j = 0; j < n - i; j = j + i + i) { // j數組的索引 var start = j var end = Math.min(j + i + i - 1, n-1) var mid = parseInt((start + end) / 2) merge(arr, start, mid, end) } } } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; sort(arr)
為了方便理解,已經在代碼中加了必要的注釋,可能這段代碼比之前的要難理解一些,需要大家耐心多花一些時間去理解
快速排序快速排序也是一種分治的排序算法,由于它實現簡單并且效率比一般的排序算法高,因此,它的應用范圍非常廣泛,接下來讓我們來看快速排序的排序過程:
將數組的第一個元素做為基準,從數組末尾開始找比基準小的數,找到就停下來,記下索引j,然后從基準右邊開始找比基準大的數找到停下來,記下索引i,然后交換i和j上的元素,得到數組:
然后繼續從44的位置開始找比基準3小的一直移動到2,此時索引i和索引j相等,將基準3和i、j對應的值交換位置得到:
此時基準數3前面的元素都是比它小的數,后面元素都是比它大的數,然后從基準數前后拆成兩個數組,在遞歸執行前面同樣的操作。
看來上面的排序過程,你是不是有代碼的實現了呢?可以先試著寫一下實現的代碼,這樣更容易理解,接下來就讓我來看一下具體代碼:
function sort(arr, left, right) { var temp = arr[left],i = left, j = right, t; if (left < right) { while (i != j) { while (arr[j] >= temp && i < j) { j-- } while (arr[i] <= temp && i < j) { i++ } if (i < j) { t = arr[i] arr[i] = arr[j] arr[j] = t } } arr[left] = arr[i] arr[i] = temp sort(arr, left, i - 1) sort(arr, i + 1, right) } return arr } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(sort(arr, 0, arr.length - 1))
看了代碼之后是不是覺得并不難呢?這種快速排序的實現其實有一個問題不知道大家注意到沒有,當數組中有多個重復元素的時候,重復的元素只要排了一個就不需要重復排了,但是這中快速排序的實現并沒有考慮這種情況,即便重復的元素還是會執行排序,因此有人提出了更優的快速排序方法“三向切分的快速排序”,讓我們先來看代碼實現有什么不同:
function sort(arr, left, right) { var temp = arr[left],i = left, j = right,k = left + 1, t; if (left < right) { while (k <= j) { if (arr[k] < temp) { t = arr[k] arr[k] = arr[i] arr[i] = t i++; k++; } else if (arr[k] > temp) { t = arr[k] arr[k] = arr[j] arr[j] = t j--; } else { k++; } } sort(arr, left, i - 1) sort(arr, j + 1, right) } return arr } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48,44,38]; console.log(sort(arr, 0, arr.length - 1))
總體思路和之前的一樣保證基準值前面的比它小后面的比它大,唯一不同的地方就是用了一個臨時下標k去作比較,把小的丟到基準值前面,大的值就和末尾的值交換,得到新值再與基準值比較,當與基準值相等的時候,就只需要將臨時下標的值+1而不需要排序了
總結這篇文章詳細介紹了希爾排序、歸并排序、快速排序這三種排序的思想和實現方式,希望大家看完之后都能自己去多實踐,多思考,算法還是需要自己多動手,否則光看作用不大。
如果有錯誤或不嚴謹的地方,歡迎批評指正,如果喜歡,歡迎點贊收藏
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/100955.html
摘要:如果有錯誤或不嚴謹的地方,歡迎批評指正,如果喜歡,歡迎點贊收藏 算法對大多數前端工程師來說都是一個比較不愿意提及的話題,因為學了,感覺在工作中直接應用的場景不多,不學,大廠面試必考算法,總結來說就是:沒有學習算法的源動力,為面試學習算法總不會令人動力去學習,沒有動力想要學好算法自然也很難,對我來說,學習算法的動力就是希望寫出更高效率的代碼,更好的理解各種前端框架的設計思路,因此,后面會...
摘要:模型優先隊列是允許至少下列兩種操作的數據結構以及找出返回并刪除優先隊列中最小的元素。左式堆也是二叉樹,左式堆和二叉堆的唯一區別是左式堆不是理想平衡,而實際上趨向于非常不平衡。事實上,沿左式堆的右路徑是該堆中的最短路徑。 6.1 模型 優先隊列是允許至少下列兩種操作的數據結構:insert 以及 deleteMin(找出、返回并刪除優先隊列中最小的元素)。 insert 操作等價于 en...
閱讀 3091·2023-04-25 15:44
閱讀 1876·2019-08-30 13:11
閱讀 2830·2019-08-30 11:11
閱讀 3004·2019-08-29 17:21
閱讀 1306·2019-08-29 15:38
閱讀 898·2019-08-29 12:49
閱讀 1793·2019-08-28 18:19
閱讀 3222·2019-08-26 14:01