选择：每次选出一个合法（最大/最小）的数据放到其最终应该在的位置
1.（简单）选择排序：每趟从待排序区中，选择一个最小的数，放到待排序区的第一个位置，从而实现升序排列。
时间复杂度：O(n^2)
是否稳定：不稳定
为就地排序
2.对选择排序进行优化---->堆排序
对于一棵完全二叉树，进行编号，编号规则为：根节点为1，然后从上到下，从左到右。除根节点外，节点i的父亲节点编号为i/2(向下取整)。除叶子节点外，节点i的左孩子节点编号为2*i，右节点为2*i+1（可直接用数组存储）
堆(Heap):是一类基于完全二叉树的特殊数据结构
1.大顶堆：在大顶堆中，根节点的值必须大于等于其孩子节点的值，且所有子树均满足
2.小顶堆：在小顶堆中，根节点的值必须小于等于其孩子节点的值，且所有子树均满足
1.建堆：用一个数组保存
（1）自我初始化：在原数组基础上进行初始化
从子树入手，由小及大去调整每棵子树（不包含叶子节点）：
对于每棵子树，我们向下调整：
让根节点和其左右孩子作比较，最小值和根节点交换，继续向下调整子树
（2）通过插入建堆
数组中每多一个数据就调整一次，新插入的数据放在最后，如果其比父亲大或者新插入的数据是根节点就不用调整，否则就向上调整
堆排序：
（1）建堆
（2）循环n次，每次输出最小数---->a[0]
（3）删掉a[0]---->让堆中最后一个节点替换a[0],然后重新对a[0]向下调整
时间复杂度：O(nlogn)
是否稳定：不稳定
为就地排序
堆的应用：
1.优先队列：基于堆
2.1亿个数，选出前一百个最大的数，不能使用大顶堆，使用小顶堆
a[100]--->堆
先读入100个数，建立小顶堆
接下来，当读入一个数x时，如果x<=a[0],直接读入下一个数
否则a[0]=x,向下调整小顶堆
最后留下来的小顶堆就是答案
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;
//i为根节点下标
void Down_Adjust(vector<int>(&v), int i,int size)
{
int parent(i);//根节点下标
int l_child(2 * i);//左孩子下标
int tmp(0);
//因为调整后可能子树不再是小顶堆，所以循环向下调整
while (parent * 2 <= size)
{
l_child = 2 * parent;
if (l_child + 1 <= size && v[l_child + 1] < v[l_child])
{
l_child = l_child + 1;
}
//此时，l_child是值较小的孩子
if (v[parent] < v[l_child])
{
break;
}
else
{
tmp = v[l_child];
v[l_child] = v[parent];
v[parent] = tmp;
parent = l_child;
}
}
}
void Up_Adjust(vector<int>(&v),int i)
{
int tmp(0);
int child(i);
int parent(0);
//不是根节点就继续调整
while (child > 1)
{
parent = child / 2;
if (v[parent] < v[child])
{
break;
}
else
{
tmp = v[parent];
v[parent] = v[child];
v[child] = tmp;
child = parent;
}
}
}
void Heap_Sort(vector<int>(&v))
{
//1.建堆
//(1)自我初始化
/*for (int i = (v.size() - 1) / 2; i >= 1; --i)//枚举每一个子树根节点
{
Down_Adjust(v, i,v.size() - 1);
}*/
for (int i = 1; i < v.size(); ++i)
{
cout << v[1] << ' ';
//每次“删除”最后一个节点
v[1] = v[v.size() - i];
Down_Adjust(v, 1, v.size() - 1 - i);
}
}
void Selection_Sort(vector<int>(&v))
{
//排n-1趟
for (int i = 0; i < v.size() - 1; ++i)
{
int min_i(i);//最小数下标
int tmp(0);
for (int j = i; j < v.size(); ++j)
{
if (v[j] < v[min_i])
{
min_i = j;
}
}
tmp = v[i];
v[i] = v[min_i];
v[min_i] = tmp;
}
}
int main()
{
vector<int> v;
int n(0);
cin >> n;
//下标从1开始，方便建堆
v.resize(n+1);
//(2)插入建堆
for (int i = 1;i<v.size();++i)
{
cin >> v[i];
Up_Adjust(v,i);
}
Heap_Sort(v);
/*for (auto a : v)
{
cout << a << ' ';
}*/
return 0;
}
/*
6
6
2
3
5
1
4
*/
