1、选择排序简介

其基本思想十分简单：每趟排序在当前待排序序列中选出关键字最小的记录，添加到有序序列中。选择排序的方法主要包括简单选择排序和堆排序。

2、简单选择排序

简单选择排序是选择排序中最简单的一种排序方法。其思想就是把给定序列分为一个有序序列和待排序序列，然后每一趟在待排序序列中选出一个最小值放到有序序列中。由此可见，假如有n个数需要排序，则经过n-1躺简单选择后可完成排序。读者可在纸上模拟下该算法。

2.1代码实例


void selectSort(int arr[],int len) //传入参数：数组和数组长度
{	
  	//循环n-1躺，因为需要n-1躺排序
	for(int i = 0;i<len-1;++i)
	{
		int temp = i;
      	//需要待排序序列中的最小值
		for(int j = i+1;j<len;++j)
		{
			if(arr[j]<=arr[temp]) temp =j;
		}
		if(i!=temp)
		{
			//交换两个数
			int s = arr[temp];
			arr[temp] = arr[i];
			arr[i] = s;
		}
	}
}

数组长度计算：
假设有一个int a[5] = {1,2,3,4,5};
数组长度len = sizeof（a）/sizeof（int）；

2.2 复杂度

时间复杂度：O（n²）。
空间复杂度：O（1）。

3、堆排序

在简单选择排序中，为了从数组arr[0]...arr[n-1]中选出关键字最小的记录，必须进行n-1次的比较。然后在arr[1]....arr[n-1]中选出关键字次小的记录，又需要做n-2次的比较。事实上，后面的n-2次比较中，有很多比较可能在前面n-1比较中已经做过，但由于前一趟排序没有保留这些结果，所以在后一趟排序中又重复执行了这些操作。我们可以通过树形结构保存部分比较结果，以减少比较次数，从而提高整个排序的效率。

3.1堆的定义

alt

如果用一维数组来存放此序列，并把这个一维数组看成一颗完全二叉树的顺序表，则堆实质上是满足如下性质的完全二叉树，树中任意非叶子节点的关键字ki均不大于其左右孩子结点的关键字k2i和k2i+1，（小根堆（顾名思义，根小）），或者是均不小于其左右孩子结点的关键字k2i和k2i+1，（大根堆）。由此可见，如果序列{k1,k2....kn}是堆，则堆顶元素必为序列中n个元素的最小值（或者最大值）。

3.2 堆排序的特点

堆排序是一种树形选择排序，其特点是：在排序过程中，将array:[k1,k2.....kn]看成一颗完全二叉树顺序表，利用完全二叉树中双亲和孩子之间的内在关系，使得在当前排序记录中选取最小（最大）关键字的记录变得简单。

3.3 堆排序的思想

其基本思想是：首先将待排序记录构造成一个堆，选出堆中关键字最大的记录（即堆顶记录）；然后将堆顶记录和堆中最后一个记录交换，此时最大元素已经放到了合适的位置。并将剩余再调整成新堆，选出次大关键字的记录，即新堆顶记录。依次类推，直至堆中只有一个记录位置。

由此可见，如果题中要求输出一个序列的最值元素，使用堆排序是个不错的选择。

3.4 堆排序的两个关键问题

如何将一个无序序列构造成一个堆，即初始化堆。
在输出堆顶记录后如何调整剩余记录成一个新堆，即重新建堆。

3.5 代码实例

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
	
//构建堆
void adjustHeap(vector<int>& data,int i,int length){
	int temp=data.at(i);
    //从i节点的左子节点开始，也就是2i+1开始
	for(int k=i*2+1;k<length;k=k*2+1)
    {   
		if(k+1<length && data.at(k)<data.at(k+1)){
			//如果左子节点小于右子节点，k指向右节点
			k++;
		}
		if(data.at(k) > temp)//如果子节点大于父节点，将子节点赋值给父节点，不交换
        {
			data.at(i)=data.at(k);
			i=k;
		}else
        {
			break;
		}
	}
	data.at(i)=temp;
}
	
void sortV(vector<int>& data){
	int l=data.size();
	//1.构建大顶堆
	for(int i=l/2-1;i>=0;i--){
		adjustHeap(data,i,l);
	}
	//2.调整堆结构，交换堆顶元素与末尾元素，重新对堆进行调整
	for(int j=l-1;j>0;j--)
    {
		swap(data.at(0),data.at(j));
		adjustHeap(data,0,j);
	}
 
}

int main()
{   
  	//测试
    vector<int> v{14,1,59,38,64,100,30,24,5,3,2};
    sortV(v);
    for(auto i:v) cout<<i<<endl;
    return 0;
}

读者可以对者代码模拟下堆排序的过程，有利于加深理解。

3.6 复杂度

时间复杂度：堆排序的运行时间主要消耗在初始建堆和调整重新建堆时进行的反复“筛选”上。对n个待排序序列，交换堆顶元素后，调整重新建堆的时间复杂度最坏为O（log2n），且需要n-1次交换堆顶记录。因此算法复杂度为O（nlog2n）。
空间复杂度：O（1），因为只需要一个用于交换数据的临时单元。

3.7 堆排序适用场景

该算法对于数据较少的序列不值得提倡使用，但对于数据量大的序列还是非常有效的。而且堆排序对原始记录的排序状态不敏感，所以相对于快排来说这是优点。

基础算法——选择排序