排序是指以特定順序(數位或字母)排列線性表的元素。排序通常與搜尋一起配合使用。
有許多排序演演算法,而迄今為止最快的演演算法之一是快速排序(Quicksort)。
快速排序用分治策略對給定的列表元素進行排序。這意味著演演算法將問題分解為子問題,直到子問題變得足夠簡單可以直接解決為止。
從演演算法上講,這可以用遞迴或迴圈實現。但是對於這個問題,用遞迴法更為自然。
先看一下快速排序的工作原理:
接下來通過一個例子理解這些步驟。假設有一個含有未排序元素 [7, -2, 4, 1, 6, 5, 0, -4, 2]
的陣列。選擇最後一個元素作為基準。陣列的分解步驟如下圖所示:
在演演算法的步驟1中被選為基準的元素帶顏色。分割區後,基準元素始終處於陣列中的正確位置。
黑色粗體邊框的陣列表示該特定遞迴分支結束時的樣子,最後得到的陣列只包含一個元素。
最後可以看到該演演算法的結果排序。
這一演演算法的主幹是「分割區」步驟。無論用遞迴還是迴圈的方法,這個步驟都是一樣的。
正是因為這個特點,首先編寫為陣列分割區的程式碼 partition()
:
function partition(arr, start, end){ // 以最後一個元素為基準 const pivotValue = arr[end]; let pivotIndex = start; for (let i = start; i < end; i++) { if (arr[i] < pivotValue) { // 交換元素 [arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]]; // 移動到下一個元素 pivotIndex++; } } // 把基準值放在中間 [arr[pivotIndex], arr[end]] = [arr[end], arr[pivotIndex]] return pivotIndex; };
程式碼以最後一個元素為基準,用變數 pivotIndex
來跟蹤「中間」位置,這個位置左側的所有元素都比 pivotValue
小,而右側的元素都比 pivotValue
大。
最後一步把基準(最後一個元素)與 pivotIndex
交換。
在實現了 partition()
函數之後,我們必須遞迴地解決這個問題,並應用分割區邏輯以完成其餘步驟:
function quickSortRecursive(arr, start, end) { // 終止條件 if (start >= end) { return; } // 返回 pivotIndex let index = partition(arr, start, end); // 將相同的邏輯遞迴地用於左右子陣列 quickSort(arr, start, index - 1); quickSort(arr, index + 1, end); }
在這個函數中首先對陣列進行分割區,之後對左右兩個子陣列進行分割區。只要這個函數收到一個不為空或有多個元素的陣列,則將重複該過程。
空陣列和僅包含一個元素的陣列被視為已排序。
最後用下面的例子進行測試:
array = [7, -2, 4, 1, 6, 5, 0, -4, 2] quickSortRecursive(array, 0, array.length - 1) console.log(array)
輸出:
-4,-2,0,1,2,4,5,6,7
快速排序的遞迴方法更加直觀。但是用迴圈實現快速排序是一個相對常見的面試題。
與大多數的遞迴到迴圈的轉換方案一樣,最先想到的是用棧來模擬遞迴呼叫。這樣做可以重用一些我們熟悉的遞迴邏輯,並在迴圈中使用。
我們需要一種跟蹤剩下的未排序子陣列的方法。一種方法是簡單地把「成對」的元素保留在堆疊中,用來表示給定未排序子陣列的 start
和 end
。
JavaScript 沒有顯式的棧資料結構,但是陣列支援 push()
和 pop()
函數。但是不支援 peek()
函數,所以必須用 stack [stack.length-1]
手動檢查棧頂。
我們將使用與遞迴方法相同的「分割區」功能。看看如何編寫Quicksort部分:
function quickSortIterative(arr) { // 用push()和pop()函數建立一個將作為棧使用的陣列 stack = []; // 將整個初始陣列做為「未排序的子陣列」 stack.push(0); stack.push(arr.length - 1); // 沒有顯式的peek()函數 // 只要存在未排序的子陣列,就重複迴圈 while(stack[stack.length - 1] >= 0){ // 提取頂部未排序的子陣列 end = stack.pop(); start = stack.pop(); pivotIndex = partition(arr, start, end); // 如果基準的左側有未排序的元素, // 則將該子陣列新增到棧中,以便稍後對其進行排序 if (pivotIndex - 1 > start){ stack.push(start); stack.push(pivotIndex - 1); } // 如果基準的右側有未排序的元素, // 則將該子陣列新增到棧中,以便稍後對其進行排序 if (pivotIndex + 1 < end){ stack.push(pivotIndex + 1); stack.push(end); } } }
以下是測試程式碼:
ourArray = [7, -2, 4, 1, 6, 5, 0, -4, 2] quickSortIterative(ourArray) console.log(ourArray)
輸出:
-4,-2,0,1,2,4,5,6,7
當涉及到排序演演算法時,將其視覺化能幫我們直觀的瞭解它們是怎樣運作的,下面這個例子搬運自維基百科:
在圖中也把最後一個元素作為基準。給定陣列分割區後,遞迴遍歷左側,直到將其完全排序為止。然後對右側進行排序。
現在討論它的時間和空間複雜度。快速排序在最壞情況下的時間複雜度是 $O(n^2)$。平均時間複雜度為 $O(n\log n)$。通常,使用隨機版本的快速排序可以避免最壞的情況。
快速排序演演算法的弱點是基準的選擇。每選擇一次錯誤的基準(大於或小於大多數元素的基準)都會帶來最壞的時間複雜度。在重複選擇基準時,如果元素值小於或大於該元素的基準時,時間複雜度為 $O(n\log n)$。
根據經驗可以觀察到,無論採用哪種資料基準選擇策略,快速排序的時間複雜度都傾向於具有 $O(n\log n)$ 。
快速排序不會佔用任何額外的空間(不包括為遞迴呼叫保留的空間)。這種演演算法被稱為in-place演演算法,不需要額外的空間。
更多程式設計相關知識,請存取:!!
以上就是深入淺析JavaScript中的快速排序的詳細內容,更多請關注TW511.COM其它相關文章!