?常见排序：
- 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
- 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]?，且?r[i]?在?r[j]?之前，而在排序后的序列中，r[i]?仍在?r[j]?之前，则称这种排序算法是稳定的；否则称为不稳定的。
- 内部排序：数据元素全部放在内存中的排序。
- 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
目录
选择排序类：?
? ? ? ??选择排序类的基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
? 1、?简单选择排序：
- 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素。
- 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换。
- 在剩余的array[ i ] ~?array[ n - 2 ]（array[ i + 1 ] ~ array[ n - 1 ]）集合中，重复上述步骤，直到集合剩余1个元素。
//直接插入排序
// 对比 插入排序，谁更小。
void SelectSort(int* a, int n)
{
assert(a);
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin;
for (int i = begin + 1; i <= end; ++i)
{
if (a[i] < a[mini])
mini = i;
}
Swap(&a[begin], &a[mini]);
++begin;
}
}1.1?简单选择排序的特性总结：
- 简单选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
1.1.1 时间复杂度:
????????????????时间复杂度：O(N^2)
? ? ? ? ? ? ? ? ? ? ? ?是常见的等差数列：n, n-1, n-2, …… 1。
1.1.2?空间复杂度:
????????????????空间复杂度：O(1)
1.1.3 稳定性：?
?
??2、 堆排序：
????????堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
//数据交换
void Swap(int* e1, int* e2)
{
int tmp = *e1;
*e1 = *e2;
*e2 = tmp;
}
//向下调整
void AdjustDown(int* a, int n, int root)
{
int parent = root;
int child = parent * 2 + 1;
while (child < n)
{ //>大堆，<小堆
if (child + 1 < n && a[child + 1] > a[child])
{
++child;
}
//>大堆，<小堆
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆排序
void HeapSort(int* a, int n)
{
assert(a);
// 建堆，先从最后两个叶子上的根(索引为(n - 2) / 2开始建堆
// 建最小的堆(最大的堆)
for (int i = (n - 2) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
//end:表示最后一个位置
int end = n - 1;
//只剩一个数时，就不需要调整了
while (end > 0)
{
//0位置和最后一个位置交换
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}2.1.?堆排序的要点分两步：
2.1.1?建立大小堆：
? ? ? ? ? 对于向下调整，需要根节点的堆成立大小堆，否则会导致堆的混乱，而针对于一个未排序为堆的数组，如果以a[0]为父节点，会导致堆的混乱。
- 用于排序的父节点
- 代比较的子节点
- 比较后挑选出的子节点
- 对于当时的根节点，已排序好的节点
2.1.2 利用大小堆排序：
2.1?堆排序的特性总结：
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
2.1.1?时间复杂度:
????????首先，我们需要知道向下建堆的时间复杂度：
? ? ? ?即：O(N)。
? ? ? ?建立大小堆的时间复杂度：
? ? ? ? 于是，时间复杂度为：?O(N)。
(倒过来看，原来是从第1层向其他层看，而这个建队是从最后一个父节点开始，于是就从第h-1层看)
???????利用大小堆排序的时间复杂度：
?? ? ? 于是，时间复杂度为：?O(N*logN)。
? 单趟：
? ? ? ?在之前，我们已经建堆完成，其的无序是因为我们将最后一个元素与第一个元素交换位置。然后 n-1 ,于是唯一一个堆无序的就是第一个元素。而最差的情况就是其需要调到最底层，于是时间复杂度为O(logN)。
? 全趟：
? ? ? ?单趟是O(logN)，一共有n个元素，所以就是：O(N*logN)。
2.1.2?空间复杂度:
? ? ? ?没有使用递归，并且变量的创建也是常数。所以是O(1)。
2.1.3?稳定性:
- 用于排序的父节点
- 代比较的子节点
- 比较后挑选出的子节点
- 对于当时的根节点，已排序好的节点
