1、简单选择排序
******、算法步骤
简单选择排序也叫直接选择排序
（1）、将待排序的的记录存放在数组 r 中，第一趟从 r [0]开始，通过 n - 1次的比较，从n个数中选出关键字最小的记录！记为 r[k]，交换 r[k]和r[0]
（2）、第二趟从 r[1]开始，通过 n - 2 次的比较（因为算上第一步中已经排好的数和r[1]除外，在剩余的数中找到最小值），从 n - 1个记录中选出最小的关键字，记为 r[k]，交换 r[k]和r[1]
（3）、依次类推，完成整个排序过程！
******、算法实现
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#define endl '\n'
using namespace std;
//选择排序函数
int SelectSort(int (&a)[20],int n){ //使用引用之后，就可以在主函数中可以使用另一个数组类型的变量直接访问排好序的数组，而不用再返回排序数组的地址，打印排序结果
for(int i = 0; i < n - 1; i++){ //需要进行 n - 1趟
int min = i; //记录最小元素的位置
for( int j = i + 1; j < n;j++){
if (a[j] < a[min])
min = j; //更新最小元素位置
}
if(min != i) //交换元素
swap(a[i],a[min]);
}
}
//交换元素函数
void swap(int &a,int &b){
int temp = a;
a = b;
b = temp;
}
main(){
cout<<"\n请输入要执行选择排序的数，输入结束请输入 -1：";
int elem;
cin>>elem;
int i = 0;
int sort[20];
while(elem != -1){
sort[i] = elem;
i++;
cin>>elem;
}
SelectSort(sort,i);
cout<<"\n----------选择排序结果如下----------!\n";
int n = 0;
cout<<"\n";
while(n < i){
cout<<sort[n]<<" ";
n ++;
}
}
******、算法分析
（1）、时间复杂度：
简单选择排序过程中所需要进行记录移动的次数较少。最好是正序，不用移动；最坏情况，逆序：3（n-1）次
然而所需关键字间的比较次数依然是 nn/2
所以时间复杂度是O（nn）
（2）、空间复杂度为 O（1），因为在该过程中使用了一个变量 temp 用于临时交换！
******、算法特点
（1）、稳定排序算法
（2）、因为不需要随机存取的特性，因此可以使用链式存储结构
（3）、移动次数比较少，当每一个记录占用的空间较大的时候，此方法比直接比直接插入排序块！
2、堆排序
******、堆排序简介
是一种树形选择排序，在排序的过程中，将待排序的记录 r[1…n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的存在关系，在当前无序的序列中选择关键字最大（或最小）记录！
大根堆（大顶堆）：在完全二叉树中，根 >= 左，右孩子，堆顶元素必然为最大值
小根堆（小顶堆）：在完全二叉树中，根 <= 左，右孩子，堆顶元素必然为最小值
******、堆排序算法步骤
（1）、按照堆的定义将待排序序列 r[1…n]调整为大堆根（这个过程称为建初堆），交换r[1]和r[n]，则 r[n]为关键字最大的记录
（2）、将r[1…n-1]调整为堆，交换 r[1]和r[n-1]，则r[n-1]为次大的关键字！
（3）、循环 n - 1次，直到交换了 r[1] 和 r[2]为止，得到一个非递减的有序序列r[1…n]
同理，按照上面的方法可以通过构造小根堆得到一个非递增的有序序列！
注意，每次重新调整堆的时候，不要将已经前一次通过大堆根得到的最大关键字（小堆根得到的最小关键字）算在里面！也即上一次之后本次就要删除它！
实现堆排序的重要问题是：
（1）、建初堆：如何将一个无序序列构建称为一个对？
（2）、调整堆：去掉堆顶元素，在堆顶元素改变之后，如何调整剩余元素成为一个新的堆？
因为建初堆必须要用到调整堆的操作，所以下面先讨论调整堆的实现！