选择排序
选择排序的思想很简单，就是在数组找到一个最大的然后放到最后面（升序）、最前面（降序），或者找一个最小的放到最前面（升序）最后面（降序）。此外还有优化方案就是从两边开始，同时找最大的和最小的，找的后放到正确的位置
void SelectSort1(vector<int>& v)
{
if (v.empty())
{
return;
}
int i = 0;
int j = 0;
for (i = 0; i<v.size() - 1; i++)//控制交换的次数
{
int min = i;
for (j = i; j<=v.size() - 1; j++)//在该区间找到最小的
{
if (v[j]<v[min])
{
min = j;
}
}
if (min != i)
{
swap(v[i], v[min]);//把最小的放到当开始的位置，下一交换就是下一个位置，同时在这个位置后面寻找最小的
}
}
}
void SelectSort2(vector<int>& v)
{
if (v.empty())
{
return;
}
int left = 0;
int right = v.size() - 1;
while (left < right)
{
int min = left;
int max = right;
int i = left;
for (i = left; i <= right; i++)//从两边开始同时寻找最大的和最小的
{
if (v[i]>v[max])
{
max = i;
}
if (v[i] < v[min])
{
min = i;
}
}
swap(v[left], v[min]);
if (max == left)//这里的判断是为了避免最大的在left这个位置，而一交换，最大的数位置就会改变。
{
max = min;
}
swap(v[right], v[max]);
left++;
right--;
}
}
选择排序是一种不稳定的排序（4，4，3第一个4就会移到第二个4后面），时间复杂度为O(n^2)堆排序
堆
大堆：每个父子节点都大于孩子节点
小堆：每个父子节点都小于孩子节点
堆排序也是选择排序的一种。如果升序就建大堆，每次取堆顶的数往最后放（swap(heap[0],heap[end])）,交换往后该堆就不是一个大堆了（除最后一个放好的数），从开始位置进行一次向下调整，又将其调整为一个大堆，把堆顶与最后次位置进行交换，依次这样进行排序。如果降序建小堆
class Solution {
public:
/**
* @param A an integer array
* @return void
*/
/*void AdjustDown(vector<int>& a,int n,int root)
{
int parent=root;
int child=parent*2+1;
while(child<n)
{
if(child<n-1&&a[child+1]>a[child])
{
child++;
}
if(a[parent]<a[child])
{
swap(a[parent],a[child]);
parent=child;
child=parent*2+1;
}
else
{
break;
}
}
}
void sortIntegers2(vector<int>& A) {
// Write your code here
int i=0;
for(i=(A.size()-2)/2;i>=0;i--)
{
AdjustDown(A,A.size(),i);
}
int end=A.size()-1;
while(end>0)
{
swap(A[end],A[0]);
AdjustDown(A,end,0);
end--;
}
}*/
};此外我们也可以这样实现堆排序
void sortIntegers2(vector& v)
{
make_heap(v.begin(),v.end());
sort_heap(v.begin(),v.end());
}