排序可分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，称为内排序；如果排序过程中需要使用外存，则成为外排序。 内排序有以下几类：
各种内部排序算法的比较
直接插入排序、气泡排序和简单选择排序是基本的排序方法。它们平均情况下的时间复杂度都是，它们的实现也都非常简单。 直接插入排序对于规模很小的元素序列。 改进的冒泡排序在最好情况下只需要一趟冒泡过程就可以完成，此时也只需要次比较就可以了。 简单选择排序的排序码比较次数与待排序元素序列的初始排列无关，其比较次数总是次。 从内存复杂度来看，这三种基本的排序方法除了一个辅助元素外，都不需要其他额外的内存空间。从稳定性来看，直接插入排序和冒泡排序都是稳定的，但简单选择排序不是。它们主要用于元素个数n不是很大的情形。 快速排序是最通用的高效的内部排序算法，平均情况下的时间复杂度为。改进的快速排序算法，即三路划分的快速排序算法，能够有效地避免最坏情况的发生。 堆排序也是一种高效的内部排序算法，它的时间复杂度是，而且没有什么最坏情况会导致堆排序的运行明显变慢，并且堆排序基本不需要额外的内存空间。但堆排序不太可能提供比快速排序更好的平均性能。堆排序是一种不稳定的排序算法。 归并排序也只一个重要的高效排序算法它的性能与输入元素序列无关，时间复杂度总是的附加内存空间，虽然有方法可以克服这个缺点，但是其代价是算法会很复杂且时间复杂度会增加，因此在实际应用中一般不值得这样做。归并排序算法是一种稳定的高效排序算法。 快速排序、堆排序和归并排序适合于元素个数n很大的情况。 希尔排序的时间复杂度介于基本排序算法和高效排序算法之间，虽然迄今为止对其性能的分析还是不精确的，但是希尔排序代码简单，基本不需要什么额外内存，空间复杂度低。希尔排序是一种不稳定的排序算法。对于中等规模的元素序列，希尔排序是一种很好的选择。 基数排序是一种相对特殊的排序算法，，这类算法不仅是对元素序列的排序码进行比较，更重要的是它们对排序码的不同部分进行处理和比较。虽然基数排序具有线性增长的时间复杂度，但是由于在常规编程环境中，关键字索引统计程序内部循环中包含大量操作，其数目比快速排序或者归并排序算法的内部循环多得多。所以基数排序的线性时间开销实际上不比快速排序的时间开销小很多。并且由于基数排序基于的排序码抽取算法受到操作系统和排序元素的影响，其适应性远不如普通的比较和交换操作。因此在实际工作中，常规的高效排序算法如快速排序的应用要比基数排序广泛得多。
排序方法 时间复杂度 空间复杂度 稳定性
直接插入排序 O(n2) O(1) 是
二分法插入排序 O(nlog2n) O(1) 是
希尔排序 – O(1) 否
简单选择排序 O(n2) O(1) 否
堆排序 O(nlog2n) O(1) 否
冒泡排序 O(n2) O(1) 是
快速排序 O(nlog2n) O(log2n) 否
归并排序 O(nlog2n) O(n) 是
基数排序 O(d(n+rd)) O(rd) 是
对于旅行，从来都记忆模糊。记不得都去了哪些地方，
