在計算機科學中，排序算法是一種將列表元素按順序排列的算法。最常用的順序是數字順序和字典順序，以及升序或降序。高效排序對于優化要求輸入數據在排序列表中的其他算法（例如搜索和合并算法）的效率很重要。排序對于規范化數據和產生人類可讀的輸出通常也很有用。

形式上，任何排序算法的輸出必須滿足兩個條件：

1. 輸出是單調順序的（每個元素不小于/大于前一個元素，根據所需的順序）。
2. 輸出是輸入的排列（重新排序，但保留所有原始元素）。

為了獲得最佳效率，輸入數據應存儲在允許隨機訪問的數據結構中，而不是只允許順序訪問的數據結構中。

從計算開始，排序問題就吸引了大量的研究，這可能是由于盡管它簡單、熟悉的陳述，但有效解決它的復雜性。1951年左右早期排序算法的作者之一是從事ENIAC和UNIVAC工作的BettyHolberton。早在1956年就對冒泡排序進行了分析。自20世紀中葉以來，漸近最優算法就已為人所知——新算法仍在被發明，廣泛使用的Timsort可追溯到2002年，而庫sort于2006年首次發布。

比較排序算法具有Ω(nlogn)比較的基本要求（某些輸入序列將需要nlogn比較的倍數，其中n是要排序的數組中的元素數）。不基于比較的算法，例如計數排序，可以有更好的性能。

排序算法在計算機科學入門課程中很流行，針對該問題的大量算法提供了對各種核心算法概念的溫和介紹，例如大O表示法、分治算法、堆和二叉樹等數據結構、隨機算法、最佳、最差和平均情況分析、時空權衡以及上下限。

以最佳方式（以最少的比較和交換）或快速（即考慮機器特定的細節）對小數組進行排序仍然是一個開放的研究問題，只有非常小的數組（<20個元素）才知道解決方案。在并行機器上進行類似的最優（根據各種定義）排序是一個開放的研究課題。

排序算法可以分為：

• 計算復雜度
  • 就列表大小而言的最佳、最差和平均情況行為。對于典型的串行排序算法，好的行為是O(nlogn)，并行排序是O(log2n)，不好的行為是O(n2)。串行排序的理想行為是O(n)，但在一般情況下這是不可能的。最佳并行排序為O(logn)。
  • 交換“就地”算法。
• 內存使用（以及其他計算機資源的使用）。特別是，一些排序算法是“就地”的。嚴格來說，就地排序只需要O(1)內存，而不是被排序的項目；有時O(logn)額外內存被認為是“就地”。
• 遞歸：一些算法要么是遞歸的，要么是非遞歸的，而另一些可能兩者兼而有之（例如，歸并排序）。
• 穩定性：穩定的排序算法保持具有相等鍵（即值）的記錄的相對順序。
• 它們是否是比較排序。比較排序僅通過使用比較運算符比較兩個元素來檢查數據。
• 一般方法：插入、交換、選擇、合并等。交換排序包括冒泡排序和快速排序。選擇排序包括循環排序和堆排序。
• 算法是串行的還是并行的。本討論的其余部分幾乎完全集中于串行算法并假設串行操作。
• 適應性：輸入的預排序是否影響運行時間。考慮到這一點的算法已知是自適應的。
• 在線：在線的插入排序等算法可以對恒定的輸入流進行排序。

穩定的排序算法按照它們在輸入中出現的相同順序對相等的元素進行排序。例如，在右側的卡片排序示例中，卡片按其等級排序，而它們的花色被忽略。這允許原始列表的多個不同正確排序版本的可能性。穩定的排序算法選擇其中之一，根據以下規則：如果兩個項目比較相等（如兩張5卡），則它們的相對順序將被保留，即如果輸入中一個在另一個之前，它將來在輸出中的另一個之前。

穩定性對于保持同一數據集上多個排序的順序很重要。例如，假設由姓名和班級部分組成的學生記錄是動態排序的，首先按姓名，然后按班級部分。如果在這兩種情況下都使用穩定的排序算法，則sort-by-class-section操作不會改變名稱順序；對于不穩定的排序，可能是按部分排序會打亂姓名順序，從而導致學生列表不按字母順序排列。

更正式地說，被排序的數據可以表示為值的記錄或元組，用于排序的數據部分稱為鍵。在卡片示例中，卡片表示為記錄（等級、花色），鍵是等級。一個排序算法是穩定的，如果有兩個記錄R和S具有相同的鍵，并且R在原始列表中出現在S之前，那么R在排序列表中總是出現在S之前。

當相等的元素無法區分時，例如整數，或更一般地說，任何以整個元素為關鍵的數據，穩定性都不是問題。如果所有鍵都不同，穩定性也不是問題。

不穩定的排序算法可以專門實現穩定。這樣做的一種方法是人為地擴展鍵比較，以便使用原始輸入列表中條目的順序作為決勝局來決定具有其他相同鍵的兩個對象之間的比較。然而，記住這個順序可能需要額外的時間和空間。

雖然有大量的排序算法，但在實際實現中，少數算法占主導地位。插入排序廣泛用于小數據集，而對于大數據集，則使用漸近有效的排序，主要是堆排序、歸并排序或快速排序。高效的實現通常使用混合算法，將整體排序的漸近高效算法與遞歸底部的小列表的插入排序相結合。高度調整的實現使用更復雜的變體，例如在Android、Java和Python中使用的Timsort（合并排序、插入排序和附加邏輯），以及在某些C++排序中（以變體形式）使用的introsort（快速排序和堆排序）實現和.NET。

對于更受限的數據，例如固定區間的數字，廣泛使用計數排序或基數排序等分布排序。冒泡排序和變體在實踐中很少使用，但在教學和理論討論中很常見。

在對對象進行物理排序時（例如按字母順序排列的論文、測試或書籍），人們直觀地通常對小集合使用插入排序。對于較大的集合，人們通常首先進行分組，例如按首字母，并且多個分組允許對非常大的集合進行實際排序。通常空間相對便宜，例如將物體散布在地板上或大面積上，但操作成本高，尤其是移動物體很遠的距離——參考的位置很重要。合并排序對于物理對象也很實用，特別是因為可以使用兩只手，每個要合并的列表一只手，而其他算法，例如堆排序或快速排序，不適合人類使用。其他算法，如庫排序，一種保留空格的插入排序的變體，對于物理使用也很實用。

最簡單的兩種排序是插入排序和選擇排序，由于開銷低，這兩種排序在小數據上都很有效，但在大數據上效率不高。插入排序在實踐中通常比選擇排序快，因為在幾乎排序的數據上比較少和性能好，因此在實踐中是首選，但選擇排序使用較少的寫入，因此在寫入性能是一個限制因素時使用。

插入排序是一種簡單的排序算法，對于小型列表和大多數已排序的列表相對有效，并且通常用作更復雜算法的一部分。它的工作原理是從列表中一個一個地取出元素，并將它們插入到一個新的排序列表中的正確位置，類似于我們將錢存入錢包的方式。在數組中，新列表和剩余的元素可以共享數組的空間，但是插入是昂貴的，需要將所有后續元素移動一個。Shellsort（見下文）是插入排序的一種變體，對于較大的列表更有效。

選擇排序是一種就地比較排序。它具有O(n2)復雜度，使其在大型列表上效率低下，并且通常比類似的插入排序表現更差。選擇排序以其簡單性著稱，在某些情況下也比更復雜的算法具有性能優勢。

該算法找到最小值，將其與xxx個位置的值交換，然后對列表的其余部分重復這些步驟。它不超過n次交換，因此在交換非常昂貴的情況下很有用。

實用的通用排序算法幾乎總是基于平均時間復雜度（通常是最壞情況復雜度）O(nlogn)的算法，其中最常見的是堆排序、歸并排序和快速排序。每個人都有優點和缺點，最顯著那么簡單實現合并排序使用O（?）額外的空間，并實現簡單快速排序為O（?2）最壞情況的復雜性。這些問題可以以更復雜的算法為代價來解決或改善。

雖然這些算法在隨機數據上是漸近有效的，但為了在現實世界數據上的實際效率，使用了各種修改。首先，這些算法的開銷在較小的數據上變得顯著，因此通常使用混合算法，一旦數據足夠小，通常會切換到插入排序。其次，算法通常在已經排序的數據或幾乎排序的數據上表現不佳——這些在現實世界的數據中很常見，并且可以通過適當的算法在O(n)時間內排序。最后，它們也可能是不穩定的，而穩定性通常是一種理想的屬性。因此，通常會使用更復雜的算法，例如Timsort（基于歸并排序）或introsort（基于快速排序，回退到堆排序）。