选择排序基本思想是：每一次在n-i+1（i=1,2,3,••••,n-1)个记录中选取键值最小的记录作为有序序列的第i个记录。基本分类有直接选择排序和堆排序两种方式。下面分别介绍
直接选择：
思想：在第i次选择操作中，通过n-i次键值比较，从n-i+1个记录中选出键值最小的记录，并和第i个记录交换
算法描述为：
Void SelectSort（List R，int n)
{
Int min, i ,j;
For(i=1;i<=n=1;i++)//每次循环选出一个最小值
{
Min=i; //假设第i个键值最小
For(j=i+1;j<=n;j++)
If(R[j].key<R[min].key) min=j; //记录下键值较小的记录下
If(min!=i) swap(R[min],R[i]); //将最小值记录和第i个记录交换
}
}
从代码中可以开出，代码的辅助变量为3个整型变量，与问题的规模无关，所以空间复杂度为O(1)，而时间复杂度是双重的n次循环，所以时间复杂度为O(n*n）
实例对初始关键字
[49 38 65 97 76 13 27 49]进行直接排序。排序过程和结果如下
第一趟排序后 13 [38 65 97 76 49 27 49]
第二趟排序后 13 27 [65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [76 97 65 49 ]
第五趟排序后 13 27 38 49 49 [97 65 76]
第六趟排序后 13 27 38 49 49 65 [97 76]
第七趟排序后 13 27 38 49 49 65 76 [97]
最后排序结果 13 27 38 49 49 65 76 97
堆排序
堆排序是对直接排序的优化，是在n-1次比较所得的信息，减少以后各次选择中的比较次数。基于以上分析。推导出堆排序
学习堆排序前，先讲解下什么是数据结构中的二叉堆。
二叉堆的定义
二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性：
1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆：
由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆就简称为堆。
堆的存储
一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2* i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。
如何创建一个堆？
首先将要排序的所有键值看成是一颗完全二叉树的各个结点（这个时候并不一定具备对特性），根据完全二叉树性质，最后一个非终端结果是第|n/2|个元素，对于i>|n/2|的结点k(i)都没有孩子结点，这样以K(i)为根的子树是堆。所以只需从|n/2|开始，逐步把
k[n/2], k[(n/2)-1], k[(n/2)-2], k(i)为根的子树筛选为堆就完成了建立堆的过程.
实例，对集合{ 40 ,10,30 ,50}对应的二叉树，筛选堆的过程如下
n=4, n/2=2,所以从k(2)开始执行，10<50，不调整，K(1)
40>10,进行调整
基本的建立过程就是上图的表示了。
时间复杂度为O(N * logN)，共N -1次重新恢复堆操作。
直接选择排序和堆排序是很类似的，每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。