- 直接插入排序
- 折半插入排序
- 希尔排序
- 冒泡排序
- 快速排序
每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列。
- 简单选择排序
每一趟在待排序元素中选取关键字最小的元素加入有序子序列。
n个元素的简单选择排序需要n-1趟处理。
代码实现如下：
//简单选择排序
void SelectSort(int A[], int n)
{
for (int i = 0; i < n - 1; i++) //一共进行n-1趟排序
{
int min = i; //记录最小元素的位置
for (int j = i + 1; j < n; j++) //在A[i...n-1]中选择最小的元素
if (A[j] < A[min]) min = j; //更新最小元素的位置
if (min != i) swap(A[i], A[min]); //封装的swap()函数共移动元素3次
}
}
//交换
void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
空间复杂度：O(1)
时间复杂度：
稳定性：不稳定
适用性：既可以用于顺序表，也可以用于链表
- 堆排序
--什么是堆？
若n个关键字序列L[1...n]满足下面某一条性质，则称为堆（Heap）：
（1）若满足：L(i)≥L(2i)且L(i)≥L(2i+1)（1≤i≤n/2）——大根堆
（2）若满足：L(i)≤L(2i)且L(i)≤L(2i+1)（1≤i≤n/2）——小根堆
【理解】：在二叉树的顺序存储中，有几个常考的基本操作：
- i的左孩子 2i
- i的右孩子 2i+1
- i的父结点 [i/2]
- i所在的层次 或
若完全二叉树中共有n个结点，则
- 判断i是否有左孩子？ 2i≤n
- 判断i是否有右孩子？ 2i+1≤n
- 判断i是否是叶子/分支结点 i>[n/2]
堆，从物理上看，是一个连续存放的数组；从逻辑上看，应该把堆看成一棵顺序存储的完全二叉树。
数组下标为1的结点是完全二叉树的根结点。
数组下标为i的结点，它的左孩子数组下标是2i，它的右孩子数组下标是2i+1。
1≤i≤n/2的意思是，这个结点一定是一个分支结点。
所以大根堆就是：在完全二叉树中，根≥左、右
【对比二叉排序树BST：左≤根≤右】
小根堆：在完全二叉树中，根≤左、右
--如何基于“堆”进行排序？
堆排序是一种选择排序。
选择排序：每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列。
如果现在已经有了一个大根堆，直接选取关键字最大的元素，即数组中第一个元素，进行排序。
但是现在没有大根堆。
--对于一个序列，如何建立大根堆？（根≥左、右）
思路：把所有分支结点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整。
在上面的完全二叉树中，总共有8个结点。1≤i≤n/2，结点下标 ≤ n / 2 的结点都是分支结点。
在本例中，检查所有分支结点，就是检查下标≤4的结点（即53,17,78,09）。
现在从后往前依次处理这些结点：
第一个被处理的是4号结点——09，查看以4号结点为根的部分，是否满足大根堆的要求（根≥左、右）。
若不满足，将当前结点与更大的一个孩子互换，由于4号结点只有左孩子，所以4号节点和它的左孩子互换。
现在处理3号结点——78，同理找到以3号结点为根结点的子树，左孩子65，右孩子78，不满足大根堆的条件，将78和87互换。
现在处理2号结点——17，左孩子32，右孩子45，不满足大根堆条件，跟45换。
现在处理1号结点——53，左孩子45，右孩子87，不满足大根堆条件，跟87换。
我们发现，以53为根结点的子树，不满足大根堆的条件，重复上述操作。
53的左孩子65，右孩子78，跟78换。
至此，整棵树符合大根堆的要求。
建立大根堆的算法：
//建立大根堆
void BuildMaxHeap(ElemType A[], int len)
{
for (int i = len / 2; i > 0; i--) //从后往前调整分支结点
HeadAdjust(A, i, len);
}
//将以k为根的子树调整为大根堆
void HeadAdjust(ElemType A[], int k, int len)
{
A[0] = A[k]; //A[0]暂存子树的根结点
for (i = 2 * k; i <= len; i *= 2) //沿key较大的子结点向下筛选
{
if (i < len && A[i] < A[i + 1])
i++; //取k较大的子结点的下标
if (A[0] > A[i]) break; //筛选结束
else
{
A[k] = A[i]; //将A[i]调整到双亲结点上
k = i; //修改k的值，以便继续向下筛选
}
}
A[k] = A[0]; //被筛选结点的值放入最终的位置
}
--现在，我们已经有了一个大根堆，如何基于大根堆进行排序？
选择排序思想：每一趟在待排序元素中选取关键字最大的元素加入有序子序列。
堆排序思想：每一趟将堆顶元素加入有序子序列（与待排序序列中最后一个元素交换），并将待排序元素序列再次调整为大根堆（小元素不断“下坠”），HeadAdjust函数。
【注意】：基于“大根堆”的堆排序得到“递增序列”。
基于大根堆进行排序，代码实现如下：
//建立大根堆
void BuildMaxHeap(int A[], int len)
{
for (int i = len / 2; i > 0; i--) //从后往前调整所有分支结点
HeadAdjust(A, i, len);
}
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len)
{
A[0] = A[k]; //A[0]暂存子树的根结点
for (int i = 2 * k; i <= len; 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(int A[], int len)
{
BuildMaxHeap(A, len); //初始建堆
for (int i = len; i > 1; i--) //n-1趟的交换和建堆过程
{
swap(A[i], A[1]); //堆顶元素和堆底元素交换
HeadAdjust(A, 1, i - 1); //把剩余的待排序元素整理成堆
}
}
基于大根堆排序的，算法效率分析：
一个结点，每“下坠”一层，最多值需对比关键字2次。（如果有两个孩子，要对比两次，一次是两个孩子之间对比，一次是子树根结点和两个孩子中较大的那个对比；如果有一个孩子，只需要对比一次）
若树高为h，某结点在第1层，则将这个结点向下调整最多只需要“下坠”h-i层，关键字对比次数不超过2(h-i)。
n个结点的完全二叉树树高 。
第i层最多有个结点，而只有第1~（h-1）层的结点才有可能需要“下坠”调整。
建堆的过程，关键字对比次数不超过4n，建堆的时间复杂度=O(n)。
下面分析排序的过程：
根结点最多“下坠”n-1层，每“下坠”一层，最多只需对比关键字2次，因此每一趟排序复杂度不超过O(h)=O(）。共n-1趟，总的时间复杂度=O()。
所以，总体来说，堆排序的时间复杂度度=O(n) + O() = O()
堆排序的空间复杂度=O(1) 。
算法的稳定性分析：
堆的插入删除
- 在堆中插入新元素
对于小根堆，新元素放到表尾，与父结点对比，若新元素比父结点更小，则将二者互换。新元素就这样一路“上升”，直到无法继续上升为止。
首先插入新元素13。
13＜其父结点32，交换13和32。
13还要继续和它的父结点比较，13<17，交换。
13>它的父结点09，符合小根堆条件。
其次，插入新元素46，放在表尾和堆底。
46无法上升，待在堆底。
- 在堆中删除元素
被删除的元素用堆底元素替代，然后让该元素不断“下坠”，直到无法下坠为止。
如，删除13，用堆底元素46替代。
46，左孩子17，右孩子45。46和17交换。
46，左孩子53，右孩子32。46和32交换。
46下坠到堆底了。
接下来，删除65，步骤如下：
46，左孩子78，右孩子87，满足小根堆的条件。
