整理定义

复述展开

算法对比分析

常见的快速排序、归并排序、堆排序以及冒泡排序等都属于比较类排序算法。比较类排序是通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。在冒泡排序之类的排序中，问题规模为 n，又因为需要比较 n 次，所以平均时间复杂度为 O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为 logn 次，所以时间复杂度平均 O(nlogn)。

比较类排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

而计数排序、基数排序、桶排序则属于非比较类排序算法。非比较排序不通过比较来决定元素间的相对次序，而是通过确定每个元素之前，应该有多少个元素来排序。由于它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度 O(n)。

非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

算法对比总结

说明：

稳定的排序算法按照元素在输入中出现的相同顺序对相等的元素进行排序。如果一个算法具备稳定性，那么在排序之后，如果两个元素相等，排序结果能够相同元素的原始的排列顺序。
排序方式中，in-place 表示可以在已有空间中使用，out-place 表示需要额外的空间进行存储中间数据。

→ 十大排序算法超级链接 →

理解体会

排序算法可以算是计算机科学与技术的基础入门知识，也是在面试中常见的提醒。掌握十大排序算法可以说是面试做题的基础的基础了。在掌握算法各大原理之余，还需要掌握各个算法之间的时间复杂度以及空间复杂度，以及各个算法的排序方式和稳定性。可以在算法对比总结表中查看。
面试过程中，很多时候，简单的算法是决定面试结果的重要因素。试想，如果练如此基础的算法都无法掌握的话，那如何去使用和改进更复杂的算法呢？所以，在学习算法过程中，还需要自己实地去使用代码编写逻辑，知道原理，也知道如果用代码解决算法问题。