web開發(fā)中如何實(shí)現(xiàn)快速排序

小編給大家分享一下web開發(fā)中如何實(shí)現(xiàn)快速排序，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

快速排序

快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個(gè)項(xiàng)目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見。事實(shí)上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來。

快速排序使用分治法（Divide and conquer）策略來把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）。

快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。

算法步驟

1. 從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）;

2. 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作；

3. 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序；

遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì)退出，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。

來源：https://github.com/hustcc/JS-Sorting-Algorithm

算法演示

排序動(dòng)畫過程解釋

1. 首先，操作數(shù)列中的所有數(shù)字

2. 在所有數(shù)字中選擇一個(gè)數(shù)字作為排序的基準(zhǔn)（pivot）, pivot 通常是隨機(jī)選擇的，在這里為了演示方便，我們選擇最右邊的數(shù)字作為 pivot

3. 選取好 pivot 后，在操作數(shù)列中選擇最左邊的數(shù)字標(biāo)記為 左標(biāo)記 ，最右邊的數(shù)字標(biāo)記為 右標(biāo)記

4. 將左邊的標(biāo)記向右移動(dòng)

5. 當(dāng) 左標(biāo)記 達(dá)到超過 pivot 的數(shù)字時(shí)，停止移動(dòng)

6. 在這里，8 > 6 ,所以停止移動(dòng)

7. 然后將右邊的標(biāo)記向左移動(dòng)

8. 當(dāng) 右標(biāo)記 達(dá)到小于 pivot 的數(shù)字時(shí)，停止移動(dòng)

9. 在這里，4 < 6 ,所以停止移動(dòng)

10. 當(dāng)左右標(biāo)記停止時(shí)，更改標(biāo)記的數(shù)字

11. 因此，左標(biāo)記 的作用是找到一個(gè)大于 pivot 的數(shù)字，右標(biāo)記 的作用是找到一個(gè)小于 pivot 的數(shù)字

12. 通過交換數(shù)字，可以在數(shù)列的左邊收集小于 pivot 的數(shù)字集合，右邊收集大于 pivot 的數(shù)字集合

13. 交換之后，繼續(xù)移動(dòng) 左標(biāo)記

14. 在這里，9 > 6 ,所以停止移動(dòng)

15. 然后將右邊的標(biāo)記向左移動(dòng)

16. 當(dāng) 右標(biāo)記 碰撞到 左標(biāo)記 時(shí)也停止移動(dòng)

17. 如果左右側(cè)的標(biāo)記停止時(shí)，并且都在同一個(gè)位置，將這個(gè)數(shù)字和 pivot 的數(shù)字交換

18. 這就完成了第一次操作

19. 小于 6 的都在 6 的左側(cè)，大于 6 的都在 6 的右側(cè)

20. 然后遞歸對(duì)這分成的兩部分都執(zhí)行同樣的操作

21. 完成 快速排序

代碼實(shí)現(xiàn)

為了更好的讓讀者用自己熟悉的編程語言來理解動(dòng)畫，筆者將貼出多種編程語言的參考代碼，代碼全部來源于網(wǎng)上。

C++代碼實(shí)現(xiàn)

Java代碼實(shí)現(xiàn)

Python代碼實(shí)現(xiàn)

JavaScript代碼實(shí)現(xiàn)

以上是“web開發(fā)中如何實(shí)現(xiàn)快速排序”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！