您好,登錄后才能下訂單哦!
JavaScript中快速排序的案例?這個(gè)問題可能是我們?nèi)粘W(xué)習(xí)或工作經(jīng)常見到的。希望通過這個(gè)問題能讓你收獲頗深。下面是小編給大家?guī)淼膮⒖純?nèi)容,讓我們一起來看看吧!
排序是指以特定順序(數(shù)字或字母)排列線性表的元素。排序通常與搜索一起配合使用。
有許多排序算法,而迄今為止最快的算法之一是快速排序(Quicksort)。
快速排序用分治策略對(duì)給定的列表元素進(jìn)行排序。這意味著算法將問題分解為子問題,直到子問題變得足夠簡(jiǎn)單可以直接解決為止。
從算法上講,這可以用遞歸或循環(huán)實(shí)現(xiàn)。但是對(duì)于這個(gè)問題,用遞歸法更為自然。
先看一下快速排序的工作原理:
接下來通過一個(gè)例子理解這些步驟。假設(shè)有一個(gè)含有未排序元素 [7, -2, 4, 1, 6, 5, 0, -4, 2]
的數(shù)組。選擇最后一個(gè)元素作為基準(zhǔn)。數(shù)組的分解步驟如下圖所示:
在算法的步驟1中被選為基準(zhǔn)的元素帶顏色。分區(qū)后,基準(zhǔn)元素始終處于數(shù)組中的正確位置。
黑色粗體邊框的數(shù)組表示該特定遞歸分支結(jié)束時(shí)的樣子,最后得到的數(shù)組只包含一個(gè)元素。
最后可以看到該算法的結(jié)果排序。
這一算法的主干是“分區(qū)”步驟。無論用遞歸還是循環(huán)的方法,這個(gè)步驟都是一樣的。
正是因?yàn)檫@個(gè)特點(diǎn),首先編寫為數(shù)組分區(qū)的代碼 partition()
:
function partition(arr, start, end){ // 以最后一個(gè)元素為基準(zhǔn) 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]]; // 移動(dòng)到下一個(gè)元素 pivotIndex++; } } // 把基準(zhǔn)值放在中間 [arr[pivotIndex], arr[end]] = [arr[end], arr[pivotIndex]] return pivotIndex; };
代碼以最后一個(gè)元素為基準(zhǔn),用變量 pivotIndex
來跟蹤“中間”位置,這個(gè)位置左側(cè)的所有元素都比 pivotValue
小,而右側(cè)的元素都比 pivotValue
大。
最后一步把基準(zhǔn)(最后一個(gè)元素)與 pivotIndex
交換。
在實(shí)現(xiàn)了 partition()
函數(shù)之后,我們必須遞歸地解決這個(gè)問題,并應(yīng)用分區(qū)邏輯以完成其余步驟:
function quickSortRecursive(arr, start, end) { // 終止條件 if (start >= end) { return; } // 返回 pivotIndex let index = partition(arr, start, end); // 將相同的邏輯遞歸地用于左右子數(shù)組 quickSort(arr, start, index - 1); quickSort(arr, index + 1, end); }
在這個(gè)函數(shù)中首先對(duì)數(shù)組進(jìn)行分區(qū),之后對(duì)左右兩個(gè)子數(shù)組進(jìn)行分區(qū)。只要這個(gè)函數(shù)收到一個(gè)不為空或有多個(gè)元素的數(shù)組,則將重復(fù)該過程。
空數(shù)組和僅包含一個(gè)元素的數(shù)組被視為已排序。
最后用下面的例子進(jìn)行測(cè)試:
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
快速排序的遞歸方法更加直觀。但是用循環(huán)實(shí)現(xiàn)快速排序是一個(gè)相對(duì)常見的面試題。
與大多數(shù)的遞歸到循環(huán)的轉(zhuǎn)換方案一樣,最先想到的是用棧來模擬遞歸調(diào)用。這樣做可以重用一些我們熟悉的遞歸邏輯,并在循環(huán)中使用。
我們需要一種跟蹤剩下的未排序子數(shù)組的方法。一種方法是簡(jiǎn)單地把“成對(duì)”的元素保留在堆棧中,用來表示給定未排序子數(shù)組的 start
和 end
。
JavaScript 沒有顯式的棧數(shù)據(jù)結(jié)構(gòu),但是數(shù)組支持 push()
和 pop()
函數(shù)。但是不支持 peek()
函數(shù),所以必須用 stack [stack.length-1]
手動(dòng)檢查棧頂。
我們將使用與遞歸方法相同的“分區(qū)”功能??纯慈绾尉帉慟uicksort部分:
function quickSortIterative(arr) { // 用push()和pop()函數(shù)創(chuàng)建一個(gè)將作為棧使用的數(shù)組 stack = []; // 將整個(gè)初始數(shù)組做為“未排序的子數(shù)組” stack.push(0); stack.push(arr.length - 1); // 沒有顯式的peek()函數(shù) // 只要存在未排序的子數(shù)組,就重復(fù)循環(huán) while(stack[stack.length - 1] >= 0){ // 提取頂部未排序的子數(shù)組 end = stack.pop(); start = stack.pop(); pivotIndex = partition(arr, start, end); // 如果基準(zhǔn)的左側(cè)有未排序的元素, // 則將該子數(shù)組添加到棧中,以便稍后對(duì)其進(jìn)行排序 if (pivotIndex - 1 > start){ stack.push(start); stack.push(pivotIndex - 1); } // 如果基準(zhǔn)的右側(cè)有未排序的元素, // 則將該子數(shù)組添加到棧中,以便稍后對(duì)其進(jìn)行排序 if (pivotIndex + 1 < end){ stack.push(pivotIndex + 1); stack.push(end); } } }
以下是測(cè)試代碼:
ourArray = [7, -2, 4, 1, 6, 5, 0, -4, 2] quickSortIterative(ourArray) console.log(ourArray)
輸出:
-4,-2,0,1,2,4,5,6,7
當(dāng)涉及到排序算法時(shí),將其可視化能幫我們直觀的了解它們是怎樣運(yùn)作的,下面這個(gè)例子搬運(yùn)自維基百科:
在圖中也把最后一個(gè)元素作為基準(zhǔn)。給定數(shù)組分區(qū)后,遞歸遍歷左側(cè),直到將其完全排序?yàn)橹埂H缓髮?duì)右側(cè)進(jìn)行排序。
現(xiàn)在討論它的時(shí)間和空間復(fù)雜度。快速排序在最壞情況下的時(shí)間復(fù)雜度是 $O(n^2)$。平均時(shí)間復(fù)雜度為 $O(n\log n)$。通常,使用隨機(jī)版本的快速排序可以避免最壞的情況。
快速排序算法的弱點(diǎn)是基準(zhǔn)的選擇。每選擇一次錯(cuò)誤的基準(zhǔn)(大于或小于大多數(shù)元素的基準(zhǔn))都會(huì)帶來最壞的時(shí)間復(fù)雜度。在重復(fù)選擇基準(zhǔn)時(shí),如果元素值小于或大于該元素的基準(zhǔn)時(shí),時(shí)間復(fù)雜度為 $O(n\log n)$。
根據(jù)經(jīng)驗(yàn)可以觀察到,無論采用哪種數(shù)據(jù)基準(zhǔn)選擇策略,快速排序的時(shí)間復(fù)雜度都傾向于具有 $O(n\log n)$ 。
快速排序不會(huì)占用任何額外的空間(不包括為遞歸調(diào)用保留的空間)。這種算法被稱為in-place算法,不需要額外的空間。
感謝各位的閱讀!看完上述內(nèi)容,你們對(duì)JavaScript中快速排序的案例大概了解了嗎?希望文章內(nèi)容對(duì)大家有所幫助。如果想了解更多相關(guān)文章內(nèi)容,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。