所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。
排序是数据处理中经常使用的一种重要运算。在计算机及其应用系统中，花费在排序上的时间在系统运行时间中占有很大比重，并且排序本身对推动算法分析的发展也起很大作用。目前已有上百种排序方法，但并没有一个万能的排序方法来解决所有问题，接下来介绍几种常用的排序方法，并对它们进行分析和比较。
1．按是否涉及数据的内、外存交换
内排序
在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序。
外排序
若排序过程中要进行数据的内、外存交换，则称之为外部排序。
2．按策略划分内部排序方法
插入排序
选择排序
交换排序
归并排序
分配排序
评价排序算法好坏的标准主要有两条：
执行时间和所需的辅助空间
算法本身的复杂程度
排序算法的时间复杂度：
大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。
排序算法的空间复杂度：
若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序(In-PlaceSou)。非就地排序一般要求的辅助空间为O(n)。
插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。
常用的插入排序：直接插入排序 和希尔排序。
1.直接插入排序
排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
时间复杂度为O（n^2），空间复杂度为O（1），稳定的。
伪码：
2.希尔排序
希尔排序（Shell Sort）又称为“缩小增量排序”。是1959年由D.L.Shell提出来的。该方法先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。
在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
希尔排序是不稳定的。
交换排序是通过两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。
应用交换排序基本思想的主要排序方法有：冒泡排序和快速排序。
1.冒泡排序
将被排序的记录数组S[1..n]垂直排列，每个记录s[i]看作是重量为s[i]的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组s：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
平均时间复杂度为O（n^2），空间复杂度为O（1），由于是交换式的所以稳定。
代码：
2.快速排序
设当前待排序的无序区为S[low..high]，利用分治法可将快速排序的基本思想描述为：
①分解：
在S[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间S[low..pivotpos-1)和S[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。
注意：
划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=S[pivotpos])：
S[low..pivotpos-1].keys≤S[pivotpos].key≤S[pivotpos+1..high].keys
其中low≤pivotpos≤high。
②求解：
通过递归调用快速排序对左、右子区间S[low..pivotpos-1]和S[pivotpos+1..high]快速排序。
③组合：
因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。
在当前无序区中选取划分的基准关键字是决定算法性能的关键。
由于快速排序的交换思想，可知它是不稳定的。
它的平均复杂度可以计算出为O（nlogn），空间复杂度为O（1）。
选择排序通过每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。
常用的选择排序方法有直接选择排序和堆排序。
1.直接选择排序
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
在无序区S[1..n]中选出关键字最小的记录S[k]，将它与无序区的第1个记录S[1]交换，使S[1..1]和S[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。第i趟排序开始时，当前有序区和无序区分别为S[1..i-1]和S[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录S[k]，将它与无序区的第1个记录S[i]交换，使S[1..i]和S[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
平均时间复杂度为O(n^2)，空间复杂度为O（1）。
由于这个选择的关系，有可能会把相同元素的相对位置改变，故为不稳定的。
2.堆排序
1.堆的定义
n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤
)
2.堆的分类
堆可分为大根堆和小根堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。
3.基本思想
通常堆是通过一维数组来实现的。在起始数组为 0 的情形中：
堆的根节点（即堆积树的最大值）存放在数组位置 1 的地方;
注意：不使用位置 0，否则左子树永远为 0[2]
父节点i的左子节点在位置 (2*i);
父节点i的右子节点在位置 (2*i+1);
子节点i的父节点在位置 floor(i/2);
在堆的数据结构中，堆中的最大值总是位于根节点。堆中定义以下几种操作：
最大堆调整（Max_Heapify）：将堆的末端子结点作调整，使得子结点永远小于父结点
创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根结点，并做最大堆调整的递归运算
4.算法复杂度
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1)，它是不稳定的排序方法。
代码:
归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。
1、算法基本思路
设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。
（1）合并过程
合并过程中，设置i，j和p三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1[p]中，然后将被复制记录的指针i或j加1，以及指向复制位置的指针p加1。
重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子文件中剩余记录依次复制到R1中即可。
（2）动态申请R1
实现时，R1是动态申请的，因为申请的空间可能很大，故须加入申请空间是否成功的处理。
平均时间复杂度为O（nlogn），空间复杂度为O（n），稳定的。
代码：
分配排序的基本思想：排序过程无须比较关键字，而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶：O(n)。
分配排序包括桶排序和基数排序。
1.桶排序
桶排序(Bucket Sort)，其基本思想是：设置若干个桶，依次扫描待排序的记录R[0]，R[1]，…，R[n-1]，把关键字等于k的记录全都装入到第k个桶里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。
箱子的个数取决于关键字的取值范围。
桶排序的平均时间复杂度是线性的，即O(n)。但最坏情况仍有可能是O(n^2)。空间复杂度为O（m+n）。（m为每个桶的值域）
2.基数排序
基数排序(Radix Sort)是当每个桶的值域区间很大时对桶排序的改进。
将一个记录的值即排序码拆分为多个部分来进行比较。例如如果要对0~9999之间的整数进行排序，可以先按照千位数字进行桶排序，将所有数字分配到10个桶中，接下来，继续按照桶排序的方法对百位、十位、个位进行排序，这样，可以完成排序。这种将排序码拆分为多个字码分别来进行排序的方法就是基数排序。
本文转自cococo点点博客园博客，原文链接：http://www.cnblogs.com/coder2012/archive/2013/05/26/3088242.html，如需转载请自行联系原作者