快速排序(quick sort)和合併排序(merge sort)的區別
對列表中的專案進行排序是一項很平常的任務，而且常常很耗時。術語排序通常是指根據預先指定的排序關係，以升序或降序排列列表中的專案。排序通常用於搜尋，這是資料處理中的另一項基本活動。想象一下，如果字典裡的單詞沒有被組織或分類，那麼在字典裡搜尋單詞是多麼困難。這就是為什麼字典裡的詞條是按標準的字母順序排列的。透過排序，許多工和計算變得毫不費力。這就是排序演算法的用武之地。
排序演算法只不過是一種將列表中的元素按特定順序組織的方法，例如從最小值到最大值、從最大值到最小值、遞增順序、遞減順序、字母順序等。最常用的順序是數字順序和字典順序。演算法通常使用排序作為關鍵子例程。有各種各樣的排序演算法貫穿始終，每一種都採用了一套豐富的技術。一種流行但同樣強大的演算法是分治演算法，它是一種基於多分支遞迴的演算法。快速排序和合併排序是基於分治演算法的兩種常用演算法。
什麼是快速排序(quick sort)？
快速排序是一種基於分而治之方法的高效排序演算法，類似於將問題分解為兩個子問題或多個子問題，然後遞迴求解的動態排序方法。如果子問題的大小足夠小，那麼它們就可以簡單地以直接的方式解決，而不需要任何麻煩。快速排序演算法也稱為分割槽交換排序，它將要排序的列表分為三個主要部分：1）樞軸元素（中心元素），2）小於樞軸的元素，3）大於樞軸的元素。樞軸本身在兩個組之間移動到最終位置，然後遞迴地應用快速排序。
什麼是合併排序(merge sort)？
合併排序是另一種基於分治技術的通用排序演算法。它是最受尊敬和流行的排序演算法之一，設計用於高效地對外部儲存在檔案中的資料進行排序。在使用O（n）額外儲存的最壞情況下，它提供O（n logn）行為。它將集合“a”劃分為兩個較小的集合，然後對每個集合進行排序。在最後階段，這兩個已排序的集合將合併回大小為n的單個集合。這將是排序列表。該演算法是相當快，也是一個穩定的排序，是理想的首選連結串列。
快速排序和合併排序的區別
基礎知識
–快速排序和合併排序都是基於分而治之的排序演算法，其基本原理相同–將一個問題分成兩個或多個子問題，然後遞迴求解。然而，它們在合併程式和效能方面有所不同。對於小資料集，快速排序通常比其他排序演算法（包括合併排序）更好更快，而合併排序保持一致性，而不管資料集的型別如何。快速排序是理想的首選陣列，而合併排序是理想的首選連結串列。
空間複雜性
–快速排序演算法中的排序是遞迴進行的，每個遞迴呼叫都需要堆疊位置。它不需要額外的空間來進行合併，只需要一個記憶體空間來進行合併。由於它是就地排序演算法，因此不需要額外的空間來執行排序。實際上，它在分割和合併陣列時使用相同的陣列。另一方面，在Merge-Sort中，有幾種方法可以將資料表示為檔案或陣列，因此它需要像子檔案或相同大小的陣列這樣的工作區，這些工作區需要額外的空間。
最壞情況複雜性
–快速排序的最壞情況發生在分割槽不平衡時，這取決於用於分割槽的元素，在這種情況下，演算法與**排序一樣緩慢地漸進執行。快速排序的最壞情況是O（n2），並留作練習。但是，可以透過選擇正確的軸來避免這種情況。另一方面，合併排序的最壞情況發生在它必須進行最大數量的比較時。考慮到合併的線性效能，合併排序的最壞情況是O（nlog2n）。
演出
–儘管快速排序和合併排序演算法都是基於分而治之的排序方法，但它們在執行拆分和合併過程的方法上有所不同。對於快速排序，大部分工作是將列表劃分為兩個子列表，這在子列表排序之前發生。對於合併排序，大部分工作是在對子列表進行排序之後合併兩個子列表。合併排序需要一個臨時陣列來合併兩個子陣列，而快速排序不需要額外的陣列空間，因此比Marge排序更節省空間。
快速排序與合併排序：比較圖
總結 - 快速排序(of quick sort) vs. 合併排序(merge sort)
快速排序和合併排序演算法都是基於分而治之的排序方法。但是，它們在執行拆分和合併過程時使用的方法不同。它們的工作原理基本相同——將一個問題分成兩個或多個子問題，然後遞迴求解。在最壞的情況下，合併排序比快速排序更有效，但在平均情況下，兩者的效率相同。但是快速排序比合併排序更節省空間。因此，快速排序無疑比合併排序更快更好，但在一些情況下（例如在比較時），它會變得效率低下。
- 發表於 2021-06-25 22:32
- 閱讀 ( 52 )
- 分類：科技
你可能感興趣的文章
銀行程式碼(swift code)和分類程式碼(sort code)的區別
...的銀行的SWIFT程式碼以及相關的賬戶詳細資訊。 什麼是排序程式碼(sort code)？ 分類程式碼是英國和愛爾蘭版本的路由號碼，用於在各自國家內的金融機構之間透過各自的清算所進行資金轉移。它是一個六位數的數字，通常分為...
插入排序(insertion sort)和選擇排序(selection sort)的區別
關鍵區別-**排序與選擇排序 **排序和選擇排序是兩種排序演算法，用於對一組資料進行排序。有時有必要按特定順序排列資料。排序演算法是對一組資料進行排序的機制。在排序中，資料是按照數字或字典順序排列的。如果...
如何刪除xbox one上的遊戲
...n A time.按上次用於檢視您有一段時間沒有玩過的遊戲進行排序。或者，選擇“按大小排序”，首先檢視最大的遊戲。 突出顯示一個遊戲，然後按控制器上的選單按鈕。 選擇“解除安裝”，然後選擇...
如何按評論數對亞馬遜搜尋結果排序
... Amazon Sort for Chrome幫助您按評論數對搜尋結果進行排序。簡單但有效！ ...
為編寫者和開發人員提供的5個最佳mac檔案比較工具
...的選單中。它有許多可自定義的設定，使檔案比較容易和快速。在第一次啟動時，應用程式為您提供了一個選擇比較模組的選項。 ...
如何在excel中生成可排序標題
...到最舊的排序。 在這個例子的後面，假設我們想給需要快速銷售的商品貼上標籤。我們可以用一個簡單的綠色、黃色和紅色系統來標記日期，以顯示幾天內有效的商品，那些接近銷售日期的商品，以及那些必須立即**的商品。...
如何在谷歌地圖中更改汽車圖示
在分析googlesheets中的複雜資料集時，可以利用其內建的排序功能來組織資料。您可以按單個列排序，或者，對於更復雜的資料，可以按多列排序。 為此，您需要開啟googlesheets電子表格並選擇要排序的資料集。您可以手動執行此...
如何在linux上使用uniq命令
linuxuniq命令在文字檔案中快速查詢唯一或重複的行。在本指南中，我們將介紹它的多功能性和特性，以及如何充分利用這個漂亮的實用程式。 在linux上查詢匹配的文字行 uniq命令是快速、靈活的，而且非常擅長它所做的事情。...
如何在linux上使用tail命令
...的末尾，因此tail命令是檢視檔案中最新新增內容的一種快速簡便的方法。它還可以監視一個檔案，並在出現新的文字條目時顯示該檔案。這使它成為監視日誌檔案的好工具。 許多現代Linux發行版都採用了systemd系統和****器。這是...
如何在linux上使用管道
...awk '{print $5 " " $3 " " $9}' | sort -n 輸出現在按檔案大小順序排序，我們自定義選擇了三列。 新增其他命令 最後我們將新增tail命令。我們將告訴它只列出最後五行輸出。 ls -l | grep "page" | awk '{print $5 " " $3 " " $9}' | sort -n | tail -5 這...
