Java中的合併排序程序：合併排序和快速排序之間的區別

JAVA中的歸併排序程序介紹

顧名思義，JAVA中的歸併排序程序是一種排序算法。 它被經典地概念化為 JAVA 中的分而治之算法。 Java 中的歸併排序程序通過遞歸地將輸入數組分解為其兩個或多個組成子問題來工作，直到這些子問題簡單到可以直接解決。

組成子問題可以與父問題相似或有些相關。 然後將每個子問題的單獨解決方案組合起來以獲得原始父問題的解決方案。

Java 中的歸併排序程序是如何工作的？

如前所述，JAVA 中的歸併排序程序是一種分而治之的算法。 這是一種穩定的排序，這意味著數組元素在整個排序過程中保持其相對於彼此的原始位置。

• 劃分： 在這一步中，輸入數組被分成兩個組成部分。 對所有得到的半陣列不斷重複此步驟，直到沒有更多的半陣列可以進一步劃分。
• 征服：在這一步中，將分割後的數組從下到上排序合併，達到最終排序後的數組。

Java中快速排序和合併排序程序的區別

儘管功能相似，但必須重點強調 JAVA 中快速排序和合併排序之間的根本區別。

• 機制：快速排序是一種內部的就地排序算法，而歸併排序是一種外部的就地排序算法。 在快速排序中，元素是根據稱為樞軸的關鍵元素進行排序的。 樞軸通常是輸入數組中的中間值。 值小於樞軸的元素被推到樞軸的左側，而具有更大值的元素被推到樞軸的右側。 這裡，將左側稱為左分區，將右側稱為右分區。 相反，歸併排序將一個數組重複拆分為兩個子數組（n/2），直到只剩下一個元素。 然後它組合子數組以形成排序數組。
• 應用：雖然快速排序適用於小型數組，但合併排序適用於任何數組，無論其大小。
• 速度：在快速排序的情況下，數據集越小，算法越快。 另一方面，Mergesort 以一致的速度處理所有數據集。
• 空間需求和內存使用：如前所述，歸併排序是一種外部的、異地排序算法。 它的空間複雜度是O(n)。 因此，需要額外存儲 (O(n)) 來對輔助數組進行排序。

另請閱讀： Java 中的文字類型及示例

JAVA中歸併排序程序的時間複雜度分析

JAVA中的歸併排序程序的時間複雜度為O(n*log n)。 根據二分搜索，每當一個數字在每一步中被分成兩半時，它都可以用對數函數'log n'來表示。 步數（最多）可以用 log n +1 表示。 任何子數組的中間都是 O(1)。

因此，要合併子陣列，將需要 O (n) 的運行時間。 因此，在 JAVA 中合併排序程序的總時間變為 n (log n +1)。 在所有三種情況（最差、平均和最佳）中，這相當於 O (n*log n) 的時間複雜度，因為合併排序總是需要線性時間來合併兩半。

從世界頂級大學在線學習軟件課程。 獲得行政 PG 課程、高級證書課程或碩士課程，以加快您的職業生涯。

加起來

正如人類的排序數據在邏輯上是合理的並且更容易理解一樣，排序數組對於計算機來說更易於管理。 這就是 JAVA 中的歸併排序程序的優勢所在。 它是一種高效的、通用的、基於比較的排序算法。

如果您有興趣了解有關 Java 全棧軟件開發的更多信息，請查看 upGrad 和 IIIT-B 的全棧軟件開發執行 PG 計劃，該計劃專為工作專業人士設計，提供 500 多個小時的嚴格培訓，9+項目和任務、IIIT-B 校友身份、實用的實踐頂點項目和頂級公司的工作協助。