常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

1. 冒泡排序（Bubble Sort）：比较相邻的元素，如果前面的元素大于后面的元素，就交换这两个元素的位置。时间复杂度为O(n^2)。
2. 选择排序（Selection Sort）：在未排序的数据中找到最小（大）的元素，放置在已排序的数据末尾。时间复杂度为O(n^2)。
3. 插入排序（Insertion Sort）：将未排序的元素插入到已排序的序列中，时间复杂度为O(n^2)。
4. 希尔排序（Shell Sort）：希尔排序是插入排序的一种改进，它将原序列分割成若干个子序列，对每个子序列进行插入排序，最后对整个序列进行插入排序。时间复杂度为O(nlogn)。
5. 二路归并排序（Merge Sort）：二路归并排序是指将一个序列分成两个子序列，分别对两个子序列进行归并排序，然后将排序好的两个子序列合并成一个有序序列的过程。这种排序思想采用了分治算法的思想，排序效率较高，时间复杂度为 O(nlogn)。
6. 快速排序（Quick Sort）：选择一个基准元素，将大于基准元素的数放在一边，小于基准元素的数放在另一边，递归执行该过程，最后得到有序序列。时间复杂度为O(nlogn)。
7. 堆排序（Heap Sort）：将序列转换为一个大根堆，每次将堆顶元素与堆底元素交换，然后将剩余元素重新构建堆，重复执行该过程，最后得到有序序列。时间复杂度为O(nlogn)。
8. 计数排序（Counting Sort）：统计小于等于每个元素的个数，再依次计算出每个元素在有序序列中的位置。时间复杂度为O(n+k)，其中k为最大元素值。
9. 桶排序（Bucket Sort）：将元素分到多个桶中，对每个桶进行排序，最后将所有桶中的元素按顺序合并起来。时间复杂度为O(n)。
10. 基数排序（Radix Sort）：按照低位到高位的顺序对元素进行排序，依次排序后得到有序序列。时间复杂度为O(dn)，其中d为元素的位数。

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。

在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n^2)。在归并排序、快速排序之类的排序中问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

计数排序、基数非序、桶排序则属于非比较排序，非比较排序是通过确定每个元索之前，应该有多少个元素来排序，针对数组arr，计算arr之前有多少个元素，则唯一确定了arr在排序后数组中的位置。

非比较排序只要确定每个元索之前的已有的元案个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。非比较排序时间复杂度低，但由于非比较排序需要占用空间来确定唯一位置，所以对数据规模和数据分布有一定的要求.

基本的术语

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。

不稳定：如果a原本在b的前面，而a=b，排序之后a可能出现在b的后面。

内排序：所有的排序操作都在内存中完成。

外排序：由于数据大大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行

时间复杂度：一个算法执行所消耗的时间;

空间复杂度：运行完一个程序所需内存的大小

算法复杂度