分类 Classification

排序算法通常分类为：Sorting algorithms are often classified by

1. Computational complexity (worst, average and best hehavior) in terms of the size of the list (n). For typical serial sorting algorithms good behavior is O(n log n), with parallel sort in O(log^2 n), and bad behavior is O(n^2). (See Big O notation.) Ideal behavior for a serial sort is O(n), but this is not possible in the average case. Optimal parallel sorting is O(log n). Comparison-based sorting algorithms need at least O(n log n) comparisons for most inputs.根据列表（n）的大小计算复杂度（最差、平均和最佳表现）。对于典型的串行排序算法，良好的行为是O（n log n），在O（log 2 n）中并行排序，不良行为为O（n 2）。（见Big O符号）。串行排序的理想行为是O（n），但在平均情况下是不可能的。最优并行排序为O（log n）。基于比较的排序算法对于大多数输入需要至少O（n log n）比较。

2. Computational complexity of swaps (for "in-place" algorithms).互换的计算复杂度（适用于“就地”算法）。

3. Memory usage (and use of other computer resources). In particular, some sorting algorithms ar "in place". Strictly, an in-place sort needs only O(1) memory beyond the items being sorted; sometimes O(log(n)) additional memory is considered "in-place".内存使用（和其他计算机资源的使用）。特别地，一些排序算法是“ 就地 ”的。严格地说，就地排序只需要O（1）个内存，超出被排序的项目; 有时O（log（n））附加内存被认为是“就地”。

4. Recursion. Some algorithms are either recursive or non-recursive, while others may be both (e.g., mergo sort).递归。一些算法是递归的或非递归的，而其他算法可能都是（例如，合并排序）。

5. Stability: stable sorting algorithms maintain the relative order of records with equal keys(i.e., values).稳定性：稳定的排序算法保持具有相等键（即值）的记录的相对顺序。

6. Whether or not they are a comparison sort. A comparison sort examines the data only by comparing two elements with a comparison operator.他们是否是比较排序。比较排序仅通过将两个元素与比较运算符进行比较来检查数据。

7. General method: insertion, exchange, selection, merging, etc. Exchange sorts include bubble sort and quicksort. Selection sorts include shaker sort and heapsort. Also whether the algorithm is serial or parallel. The remainder of this discussion almost exclusively concentrates upon serial algorithms and assumes serial operation.一般方法：插入，交换，选择，合并等。交换类型包括气泡排序和快速排序。选择种类包括振动筛分类和堆肥。还有算法是串行还是并行。本讨论的其余部分几乎完全集中在串行算法上，并假设串行操作。

8. Adaptability: Whether or not the presortedness of the input affects the running time. Algorithms that take this into account are known to be adaptive.适应性：输入的预处理是否影响运行时间。已经考虑到这一点的算法是自适应的。