1.冒泡排序
平均时间复杂度：O(n^2)
最好情况：O(n)
最坏情况：O(n^2)
空间复杂度：O(1)
排序方式：In-place
稳定性：稳定
2.选择排序
平均时间复杂度：O(n^2)
最好情况：O(n^2)
最坏情况：O(n^2)
空间复杂度：O(1)
排序方式：In-place
稳定性：不稳定
3.插入排序
平均时间复杂度：O(n^2)
最好情况：O(n)
最坏情况：O(n^2)
空间复杂度：O(1)
排序方式：In-place
稳定性：稳定
4.希尔排序
平均时间复杂度：O(nlogn)
最好情况：O(nlog^2n)
最坏情况：O(nlog^2n)
空间复杂度：O(1)
排序方式：In-place
稳定性：不稳定
5.归并排序（分治法）
平均时间复杂度：O(nlogn)
最好情况：O(nlogn)
最坏情况：O(nlogn)
空间复杂度：O(n)
排序方式：Out-place
稳定性：稳定
6.快速排序（分治法）
平均时间复杂度：O(nlogn)
最好情况：O(nlogn)
最坏情况：O(n^2)
空间复杂度：O(logn)
排序方式：In-place
稳定性：不稳定
7.堆排序
平均时间复杂度：O(nlogn)
最好情况：O(nlogn)
最坏情况：O(nlogn)
空间复杂度：O(1)
排序方式：In-place
稳定性：不稳定
8.基数排序
平均时间复杂度：O(n*k)
最好情况：O(n*k)
最坏情况：O(n*k)
空间复杂度：O(n+k)
排序方式：Out-place
稳定性：稳定
直接插入排序（straight insertion sort）是插入排序中最简单的排序方法，类似于玩纸牌时整理手中纸牌的过程。其基本思想是：依次将待排序序列中的每一个记录插入到一个已排好序的序列中，直到全部记录都排好序。
void InsertSort(int r[], int n) {//0号单元用作暂存单元和监视哨
for (i = 2; i <= n; i++) {
r[0] = r[i]; //暂存待插关键码，设置哨兵
for (j = i-1; r[0] < r[j]; j--)//寻找插入位置
r[j+1] = r[j]; //记录后移
r[j+1] = r[0];
}
}
希尔排序的基本思想是：先将整个待排序记录序列分割成若干个子序列，在子序列内分别进行插入排序，待整个排序基本有序时，再对全体记录进行一次直接插入排序。
void ShellSort(int r[], int n) { //0号单元用作暂存单元
for (d = n/2; d >= 1; d = d/2) { //以增量为d进行直接插入排序
for (i = d+1; i <= n; i++) {
r[0] = r[i];//暂存被插入记录
for (j = i - d; j > 0 && r[0] < r[j]; j = j - d)
r[j+d] = r[j]; //记录后移d个位置
r[j+d] = r[0];
}
}
}
起泡排序（bubble sort）是交换排序中最简单的排序方法，其基本思想是：在待排序序列中选两个记录，将它们的关键码进行比较，如果反序则交换，直到没有反序的记录为止。
void BubbleSort(int r[], int n) //0号单元用作交换操作的暂存单元
{
exchange = n; //第一趟起泡排序的区间是[1, n]
while(exchange != 0)//当上一趟排序有记录交换时
{
bound = exchange;
exchange = 0;
for (j = 1; j < bound; j++)//一趟起泡排序，排序区间是[1, bound]
if (r[j] > r[j+1]) { //
r[j]<-->r[j+1]
exchange = j; //记载每一次记录交换的位置
}
}
}
快速排序(quick sort)是对起泡排序的一种改进，改进的着眼点事：在起泡排序中，记录的比较和移动是在相邻位置进行的，记录每次交换只能后移一个位置，因而总的比较次数和移动次数较多。在快速排序中，记录的比较和移动是从两端向中间进行的，关键码较大的记录一次就能从前面移动到后面，关键码较小的记录一次就能从后面移动到前面，记录移动的距离较远，从而减少了总的比较次数和移动次数。
伪代码：
1.将i和j分别指向待划分区间的最左侧记录和最右侧记录的位置；
2.重复下述过程，直到i=j
2.1 右侧扫描，直到记录j的关键码小于轴值记录的关键码；
2.2 如果存在划分区间，则将r[j]与r[i]交换，并执行i++；
2.3 左侧扫描，直到记录i的关键码大于轴值记录的关键码；
2.4 如果存在划分区间，则将r[i]与r[j]交换，并执行j--；
3. 退出循环，说明i和j指向了轴值记录的所在位置，返回该位置；
快速排序一次划分算法Partition
int Partition(int r[], int first, int end)
{
i = first; j = end; //初始化
while (i < j)
{
while (i<j && r[i] <= r[j]) j--; //右侧扫描
if (i < j) {
r[i]<-->r[j]; //将较小记录交换到前面
i++;
}
while (i<j && r[i] <= r[j]) i++; //左侧扫描
if (i < j) {
r[j]<-->r[i]; //将较大记录交换到后面
j--;
}
}
return i; //i为轴值记录的最终位置
}
对待排序序列进行一次划分之后，再分别对左右两个子序列进行快速排序，以此类推，直到每个分区都只有一个记录为止。
void QuickSort(int r[], int first, int end)
{
if (first < end) { //区间长度大于1，执行一次划分，否则递归结束
pivot = Partition(r, first, end);//一次划分
QuickSort(r, first, pivot-1);//递归地对左侧子序列进行快速排序
QuickSort(r, pivot+1, end);//递归地对右侧子序列进行快速排序
}
}
简单选择排序（simple selection sort）是选择排序中最简单的排序方法，其基本思想是：第i趟排序在待排序序列r[i]~r[n](1<=i<=n-1)中选取关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。
void SelectSort(int r[], int n) //0号单元用作变换操作的暂存单元
{
for (i = 1; i < n; i++) //对n个记录进行n-1趟简单选择排序
{
index = i;
for (j = i + 1; j <= n; j++) { //在无序区中选取最小记录
if (r[j] < r[index]) index = j;
if (index != i) r[i]<-->r[index];
}
}
}
自堆顶至叶子的调整过程称为“筛选”，筛选算法用伪代码可描述为：
1.设置i和j，分别指向当前要筛选的节点和要筛选节点的左孩子；
2.若节点i已是叶子，则筛选完毕，算法结束；否则，执行下述操作：
2.1 将j指向节点i的左右孩子中较大者；
2.2 如果r[i]大于r[j]，则筛选完毕，算法结束；
2.3 如果r[i]小于r[j]，则将r[i]与r[j]交换；令i=j，转步骤2继续筛选；
假设当前要筛选节点的编号为k，堆中最后一个节点的编号为m，并且节点k的左右子树均是堆，即r[k+1]~r[m]满足堆的条件，堆调整算法的C++代码如下：
筛选法调整堆的算法Sift
void Sift(int r[], int k, int m) //0号单元用作交换操作的暂存单元
{
i = k; j = 2 * i; //i指向被筛选节点，j指向节点i的左孩子
while (j <= m) //筛选还没有进行到叶子
{
if (j < m && r[j] < r[j+1]) j++; //比较i的左右孩子，j指向较大者
if (r[i] > r[j]) break; //根节点已经大于左右孩子中的较大者
else {
r[i] <--> r[j]; //将根节点与节点j交换
i = j; j = 2 * i; //被筛节点位于原来节点j的位置
}
}
}
堆排序是利用堆（假设利用大根堆）的特性进行排序的方法，其基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录。然后将将堆顶记录移走，并将剩余的记录再调整成堆，这样又找出次大的记录。以此类推，直到堆中只有一个记录为止。
void HeapSort(int r[], int n) //0号单元用作交换操作的暂存单元
{
for (i = n/2; i >= 1; i--) //初始建堆，从最后一个分支节点至根节点
Sift(r, i, n);
for ( i = 1; i < n; i++) //重复执行移走堆顶及重建堆的操作
{
r[1] <--> r[n-i+1];
Sift(r, 1, n-i);
}
}
归并排序、基数排序参考其他资料。
