web開發(fā)中如何實現(xiàn)歸并排序

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

歸并排序

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。

作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實現(xiàn)由兩種方法：

• 自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；

• 自下而上的迭代；

和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因為始終都是 O(nlogn) 的時間復雜度。代價是需要額外的內(nèi)存空間。

算法步驟

1. 申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列；

2. 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置；

3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；

4. 重復步驟 3 直到某一指針達到序列尾；

5. 將另一序列剩下的所有元素直接復制到合并序列尾。

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

算法演示

動畫演示加載有點慢，請稍等片刻

排序動畫過程解釋

1. 首先，將數(shù)字分割成兩片區(qū)域

2. 再將數(shù)字分割成兩片區(qū)域

3. 依次劃分

4. 直到每片區(qū)域只有一個元素

5. 分割完成

6. 接下來，將分割的每片區(qū)域進行合并組合

7. 合并時，按照數(shù)字的升序移動，使得合并后的數(shù)字在組內(nèi)按升序排列

8. 當合并包含多個數(shù)字的組時，比較開頭的數(shù)字，移動其中較小的數(shù)字

9. 比如在動畫中，比較開頭的 4 和 3

10. 其中 4 大于 3， 因此移動 3

11. 按照同樣的邏輯去比較該列剩余的頭數(shù)

12. 4 小于 7 ，所以移動 4

13. 同樣的邏輯去進行接下來的操作

14. 遞歸的重復組的合并操作，直到所有數(shù)字都在一個組中。

15. 完成 歸并排序 

代碼實現(xiàn)

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

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

Java代碼實現(xiàn)

Python代碼實現(xiàn)

JavaScript代碼實現(xiàn)

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