排序簡介
本頁面將簡要介紹排序算法。
定義
排序算法（英語：Sorting algorithm）是一種將一組特定的數據按某種順序進行排列的算法。排序算法多種多樣，性質也大多不同。
性質
穩定性
穩定性是指相等的元素經過排序之後相對順序是否發生了改變。
擁有穩定性這一特性的算法會讓原本有相等鍵值的紀錄維持相對次序，即如果一個排序算法是穩定的，當有兩個相等鍵值的紀錄 \(R\) 和 \(S\)，且在原本的列表中 \(R\) 出現在 \(S\) 之前，在排序過的列表中 \(R\) 也將會是在 \(S\) 之前。
基數排序、計數排序、插入排序、冒泡排序、歸併排序是穩定排序。
選擇排序、堆排序、快速排序、希爾排序不是穩定排序。
時間複雜度
主頁面：複雜度
時間複雜度用來衡量一個算法的運行時間和輸入規模的關係，通常用 \(O\) 表示。
簡單計算複雜度的方法一般是統計「簡單操作」的執行次數，有時候也可以直接數循環的層數來近似估計。
時間複雜度分為最優時間複雜度、平均時間複雜度和最壞時間複雜度。OI 競賽中要考慮的一般是最壞時間複雜度，因為它代表的是算法運行水平的下界，在評測中不會出現更差的結果了。
基於比較的排序算法的時間複雜度下限是 \(O(n\log n)\) 的。
當然也有不是 \(O(n\log n)\) 的。例如，計數排序 的時間複雜度是 \(O(n+w)\)，其中 \(w\) 代表輸入數據的值域大小。
以下是幾種排序算法的比較。
空間複雜度
與時間複雜度類似，空間複雜度用來描述算法空間消耗的規模。一般來説，空間複雜度越小，算法越好。
外部鏈接
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用