排序的基本概念与分类
假设含有n个记录的序列为{r1 , r2 , … rn}，其相应的关键字分别为{k1 , k2 , … kn}，需确定1, 2, … n的一种排列p1 , p2 … pn ，使其相应的关键字满足kp1<=kp2 … kpn ，非递减（非递增）关系，即使得序列称为一个按关键字有序的序列{rp1 , rp2 … rpn}，这样的操作就称为排序。
排序的稳定性
假设ki = kj (1<=i<=n, 1<=j<=n, i≠j)，且在排序前的序列中ri 领先于rj(即i<j)。如果排序后ri 仍领先于rj ，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中rj 领先于ri ，则称所用的排序方法是不稳定的。
内排序与外排序
内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序时由于排序的记录个数太多，不能同时放置在内存中，整个排序过程需要在内外存之间多次交换数据才能进行。（这里主要介绍内排序）
对内排序来说，排序算法的性能主要受三个方面影响：
（1）时间性能，即高效的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。
（2）辅助空间
（3）算法复杂度
根据排序过程中借助的主要操作，把内排序分为插入排序、交换排序、选择排序和归并排序。
排序用到的结构与函数
仅作示例：
#define MAXSIZE 10000
typedef struct
{
int r[MAXSIZE];
int length;
}SqList;
void swap(SqList *L, int i, int j)
{
int temp = L->r[i];
L->r[i] = L->r[j];
l->r[j] = temp;
}
冒泡排序
冒泡排序(Bubble Sort)是一种交换排序，它的基本思路时：两两比较相邻记录的关键字，如果反序则交换，知道没有反序的记录为止。
//初级版
void BubbleSort(SqList *L)
{
for(int i = 0; i < L->length; i++)
{
for(int j = i + 1; j <= L->length; j++)
{
if(L->r[i] > L->r[j])
{
swap(L, i, j);
}
}
}
}
void BubbleSort1(SqList *L)
{
for(int i = 0; i < L->length; i++)
{
for(int j = L->length - 1; j >= i; j--)
{
if(L->r[j] > L->r[j + 1])
{
swap(L, j, j + 1);
}
}
}
}
//改进
void BubbleSort2(SqList *L)
{
int flag = 1;//标记目前是否已经有序
for(int i = 0; i < L->length && flag; i++)
{
flag = 0;
for(int j = length - 1; j >= i; j--)
{
if(L->r[j] > L->[j + 1])
{
swap(L, j, j + 1);
flag = 1;
}
}
}
}
算法复杂度为O(n2)。
简单选择排序
简单选择排序(Simple Selection Sort)就是通过n - i次关键字间的比较，从n - i + 1个记录中选出关键字的最小记录，并和第i(1<=i<=n)个记录交换。
void SelectSort(SqList *L)
{
int min;
for(int i = 0; i < L->length; i++)
{
min = i;
for(int j = i + 1; j < L->length; j ++)
{
if(L->r[min] > L->r[j])
min = j;
}
if( i != min)
swap(L, i, min);
}
}
其时间复杂度为O(n2)，但其性能会略优于冒泡排序。
直接插入排序
直接插入排序(Straight Insertion Sort)的基本操作时将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录增1的有序表。
void InsertSort(SqList *L)
{
for(int i = 1; i < L->length; i++)
{
if(L->r[i] < L->r[i - 1])
{
int temp = L->r[i];
for(int j = i - 1; L->r[j] > temp && j >= 0; j--)
L->r[j + 1] = L->r[j];
L->r[j + 1] = num;//j已经自减
}
}
}
其时间复杂度为O(n2)，但比冒泡和简单选择排序的性能要略好一些。
希尔排序
希尔排序(Shell Sort)。将相距某个“增量”的记录组成一个子序列，然后在这些子序列内分别进行直接插入排序（其在原本的大序列中的位置不变），当整个序列都基本有序时，再对全体记录进行直接排序。
基本有序：就是小的关键字基本在前，大的基本在后，不大不小排中间，像{2, 1,3, 6, 4, 7, 5, 8, 9}就可以称为基本有序。
void ShellSort(SqList *L)
{
int k = 0;
int increment = L->length;
do
{
increment = increment / 3 + 1;
for(int i = increment; i < L->length; i++)
{
if(L->r[i] < L->[i - increment])
{
int temp = L->r[i];
for(int j = i - increment; j > 0 && temp < L->r[j]; j -= increment)
L->r[j + increment] = L->[j];
L->r[j + increment] = temp;
}
}
}
while(increment > 1)
//使用do...while循环会多一次increment=0的直接插入排序，也就是最后对整个序列进行的直接插入排序
}
可以看出该算法中的增量increment是其时间复杂度大小的关键。大量研究表明，当增量序列为dlta[k]=2t-k+1 -1（0≤k≤t≤?log2(n+1)?）时，可以获得不错的效率，其时间复杂度为O(n2/3)。
由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法。
堆排序
堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子的值，称为大顶堆；或每个结点的值都小于或等于其左右孩子的值，称为为小顶堆。
根结点一定是堆中所有结点最大（小）者。较大（小）的结点靠近根结点（但不绝对）。按照层序遍历的方式给结点从1开始编号，则结点之间满足如下关系：Ki >=K2i && Ki >=K2i+1 或Ki <=K2i && Ki <=K2i+1 (1 <= i <= [n/2]) 
堆排序算法（大顶堆）
将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是顶堆的根结点。将它与堆数组的末尾元素交换，然后将剩余的n-1个序列重新构造成一个堆，再将当前根结点与剩余序列的最后一个元素进行交换。如此反复执行，便能得到一个有序序列。
void HeapSort(SqList *L)
{
for(int i = L->length / 2; i > 0; i--)//把r构建成一个大顶堆
HeapAdjust(L, i, L->length);
for(int i = L->length; i > 1; i--)
{
swap(L, 1, i);
HeapAdjust(L, 1, i - 1);
//只是将根结点与末尾结点交换，所以只需要将根结点再次调整为大顶堆，无需每个结点都进行调整
}
}
void HeadAdjust(SqList *L, int s, int m)
{
int temp;
temp = L->r[s];
for(int j = 2 * s; j <= m; j *= 2)//沿左孩子往下筛选
{
if(j < m && L->r[j] < L->r[j + 1])//若右孩子较大，将j指向右孩子
++j;
if(temp >= L->r[j])//当前根结点值已经最大，终止循环
break;
L->r[s] = L->r[j];//调整根结点的值
s = j;//更新根结点s。
}
L->r[s] = temp;
//因为s=j后，temp可能还是比目前位置s左右孩子小，仍需要为temp找个合适的位置，所以将temp的赋值放在循环外，此时s的位置即temp合适的位置。
}
（1）第一个循环要将现在的待排序序列构成一个大顶堆。第二个循环逐步将每个最大值的根结点与末尾元素交换，并且调整其称为大顶堆。
（2）第一个循环第一个构建大顶堆，其实就是从下到上、从右到左，将每一个非终端结点（非叶节点）当作根结点，将其和其子树调整成大顶堆。
（3）第二个循环中，每次交换只改变了根结点的值，所以只需要对根结点再构建一次大顶堆即可。
堆排序中，整个构建堆的时间复杂度为O(n)，正式排序时，重建堆的时间复杂度为O(nlogn)。由于堆对原始记录的排序状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。总体来说，其时间复杂度为O(nlogn)。
归并排序
归并排序(Merging Sort)。其原理是假设初始序列含有n个记录，则可以看成是你n个有序的子序列，每个子序列长度为1，然后两两归并，得到[n/2] ([x]表示不小于x的最小整数)个长度为2或1的有序子序列；再两两归并，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。
void MergeSort(SqList *L)
{
MSort(L->r, L->r, 1, L->length);
}
void MSort(int SR[], int TR1[], int s, int t)
{
int m;
int TR2[MAXSIZE + 1];
if(s == t)//递归终止条件，此时即将元素存入TR1，然后返回上一个循环
TR1[s] = SR[s];
else
{
m = (s + t) / 2;
MSort(SR, TR2, s, m);//拆分数组，mid前
MSort(SR, TR2, m + 1, t);//拆分数组，mid后
Merge(TR2, TR1, s, m, t);//对TR2[]进行归并排序
}
}
void Merge(int SR[], int TR[], int i, int m, int n)//i为起始，m为中点，n为末尾
{
//SR[]为待归并数组，TR[]为目标数组
int j, k, l;
for(j = m + 1, k = i; i <= m && j <= n; k++)
{
if(SR[i] < SR[j])//比较待归并的两数组元素的大小，然后存入目标数组
TR[k] = SR[i++];
else
TR[k] = SR[j++];
}
if(i <= m)//有多余元素，将SR[i...m]复制到TR[]
{
for(l = 0; l <= m - i; l++)
TR[k + l] = SR[i + l];
}
if(j <= n)//有多余元素，将SR[j...n]复制到TR[]
{
for(l = 0; l <= n - j; l++)
TR[k + l] = SR[j + l];
}
}
归并排序是一种稳定的排序算法。其时间复杂度为O(nlogn)，空间复杂度为O(n+nlogn)。也就是说，归并排序是一种比较占内存，但效率较高且稳定的算法。
非递归实现归并排序
void MergeSort2(SqList *L)
{
int* TR = (int*)malloc(L->length * sizeof(int));
int k = 1;
while(k < L->length)
{
MergePass(L->r, TR, k, L->length);//由L->r归并到TR中
k = 2 * k;//子序列长度加倍
MergePass(TR, L->r, k, L->length);//再由TR归并到L->r中
k = 2 * k;
}
}
void MergePass(int SR[], int TR[], int s, int n)//SR归并进入TR
{
int i = 1;
int j;
while(i <= n - 2 * s + 1)
{
Merge(SR, TR, i, i + s - 1, i + 2 * s - 1);
i = i + 2 * s;
}
if(i < n - s + 1)//归并最后两个序列（即序列尾可能有多余的数无法归并，在此再进行一次归并）
Merge(SR, TR, i, i + s - 1, n);//（有多余数的情况下，最后一次i将等于1所以一定会有满足条件）
else//将序列末尾多出来的元素加入TR中
for(j = i; j <= n; j++)
TR[j] = SR[j];
}
void Merge(int SR[], int TR[], int i, int m, int n)
{
int j, k, l;
for(j = m + 1, k = i; i <= m && j <= n; k++)
{
if(SR[i] < SR[j])
TR[k] = SR[i++];
else
TR[k] = SR[j++];
}
if(i <= m)
{
for(l = 0; l <= m - i; l++)
TR[k + l] = SR[i + l];
}
if(j <= n)
{
for(l = 0; l <= n - j; l++)
TR[k + l] = SR[j + l];
}
}
非递归的迭代方法，避免了递归时深度为log2n的栈空间，空间只是用到申请归并时用的TR数组，因此空间复杂度为O(n)，并且避免递归也在时间性能上有一定的提升，应该说，使用归并排序时，尽量考虑用非递归方法。
快速排序
快速排序(Quick Sort)的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一本部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
void QuickSort(SqList* L)
{
QSort(L, 1, L->length);
}
void QSort(SqList *L, int low, int high)
{
int pivot;
if(low < high)
{
pivot = Partition(L, low, high);//算出枢值pivot，然后将数组分为以枢值分为两部分
QSort(L, low. pivot - 1);//对低子表排序
QSort(L, pivot + 1, high);//对高子表排序
}
}
int Partition(SqList *L, int low, int high)
{
int pivotkey;
pivotkey = L->r[low];//将数组第一个值记录为枢值
while(low < high)//从数组两头开始扫描，更新枢值的位置
{
while(low < high && L->r[high] >= pivotkey)//寻找枢值右侧比他小的值
high--;
swap(L, low, high);
while(low < high && L->r[low] <= pivotkey)//寻找枢值左侧比他大的值
low++;
swap(L, low, high);
}
return low;//返回枢值所在的位置
}
以数组{50, 10, 90, 30, 70, 40, 80, 60, 20}为例：
Partition函数要做的就是，先选取当中的一个关键字，然后把它放到一个位置，使得它左边的值都比他小，它右边的值都比他大，把这样的关键字称为枢轴(pivot)。
快速排序是一种不稳定的排序算法。其时间复杂度为O(nlogn)；空间复杂度最好的情况为O(logn)，最坏的情况为O(n)，平均为O(longn)。
优化
- 优化选取枢轴
Partition函数选取枢值，是影响快速排序算法的因素之一，总是固定选取第一个关键字作为首个枢轴实际上是不太合理的办法。
为了优化，先是有了随机选取枢轴法，但是其随机性很大，随之产生了三数取中法：即取三个关键字先进行排序，将数组中间数作为枢轴，一般是取左端、右端和中间三个数，也可以随机选取。
int pivotkey;
int m = low + (high - low) / 2;
if(L->r[low] > L->r[high])
swap(L, low, high);
if(L->r[m] > L->r[high])
swap(L, m, high);
if(L->r[m] > L->r[low])
swap(L, m, low);
pivotkey = L->[low];
有时候对于非常大的待排序列来说还是不足以保证能够选择出一个好的pivotkey，因此还有一个办法是九数取中法。
- 优化不必要的交换
在排序过程中，实际上pivotkey的位置有很多不必要的交换。可以对此进行优化：
int Partition(SqList *L, int low, int high)
{
int pivotkey;
if(L->r[low] > L->r[high])
swap(L, low, high);
if(L->r[m] > L->r[high])
swap(L, m, high);
if(L->r[m] > L->r[low])
swap(L, m, low);
pivotkey = L->r[low];
int temp = pivotkey;//将枢轴关键字备份
while(low < high)
{
while(low < high && L->r[high] >= pivotkey)
high--;
L->r[low] = L->r[high];//采用替换的方式更新数组，而不是交换
while(low < high && L->r[low] <= pivotkey)
low++;
L->r[high] = L->r[low];
}
L->r[low] = temp;
return low;
}
实际上就是把原先的所有swap函数改为“替换”，在最后找到了枢轴的位置，在将temp赋值回L->r[low]。
- 优化小数组时的排序方案
面对待排序序列长度极小时，该算法的优势也几乎不存在，此时对QSort函数进行稍稍改进：
#define MAX_LENGTH_SORT 7//用于快速排序时判断是否选用插入排序的阈值
void QSort(SqList *L, int low, int high)
{
int pivot;
if((high - low) > MAX_LENGTH_SORT)
{
pivot = Partition(L, low, high);
QSort(L, low. pivot - 1);
QSort(L, pivot + 1, high);
}
else
InsertSort(L);
}
(也有认为50作为阈值较为合理的，这里选用7作为阈值)
- 优化递归操作
在算法中，递归对性能是有一定影响的，QSort()函数在其尾部有两次递归操作。如果待排序的序列划分极端不平衡，递归深度将趋近于n，而不是平衡时的log2 n，这不仅是效率问题，还会使得耗费的栈空间增加。因此如果能减少递归，将会大大提高性能。
于是对QSort()实施尾递归优化：
#define MAX_LENGTH_SORT 7//
void QSort(SqList *L, int low, int high)
{
int pivot;
if((high - low) > MAX_LENGTH_SORT)
{
while(low < high)
{
pivot = Partition(L, low, high);
QSort(L, low. pivot - 1);//对低子表排序
low = pivot + 1;//尾递归
}
}
else
InsertSort(L);
}
在if中增加一个while，因为low在完成第一次递归以后就没有用处了，所以可以将pivot+1赋值给low，再循环后，再来一次Partition()，其效果等同于原来的第二次递归。这里利用迭代来减少一次递归的方法可以缩减堆栈深度，从而提高整体性能。