This page briefly introduces sorting algorithms.
Definition
A sorting algorithm (English: Sorting algorithm) is an algorithm that arranges a set of specific data in a certain order. Sorting algorithms are diverse, and most have different properties.
Properties
Stability
Stability refers to whether the relative order of equal elements changes after sorting.
An algorithm with this property maintains the relative order of records that originally had equal keys. That is, if a sorting algorithm is stable and two records with equal keys are and , with appearing before in the original list, then also appears before in the sorted list.
Radix sort, counting sort, insertion sort, bubble sort, and merge sort are stable sorts.
Selection sort, heap sort, quicksort, and Shell sort are not stable sorts.
Time complexity
Main page: Complexity
Time complexity measures the relationship between an algorithm's running time and the input size, usually denoted by .
A simple way to calculate complexity is generally to count the number of executions of “simple operations”; sometimes the number of loop levels can be counted directly for an approximate estimate.
Time complexity is divided into best-case, average-case, and worst-case time complexity. In OI contests, the worst-case time complexity is generally what matters, because it represents the lower bound of the algorithm's running performance; no worse result will occur during evaluation.
The lower bound on the time complexity of comparison-based sorting algorithms is .
Of course, there are also algorithms that are not . For example, counting sort has time complexity , where denotes the size of the value range of the input data.
The following is a comparison of several sorting algorithms.
Space complexity
Like time complexity, space complexity describes the scale of an algorithm's space consumption. In general, the smaller the space complexity, the better the algorithm.