1、排序的基本概念
内排序和外排序：如果待排序的个数较少，整个排序过程可分为两类。如果待排序的记录个数较少，整个排序过程中所有的记录都可以存放在内存中，这样的排序叫做内排序。如果待排序数量较大，内存无法容纳所有记录。在排序过程中还需访问外部内存，这样的排序叫做外排序。
算法的稳定性：如果存在多个具有相同排序码的记录，经过排序后这些记录的相对次序仍然保持不变，这种排序算法称为“稳定的”，否则称为“不稳定的”。
我们知道，排序的算法有很多，那么在特定的环境下该如何选择特定的排序算法呢？评价一种排序算法的好坏主要通过时间代价和空间代价来衡量，尤其是时间代价。如果有特殊的控价，则要注意采用辅助空间较小的算法。
算法的时间复杂度（平均时间代价）：排序算法的时间代价一般通过记录的总比较和总移动次数来衡量，一次移动就是一次记录赋值，一次swap交换为三次移动。记录的数量、排序码和记录的大小以及输入记录的原始有序程度都会影响到排序算法的相对运行时间。一般而言，所需时间越短的算法越好。但是，估算排序算法的时间代价时，需要分别考虑3种情况下的代价：最小时间代价（最好情况）、最大时间代价（最坏情况）、平均时间代价（平均情况）。当序列中不含重复记录时，一个长度为n的序列工业n!中排列。假定每种排列的出现都是等概率的，序列所有可能排序的平均运行时间为该算法的平均时间代价。
考虑到时间紧张，下面的算法的叙述形式，我将分为以下几个部分，算法思想，代码实现，算法的时空状态及稳定性分析。如果有时间的话，后面我将再去将各个排序算法进行分类，综合讨论比较。
2、直接插入排序
算法思想：通过线性搜索来确定待插入记录的位置。如果前面若干个记录排成了不减序列，则对已排序记录按照从大到小逐个与新纪录进行比较，直到找到第一个不大于新纪录的值，这就是新纪录应该插入的位置；依次把新纪录插入到逐步扩大的已排子序列中，直到最后完全排好序。
代码实现（cpp）：
template <class Record>
void InsertSort(Record Array[], int n){
Record tempRecord; //临时记录
int i, j;
for (i = 0; i < n; i++) { //依次插入第i个记录
tempRecord = Array[i];
j = i - 1;
//往前寻找记录i的正确位置
while (j >= 0 && tempRecord < Array[j]) {
Array[j + 1] = A[j]; //依次将大于i的元素后移
j = j-1; //下标j前移
}
}
Array[j + 1] = tempRecord; //此时j+1就是记录i的正确位置，回填
}
空间复杂度：算法用到了一个辅助存放待插入记录的临时变量，空间代价为一个记录大小，即O(1)
时间复杂度：数组正序排列时，每次第i个记录一进入内层循环就退出，迭代次数为0，比较次数为n-1；当前记录保存在临时变量中n-1次，回填n-1次，移动次数共为2(n-1)。因此最好情况O(n)。当数组恰好按照降序排列时，即正好与需要排列的顺序相反。每次在外层的第i次迭代都需要进行i次循环，比较i次；当前记录保存在临时变量发生一次移动，回填时发生一次移动，前面序列顺序向后移动i次，总共移动i+2次，故最差情况O(n^2),平均情况O(n^2)
算法稳定性：由于直接插入算法每次只与临近元素比较，直到找到第一个不大于新纪录的值停止。故算法是稳定的
适用性：直接插入排序适用于顺序存储和链式存储的线性表，采用链式存储时无需移动元素。
直接插入算法示例图：
2、shell排序
算法基本思想：shell排序通过分组来进行排序：先将待排序序列分为若干个子序列，而且要保证子序列中的记录在原始数组中不相邻，且间距相同，分别对这些小子序列进行插入排序；然后，减小记录间的间距，减少小序列个数，将原始序列分为更大、更有序的子序列，分别进行插入排序；重复进行下去，直至间距缩减为1，这是序列已基本有序，再对整个序列进行直接插入排序。
代码实现(C):（“增量”每次除以2递减的shell排序）
void ShellSort(ElemType A[], int n) {
int dk, i, j;
for (dk = n/2; dk >= 1; dk++) {
for (i = dk + 1; i <= n; i++)
if(A[i] < A[i - dk]) { //将A[i]插入到有序增量子表中
A[0] = A[i];
for (j = i - dk; j > 0 && A[0] < A[i]; j = j - dk)
A[j + dk] = A[j]; //记录后移，查找插入的位置
A[j + dk] = A[0];
}
}
}
空间复杂度：仅使用了常数个辅助单元，因而时间复杂度为O(1)。
时间复杂度：因为shell排序的时间复杂度依赖于增量序列的函数。在n的某个特定的范围，shell排序的时间复杂度约为O(n^1.3)。在最坏的情况下希尔排序的时间复杂度为O(n^2)。
稳定性：当相同关键字的记录被划分到不同的子表时，可能会改变他们的相同次序，因此shell排序是一种不稳定的算法。
适用性：shell排序适用于顺序存储的线性表。
3、简单选择排序
算法思想：逐个找出第i小的记录，并将这个记录与数组第i个位置的元素进行交换，第i小的记录一次交换到位。
代码实现(cpp):
template <class Record>
void SelectSort(Record Array[], int n) { //直接选择排序，Array[]为待排列数组，n为数组长度
int i, j, smallest;
for (i = 0; i < n - 1; i++) { //依次选出第i小的记录，即剩余记录中最小的那个
smallest = i;
for (j = i + 1; j < n; j++) { //开始向后扫描所有剩余记录
if (Array[j] < Array[smallest])
smallest = j; //如果发现更小的记录，记录它的位置
}
swap(Array, i, smallest); //第i小的记录到位
}
}
时间复杂度：直接选择排序总的时间代价仍为O(n^2)。算法不依赖于原始数组的输入顺序、因此最大、最小、平均时间代价都为O(n^2)。
空间复杂度：用到了交换操作，需要用到一个临时记录，因此空间复杂度为O(1)。
4、堆排序
算法思想：基于堆的排序主要有两种，最大堆和最小堆，这里介绍基于最大堆进行排序的算法。首先将存放在L[1...n]中的n个元素建成堆，因为堆本身的特点，所以堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大堆顶的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。
代码实现(C):
//首先建立大根堆
void BuildMaxHeap(ElemType A[], int len) {
for (int i = len/2; i > len; i++) { //从i=[n/2]~1,反复调整堆
HeadAdjust(A, i, len);
}
}
void HeadAdjust(ElemType A[], int k, int len) {
A[0] = A[k];
for (int i = 2*k; i <= len; i = i*2) { //沿key较大的子结点向下筛选
if (i < len && A[i] < A[i+1])
i++; //取key较大的子结点的下标
if (A[0] >= A[i]) break; //筛选结束
else{
A[k] = A[i]; //将A[i]调整到双亲结点上
k = i; //修改k值，继续向下
}
}
A[k] = A[0]; //被筛选结点的值放入最终位置
}
void HeapSort(ElemType A[], len) {
BuildMaxHeap(A, len); //初始建堆
for (int i = len; i > 1; i--) { //n -1趟建堆的交换和建堆的过程
Swap(A[i], A[1]); //输出堆顶元素
HeadAdjust(A, 1, i-1); //调整，把剩下的n-1个元素整理成堆
}
}
空间复杂度：仅使用常数个辅助单元，所以时间复杂度为O(1)。
时间复杂度：建堆时间为O(n)，之后有n-1次向下调整操作，每次调整的时间为O(h)，所以在最好、平均、最坏情况下，堆排序的时间复杂度为O(nlogn)。
稳定性：进行筛选时，有可能把后面相同的关键字调整到前面，所以堆排序是一种不稳定的排序算法。例如，表L = {1，2，2}，构建初始堆时可能将2交换到堆顶，此时L={2，1，2}，最终排序序列为L = {1，2，2}，显然2和2的位置已经发生交换。
适用性：堆排序仅适用于顺序存储的线性表。
下面给出堆排序的示意图，图中也可以明显看出堆排序不稳定的特点：
5、冒泡排序
算法思想：给定序列x1,x2...,xn，从后往前两两比较大小，将小的元素调整到序列前面，每次可选出一个最小元素，这样调整n-1次就可以将序列排好序。
代码实现(cpp)：
template <class record>
void BubbleSort(record Array[], int n) { //Array[]为待排序数组，n为数组长度
bool Noswap; //是否发生了交换的标志
for (int i = 0; i < n-1; i++) {
Noswap = true; //标志初始为真
for (int j = n - 1; j > i; j--) {
if (Array[j] < Array[j-]) { //判断Array[j]和Array[j-1]
swap(Array, j, j-1);
Noswap = false; //发生了交换标志变为假
}
}
}
if (Noswap) //如果没有发生交换，表明已经排好序
return;
}
空间复杂度：仅使用了常数个辅助单元，因而时间复杂度为O(1)
时间复杂度：当初始序列有序时，显然第一趟冒泡排序Noswap依然为true，从而直接跳出循环，比较次数为n-1，移动次数为0，从而最好情况下时间复杂度为O(n)；当初始序列为逆序时，需要进行n-1趟排序，第i趟排序要进行n-i次关键字的比较，而且每次比较后都必须移动3次来交换元素位置。这种情况下，比较次数=
6、快速排序
算法思想：通过一趟排序将待排序记录分割成的两部分，其中一部分记录的关键字比另一部分的关键字小，可分别对这两部分记录分别排序，以达到整个序列有序的目的。
template <class Record>
void QuickSort(Record Array[], int low, int high) {
//Partition()就是划分操作，将表A[low...high]划分为满足上述条件的两个子表
if (low < high) {
int Pivotpos = Partition(Array[], low, high);
QuickSort(Array[], low, Pivotpos - 1);
QuickSort(Array[], Pivotpos + 1, high)
}
}
void Partition(Array[], int low, int high) {
int pivot = Array[low]; //将表中的第一个元素设为枢轴，对标进行划分
while (low < high) {
while (low < high && Array[high] > pivot) high--;
//将比枢轴小的元素移到左端
Array[low] = Array[high];
while (low < high && Array[low] < pivot) low++;
//将比枢轴大的元素移到右端
Array[high] = Array[low];
}
Array[low] = pivot; //枢轴元素存放到最终位置
return low; //返回存放枢轴的最终位置
}
空间复杂度：由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为O(logn)；最坏情况下，需要进行n-1次递归调用，所以栈的深度为O(nlogn)；平均情况下，栈的深度为O(logn)。
时间效率：快速排序的运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含n-1个元素和0个元素时，这种最大程度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或者基本逆序时，就得到最坏情况下的时间复杂度O(n^2)。在最理想状态下 ，即Partition()做到最平衡的划分，得到的两个子问题的大小都不可能大于n/2，这种情况下，快速排序的时间复杂度为O(nlogn)。而快速排序的平均运行时间与最佳情况下运行时间接近，也为O(nlogn)。
稳定性：在划分算法中，若右端区间有两个关键字相同，且小于基准值的记录，则在他们交换到左端区间时，它们的相对位置发生变化，即快速排序是一种不稳定的排序算法。
7、归并排序
算法思想：
将多个有序表组合成一个新的有序表。这个算法我看了很多资料没有发现很好的解释，最简洁的话就是前面那句话。其实，和QuickSort一样，MergeSort也是一种基于分治法的排序。快速排序侧重于“分”，找枢轴量就成为了问题的关键。而归并排序更注重“治和合”，也就是对有序表合并的过程，而对“分”相对淡化。
我说一下代码实现的步骤吧，我是用二路归并实现的，首先开辟两个与序列等长数组空间，将序列复制到临时数组中，将数组从中间划分。每次从左右两端选出小的元素放入数组，直到左右两边其中某个子序列为空，剩余子序列的元素直接进入结果数组即可。
代码实现(cpp)：
//两路归并排序
template <class Record>
//Array为待排序数组，left、right分别为左右两端下标
void MergeSort(Record Array[], Record TemArray[], int left, int right) {
int middle;
if (left < right) { //如果序列中只有0、1个记录，就不用排序
middle = (left + right)/2; //从中间划分为两个序列
MergeSort(Array, TemArray, left, middle); //对左边一半进行递归
MergeSort(Array, TemArray, middle + 1, right); //对右边一半进行递归
Merge(Array, TemArray, left, right, middle); //进行合并
}
}
template <class Record>
void Merge(Record Array[], Record TemArray[], int left, int right, int middle) {
int i, j, index1, index2;
for (j = left; j <= right; j++) //将数组暂存进临时数组
TemArray[j] = Array[j];
index1 = left; //左边子序列的起始位置
index2 = middle + 1; //右边子序列的起始位置
i = left;
while (index1 <= middle && index2 <= right) {
//取较小者插入合并数组中
if (TemArray[index1] <= TemArray[index2]) //为保证稳定性，相等时左边优先
Array[i++] = TemArray[index1++];
else Array[i++] = TemArray[index2++];
}
while (index1 <= middle) //只剩左边序列，可以直接复制
Array[i++] = TemArray[index1++];
while (index2 <= right) //与上个循环互斥，直接复制剩余的右序列
Array[i++] = TemArray[idnex2++];
}
空间复杂度:归并过程需要用到一个临时数组来保存原序列数组，因此归并排序的空间代价为O(n)。
时间复杂度：O(nlogn)
稳定性：if (TemArray[index1] <= TemArray[index2])算法实现过程中，规避了交换序列元素原有相对顺序的可能。
