資料結構 - 排序技術

排序是指以特定格式排列資料。排序演算法指定以特定順序排列資料的方式。最常見的順序是數值順序或字典順序。

排序的重要性在於，如果資料以排序的方式儲存，則可以將資料搜尋最佳化到非常高的水平。排序還用於以更易讀的格式表示資料。以下是現實生活中排序的一些示例：

原地排序和非原地排序

排序演算法可能需要一些額外的空間來比較和臨時儲存少量資料元素。這些演算法不需要任何額外的空間，並且據說排序是在原地發生的，或者例如，在陣列本身內。這稱為原地排序。氣泡排序是原地排序的一個例子。

但是，在某些排序演算法中，程式需要大於或等於被排序元素的空間。使用等於或更多空間的排序稱為非原地排序。歸併排序是非原地排序的一個例子。

如果排序演算法在排序內容後不更改其出現順序的相似內容，則稱為穩定排序。

如果排序演算法在排序內容後更改其出現順序的相似內容，則稱為不穩定排序。

當我們希望維護原始元素的順序（例如元組）時，演算法的穩定性很重要。

如果排序演算法利用要排序的列表中已經“排序”的元素，則稱該排序演算法為自適應的。也就是說，在排序時，如果源列表中有一些元素已經排序，則自適應演算法將考慮這一點，並會嘗試不重新排序它們。

非自適應演算法是不考慮已經排序的元素的演算法。它們試圖強制重新排序每個元素以確認其排序性。

在討論排序技術時，通常會創造一些術語，以下是它們的簡要介紹：

如果後續元素大於前一個元素，則稱一系列值處於升序。例如，1、3、4、6、8、9 按升序排列，因為每個後續元素都大於前一個元素。

如果後續元素小於當前元素，則稱一系列值處於降序。例如，9、8、6、4、3、1 按降序排列，因為每個後續元素都小於前一個元素。

如果後續元素小於或等於序列中其前一個元素，則稱一系列值處於非遞增序。當序列包含重複值時，會出現此順序。例如，9、8、6、3、3、1 按非遞增序排列，因為每個後續元素都小於或等於（對於 3）但不大於任何前一個元素。

如果後續元素大於或等於序列中其前一個元素，則稱一系列值處於非遞減序。當序列包含重複值時，會出現此順序。例如，1、3、3、6、8、9 按非遞減序排列，因為每個後續元素都大於或等於（對於 3）但不小於前一個元素。

有幾種可用的排序技術來對各種資料結構的內容進行排序。以下是一些：

列印頁面