DIV CSS 佈局教程網

JavaScript 實現 in-place 原地快速排序
編輯:關於JavaScript     

快速排序又稱劃分交換排序,是以分治法為策略實現的排序算法。本文主要談如何用 JavaScript 實現 in-place(原地)思想的快速排序。

分治法:

在計算機科學中,分治法是一種基於多分支遞歸的重要算法範式。字面意思是「分而治之」——把一個複雜問題分成兩個或多個相同或相似的子問題,直到子問題可以簡單直接求解,原問題的解即子問題解的合併。(摘自維基百科)

快速排序的思想

在數組中指定一個元素作為標尺,比它大的放到它後面,比它小的放到它前面,如此重複直至全部有序。

快速排序分三步:

選基準:在數據結構中選一個元素作為基準(pivot)。
劃分區:參照基準值的大小劃分無序區,所有小於基準的數據放入一個區間,所有大於基準的放入另一區間;分區結束後,基準元素所在位置就是它最終排序後應在的位置。
遞歸:對初次劃分出來的兩個無序區間,遞歸調用第 1、2 步,直到所有無序區間只剩一個元素為止。

先說說普遍的實現方法(未使用原地算法):

 function quickSort(arr) { if (arr.length <= 1) return ; //取數組最接近中間的數位基准,奇數與偶數取值不同,但不印象,當然,你可以選取第一個,或者最後一個數為基准,這裡不作過多描述 var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; //左右區間,用於存放排序後的數 var left = []; var right = []; console.log('基准為:' + pivot + ' 時'); for (var i = 0; i < arr.length; i++) { console.log('分區操作的第 ' + (i + 1) + ' 次循環:'); //小於基准,放於左區間,大於基准,放於右區間 if (arr[i] < pivot) { left.push(arr[i]); console.log('左邊:' + (arr[i])) } else { right.push(arr[i]); console.log('右邊:' + (arr[i])) } } //這裡使用concat操作符,將左區間,基准,右區間拼接為一個新數組 //然後遞歸1,2步驟,直至所有無序區間都 只剩下一個元素 ,遞歸結束 return quickSort(left).concat([pivot], quickSort(right)); } var arr = [14, 3, 15, 7, 2, 76, 11]; console.log(quickSort(arr)); /* * 基准為7時,第一次分區得到左右兩個子集[ 3, 2,] 7 [14, 15, 76, 11]; * 以基准為2,對左邊的子集[3,2]進行劃分區排序,得到[2] 3。左子集排序全部結束 * 以基准為76,對右邊的子集進行劃分區排序,得到[14, 15, 11] 76 * 此時對上面的[14, 15, 11]以基准為15再進行劃分區排序, [14, 11] 15 * 此時對上面的[14, 11]以基准為11再進行劃分區排序, 11 [14] * 所有無序區間都只剩下一個元素,遞歸結束 * */

通過斷點調試,可得出結果。

弊端:

它需要 Ω(n) 的額外存儲空間,和歸並排序一樣不夠理想;在生產環境中,額外的內存開銷會影響性能。很多人以為上面就是真正的快速排序了,因此下面很有必要推薦 in-place 算法的快速排序。

in-place

快速排序一般用遞歸實現,最關鍵的是 partition 分割函數,它把數組劃分為兩部分,一部分小於 pivot,另一部分大於 pivot。具體原理前面提過。

 function quickSort(arr) { // 交換 function swap(arr, a, b) { var temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } // 分區 function partition(arr, left, right) { /** * 開始時不知最終pivot的存放位置,可以先將pivot交換到後面去 * 這裡直接定義最右邊的元素為基准 */ var pivot = arr[right]; /** * 存放小於pivot的元素時,是緊挨著上一元素的,否則空隙裡存放的可能是大於pivot的元素, * 故聲明一個storeIndex變量,並初始化為left來依次緊挨著存放小於pivot的元素。 */ var storeIndex = left; for (var i = left; i < right; i++) { if (arr[i] < pivot) { /** * 遍歷數組,找到小於的pivot的元素,(大於pivot的元素會跳過) * 將循環i次時得到的元素,通過swap交換放到storeIndex處, * 並對storeIndex遞增1,表示下一個可能要交換的位置 */ swap(arr, storeIndex, i); storeIndex++; } } // 最後: 將pivot交換到storeIndex處,基准元素放置到最終正確位置上 swap(arr, right, storeIndex); return storeIndex; } function sort(arr, left, right) { if (left > right) return; var storeIndex = partition(arr, left, right); sort(arr, left, storeIndex - 1); sort(arr, storeIndex + 1, right); } sort(arr, 0, arr.length - 1); return arr; } console.log(quickSort([8, 4, 90, 8, 34, 67, 1, 26, 17]));

分區的優化

細心的同學可能會問:選取不同基準時性能是否不同?答案是肯定的。不過由於我是搞前端的,對算法了解不深,這個坑就留給厲害的人來填補了。

複雜度

快速排序是排序速度最快的算法之一,時間複雜度為 O(n log n)。平均情況下,排序 n 個項目約需 O(n log n) 次比較;最壞情況下則需要 O(n²) 次比較。

以上就是 JavaScript 實現 in-place 思想的快速排序方法,希望對大家有所幫助。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved