Introduction to Sorting
This page provides a brief introduction to sorting algorithms.
Definition
A sorting algorithm is an algorithm that arranges a specific set of data in a certain order. There are various sorting algorithms, and their properties differ significantly.
Properties
Stability
Stability refers to whether the relative order of equal elements changes after sorting.
An algorithm with the stability property maintains the relative order of records with equal keys. That is, if a sorting algorithm is stable, and there are two records \(R\) and \(S\) with equal keys, where \(R\) appears before \(S\) in the original list, then \(R\) will also appear before \(S\) in the sorted list.
Radix sort, counting sort, insertion sort, bubble sort, and merge sort are stable sorts.
Selection sort, heap sort, quick sort, and shell sort are not stable sorts.
Time Complexity
Main page: Complexity
Time complexity is used to measure the relationship between the running time of an algorithm and the input size, usually denoted by \(O\).
A simple method to estimate complexity is to count the number of "simple operations" performed, and sometimes one can directly count the number of loop layers for an approximate estimate.
Time complexity is divided into best-case, average-case, and worst-case time complexity. In OI competitions, the worst-case time complexity is generally considered, as it represents the lower bound of the algorithm's performance, and no worse results will appear in evaluations.
The lower bound for the time complexity of comparison-based sorting algorithms is \(O(n\log n)\).
Of course, there are also algorithms that are not \(O(n\log n)\). For example, the time complexity of counting sort is \(O(n+w)\), where \(w\) represents the range of the input data.
Below is a comparison of several sorting algorithms.
Space Complexity
Similar to time complexity, space complexity describes the scale of space consumption by an algorithm. Generally, the smaller the space complexity, the better the algorithm.
External Links
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用