在内存里的排序称为内部排序，而在磁盘上的排序称为外部排序。
假设输入数据支持"<“和”>“操作符，除赋值运算外，这种运算是仅有的允许对输入数据进行的操作，在此条件下的排序称为基于比较的排序。
内容
对内部排序的考查将指出：
- 存在几种直观的算法以O(N^2)排序，如冒泡、选择、插入排序
- 希尔排序编程简单，以o(N^2)运行，在实践中很有效
- 还有一些稍微复杂的O(NlogN)算法
- 任何只使用比较的排序算法在最坏情形下和平均情形下均需要Ω(NlogN)次比较
插入排序 (insertion sort)
插入排序由N-1趟（pass）排序组成，排序策略是，在第p趟，将位置p上的元素向左移动至它在前p+1个元素中的正确位置上。
分析
O(N^2) 精确界，反序输入可达。
若已排序输入，则O(N)
平均情形Θ(N^2)
一些简单排序算法的下界
定理1 N个互异元素的数组的平均逆序数是N(N-1)/4
定理2 通过交换相邻元素进行排序的任何算法平均需要Ω(N^2)时间
对冒泡排序、选择排序、插入排序都有效
定理2告诉我们，为了以o(N^2)排序，必须执行比较，特别是要对相距较远的元素进行交换。排序通过删除逆序得以继续进行，为了有效进行，必须每次交换删除多个逆序。
希尔排序 (shell sort)
发明者是Donald Shell，该算法是冲破二次时间屏障的第一批算法之一，不过，直到它最初被发现的若干年后才证明了它的亚二次时间界。
它通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。因此，希尔排序又是也叫做缩减增量排序(diminishing increment sort)
分析
使用希尔增量的最坏情形Θ(N^2)
Hibbard增量：1，3，7，…… ，2^k - 1
使用Hibbard增量的最坏情形Θ(N^(3/2))
Sedgewick提出了几种增量序列，最坏情形时间O(N^(4/3))
希尔排序的性能在实践中是可以接受的，由于编程简单，适度数量的输入数据经常选用。
堆排序 (heap sort)
如第六章所说，优先队列可以用O(NlogN)时间进行排序，基于该思想的算法称为堆排序
由数组建立N个元素的二叉堆花费O(N)时间，每次deleteMin花费O(logN)，N次总共花费O(NlogN)
使用了附加数组，存储需求增加了一倍
避免使用附加数组的方法：每次deleteMin之后把min放到刚刚空出来的位置上，N次deleteMin之后，数组将是递减顺序，因此可以构建max堆
- 以O(N)建立max堆
- 交换最后一个和第一个元素，堆大小减1并下滤，相当于执行deleteMax
- 循环执行步骤2，N-1次
分析
在最坏情形下堆排序最多使用2NlogN-O(N)次比较
堆排序非常稳定：它平均使用的比较只比最坏情形界指出的略少
定理1 对N个互异项的随机排列进行堆排序，所用的比较平均次数为2NlogN-O(NloglogN)
可以证明，堆排序总是至少使用NlogN-O(N)次比较，而且存在达到这个界的数据。似乎平均情形也应该是2NlogN-O(N)次比较（而不是定理1中的第二项），但目前无法证明
归并排序 (merge sort)
以最坏情形O(NlogN)时间运行，所使用的比较次数几乎是最优的，它是递归算法的一个很好的实例
算法的基本操作是合并两个已排序的表，取两个输入A、B，一个输出C，每次将A、B中的小者放入C，相关的位置推进，这显然是线性的
算法
基准情形：N=1时，结果是显然的
否则，递归地将前半部分和后半部分各自归并排序，再将两部分合并
该算法是经典的分治策略，它将问题分(divide)成一些小问题然后递归求解，而治(conquering)的阶段则是将分的阶段解得的各答案合并在一起
分析
分析递归例程技巧的经典实例：必须给运行时间写出一个递推关系。
假设N是2的幂，从而总可以将它分裂成相等的两部分。对于N=1，所用时间是常数，将其记为1。则有
T(1) = 1
T(N) = 2T(N/2) + N
求解得 T(N) = NlogN + N = O(NlogN)
利弊：在java中比较耗时多于移动，因此在java中归并排序是一般目的排序的最佳选择；但在C++中，比较耗时少而复制对象代价很大，因此实践中不常用
快速排序 (quick sort)
快排是实践中最快的已知排序算法，平均运行时间是O(NlogN)，最坏情形是O(N^2)，但稍作努力就可避免。
通过将堆排序与快速排序结合，可以在堆排序O(NlogN)最坏运行时间下，得到几乎所有输入的最快运行时间。
快排也是分治的递归算法，排序数组S步骤如下：
- 若S中元素数是0或1，则返回
- 取S中任一元素v，称之为枢纽元(pivot)
- 将S-{v}（S中其余元素）划分成两个不相交的集合：S1={x∈S-{v}|x≤v}和S2={x∈S-{v}|x≥v}
- 返回{quickSort(S1),后跟v,继而quickSort(S2)}
第三步中划分的标准不是唯一的，因此这就成了设计决策。一部分好的实现方法是将这种情形尽可能有效地处理。直观地看，我们希望枢纽元能将元素对半分，一半在S1，另一半在S2。
选取枢纽元
- 一种典型的错误是将第一个元素选作枢纽元。若输入随机，那么这是可以接受的，但实际情况有很多预排序的序列，这样的分割是劣质的。类似的还有选取前2个元素的大者，这是一样的，不要使用。
- 一种安全的做法是随机选取枢纽元，但这取决于随机数生成器的质量，而且声称随机数的代价一般也是很昂贵的。
- 三数中值分割法
一组N个数的中值是第上取整(N/2)个最大的数。枢纽元的最好选择是数组的中值，但算出中值代价太高。一般的做法是选取左端、右端和中心位置上的三个元素的中值作为枢纽元。显然该方法消除了预排序输入的不好情形，并且减少了约14%的比较次数。
分割策略
- 将枢纽元与最后的元素交换
- i从第一个元素开始，j从倒数第二个元素开始
- 当i在j左边时，右移i，移过小于枢纽元的元素，j左移，移过大于枢纽元的元素，i,j都停止时交换两个元素，直到i,j交错
- 将枢纽元与i所指向的元素交换
如何处理等于枢纽元的元素？
若等于，则停止移动
小数组
对于很小的数组（N≤20），快速排序不如插入排序，而且，因为快排是递归的，这样的情形经常发生。通常的解决办法是，对于小数组使用插入排序。一种好的截止范围(cutoff range)是N=10
分析
最坏情形：O(N^2) 最佳情形：O(NlogN) 平均情形：O(NlogN)
快速选择 (quick select)
修改快速排序以解决选择问题，即找第k个最大（小）元。
前3步和快速排序一样
第4步
- 若k≤S1，那么k必然在S1中，返回quickSelect(S1, K)
- 若k = 1 + |S1|，那么枢纽元就是第k个最小元
- 否则，第k个最小元就在S2中，它是S2中的第（k-|S1|-1）个最小元，返回quickSelect(S2, k-|S1|-1)
分析
与快排相比，快速选择只进行了一次递归调用而不是两次
最坏情形：O(N^2)，当S1和S2一个是空时 平均情形：O(N)