前言
选择排序算法有两种，一种是直接选择排序，另一种是堆排序。他们的算法思想都离不开选择二字，其中堆排序比选择排序的更加快捷。
一、直接选择排序
1.排序思想
以升序为例
遍历数组，找到数组中最小的元素放到最前面，在从剩下的数组元素中找到最小的，依次放入，当只剩下一个元素时，已经排好。
2.直接选择排序代码（每次只选一个）
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void Swap(int* p1, int* p2)
{
int tem = *p1;
*p1 = *p2;
*p2 = tem;
}
void SelectSort(int* a, int n)
{
int i = 0, min = 0, j = 0;
for (i = 0; i < n - 1; i++)
{
min = i;//假设该位置的元素是最小的
for (j = i + 1; j < n; j++)
{
if (a[min] > a[j])//选出最小元素的下标
{
min = j;
}
}
if (min != i)
//如果原本位置的数据不是最小，则根据选出最小元素的下标与该位置元素交换
{
int tem = a[i];
a[i] = a[min];
a[min] = tem;
}
}
}
int main()
{
int arr[5] = { 2,3,1,4,5 };
SelectSort(arr, 5);
for (int i = 0; i < 5; i++)
{
printf("%d ", arr[i]);
}
}调试结果：
对于直接选择排序，我们可以略加优化，使其每次能选出两个值，分别是最小和最大，放入数组首和数组尾。
3.直接选择排序代码（每次选两个）
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void Swap(int* p1, int* p2)
{
int tem = *p1;
*p1 = *p2;
*p2 = tem;
}
void SelectSort(int* a, int n)
{
int begin = 0;//未排序区间起始下标
int end = n - 1;//未排序区间终点下标
while (begin < end)//排序区间左下标小于右下标
{
int max = begin, min = begin;
for (int i = begin; i <= end; i++)
{
if (a[min] > a[i])//每次遍历当前未排序区间，选出最小元素的下标
{
min = i;
}
if (a[max] < a[i])//每次遍历当前未排序区间，选出最大元素的下标
{
max = i;
}
}
Swap(&a[begin], &a[min]);
//根据最小元素的下标，将最小元素放在未排序区间的起点
if(max==begin)
//如果数组中的最大值下标恰好是第一个（即与起始位置下标重合，需要进行修正）
//这是因为在确定最大值与最小值下标后，先把最小值放到了
//数组首的位置，此时最大值和最小值发生了交换，但是最大值对应的下标却没有改变，
//此时最大值对应的下标应该是min
{
max=min;
}
Swap(&a[max], &a[end]);
//根据最大元素的下标，将最大元素放在未排序区间的终点
begin++;//选出当前区间最小值并放于起点后，区间起点位置后移
end--;//选出当前区间最大值并放于终点后，区间起点位置前移
}
}
int main()
{
int arr[5] = { 2,3,1,4,5 };
SelectSort(arr, 5);
for (int i = 0; i < 5; i++)
{
printf("%d ", arr[i]);
}
}调试结果：
二、堆排序
1.什么是堆
在讲堆排序之前，我们需要明白所谓的堆是什么。
我们知道土堆，谷堆，它们都是近似于正金字塔的形状，那么堆是不是也是这样呢？
如下图是一颗完全二叉树
它的层序遍历顺序是：100，82，74，69，73，56，65，33，47，53
堆:将这样一颗按照层序遍历顺序的完全二叉树依次放入数组中，并且该完全二叉树的每个结点的值都大于等于该结点左右孩子的值（或者每个结点的值都小于等于该结点左右孩子的值）就叫做堆。
2.堆的两种类型
堆有两种类型，最大堆和最小堆（或者叫大顶堆，小顶堆，以下统称为最大堆和最小堆）。
最大堆：所有结点的值都大于等于该结点左右孩子的值
最小堆：所有结点的值都小于等于该结点左右孩子的值
3.堆的结构
堆的逻辑结构是一颗二叉树，是我们想象构造出来的，堆的物理结构是一个数组，是实际存储数据用的结构。
堆有两种特性：
1.结构性：该特性指的是堆是用数组表示的完全二叉树
2.有序性：即每个结点的值都不小于（或者不大于）其孩子的值
4.堆与完全二叉树的联系
在上文我们解释了堆的本质就是数组，存放的是按层序遍历依次放入的完全二叉树，数组下标依次对应着二叉树结点的数值
对于完全二叉树，父节点与孩子结点有如下关系
lchild=parent*2+1,即左孩子结点的下标等于该结点的父节点的下标乘以2再加1
rchild=parent*2+2，即右孩子结点的下标等于该结点的父节点的下标乘以2再加2
parent=(child-1)/2,即父节点的下标等于他的左孩子或者右孩子结点的下标减去1后再除以2
举例说明：
我们把下标为0的结点当作父结点，0*2+1=1，0*2+2=2，得到的分别是他的左右孩子结点的下标，再例如，我们将下标为4的结点当作父节点，4*2+1=9，得到的恰好是它的左孩子结点的下标。接着，下标为7和8的两个结点是下标为3结点的的两个孩子结点，（7-1）/2=3,(7-2)/2=3，得到的也正是这两个结点的父结点的下标。
5.堆排序算法思想
以建最大堆排升序为例
第一步：建堆
什么是建堆呢？将父结点位置的元素与左右孩子中较大元素作比较，如果父结点较小，则交换两者的值，并且使父结点指向较大值所在的下标，孩子结点指向新父结点的左孩子。一直到整棵树都满足堆的要求。这个比较的过程也被称为向下调整法，向下调整有个很重要的前提，那就是父结点的左右子树必须都是最大堆
那么比较过程会在什么时候停止呢？有两种情况：一是在比较的过程中，父节点的值更大，此时无需继续比较，二是遇到叶子结点，因为叶子结点没有孩子结点，所以也无需比较
我们会发现，利用堆排序进行排序时，建堆的过程只能从最后一个有孩子结点的父结点开始依次向前开始向下调整的过程，因为只有这样才能满足向下调整法的要求（初始数据元素是乱序的，建堆的过程是将最大或者最小的值放到根结点的过程，父结点指向的位置当作根结点，该根结点的左右子树必须满足堆的要求，从后向前其实就是从最底层开始调整，底层满足要求了，才能从上层开始，向下进行调整）
我们来举例说明：
我们要把上述10个数据按照堆排序进行升序，我们把这10个数据当成一颗完全二叉树按层序遍历顺序浏览的数据，去还原出这颗树，第一个数是根节点，接下来两个数据是根节点的左右孩子，再4个数据依次是左右孩子结点的左右孩子，最后绘制结果如下
在建堆过程中，把最后一个有孩子的父结点当作根结点，使用向下调整法使子树满足堆的要求（此时该根结点的左子树或者右子树至多有一个元素，一定满足向下调整法的要求），调整完成后，父结点向前移动，将新的父结点指向的位置当作根结点，利用向下调整法使新的子树也满足堆的要求，直到整棵树逐渐变为最大堆。
我们可以通过元素个数，确定最后一个元素的下标，求得该元素的父结点的下标。例如，上述有10个数据，（10-1-1）/2=4，此时的父结点是下标为4的数据，它的孩子结点是下标为9的数据，如下图
父结点的值小于它的孩子结点的值，交换两者的数值，并使夫结点指向与他交换数值数据的下标，如下图
此时已经来到叶子结点，因此调整（比较）停止
此时，从后向前调整，新的父结点下标变为了3，孩子结点指向下标7所在位置
如下图，
以下标为3，7，8构成的堆状结构满足最大堆的要求，因此无需比较，新的父节点指向下标3的位置，孩子结点指向新的父结点的左孩子，如下图
以下标为2的结点为根节点的子树同样满足最大堆的要求，因此也无需调整，新的父结点下标再次--，指向下标1，如下图
将下标为1的位置当作新的根节点，它小于它的孩子结点中的较大值，因此发生交换，父结点指向新的位置
以新的父结点为根结点的子树满足最大堆的要求，因此无需交换，父结点此时指向下标为0的位置，它的左右子树也满足最大堆的要求，开始最后一次的向下调整，如下图
53小于100，发生交换，同时父结点指向下标为1的位置，53小于82，再次发生交换，父结点指向下标为4的位置，53小于73，再次发生交换，此时已经到达叶子结点，交换停止，依次如下图所示
最终建堆完成后如下：
第二步：利用堆进行选择排序
当我们建好一个最大堆时，会发现根结点的值是最大的，因此我们将跟结点（下标为0）的值与最后一个数据交换，让最大的值放到最后，然后不用搭理它，再次建堆，使根结点的值再次调整为最大时，再次与倒数第二个数据交换，以此类推，直到整个数组只剩下一个元素，堆排序已经完成。也因此排升序建最大堆，排降序建的是最小堆
6.堆排序代码
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void Swap(int* p1, int* p2)//交换两个变量的值
{
int tem = *p1;
*p1 = *p2;
*p2 = tem;
}
void AdustDown(int* a, int n, int root)//向下调整
{
int parent = root;
//将父结点指向的位置当作根结点，以它为根结点的树当作子树
int child = parent * 2 + 1;
//始终指向左孩子
while (child < n)
//当孩子结点的下标小于元素个数时，表面还没到叶子结点，调整继续
{
if (a[child] < a[child + 1] && (child + 1) < n)
//因为是建最大堆，因此选出左右孩子中的较大值，并且要保证右孩子存在
{
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)//堆排序
{
//建大堆，每个结点的值都不小于他的孩子结点（完全二叉树），实际用数组的形式存储
for (int i = (n - 2) / 2; i >= 0; i--)
//i是父结点的下标，从后向前，一直到整棵树的根结点
{
AdustDown(a, n,i);
}
//循环结束后，数据已经满足最大堆的要求，根结点的元素值最大
//利用堆选择排序，升序建大堆
int end = n - 1;//最后一个元素的下标
while (end > 0)//当只剩下一个元素时，循环才能结束
{
Swap(&a[0], &a[end]);
//将最大值交换到最后一个位置
AdustDown(a, end, 0);
//只需要从根结点开始，调整一次，这里end表示当前元素个数
end--;//每次交换后，最后一个元素的下标减去1
}
}
int main()
{
//堆排序，大堆
int arr[10] = { 2,6,0,9,7,14,18,27,98,5118};
HeapSort(arr, 10);
for (int i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
}调试结果：
