排序算法之选择排序堆排序

算法	时间复杂度	辅助空间复杂度	稳定性
选择排序	O(N^2)	O(1)	不稳定
堆排序	O(NlogN)	O(1)	不稳定

1.选择排序

这应该算是最简单的排序算法了，每次在右边无序区里选最小值，没有无序区时，就宣告排序完毕

比如有一个数组：[2,3,2,6,5,1,4]排序过程如下：

（注意：开始时，蓝色2的下标比红色2小）

[2,3,2,6,5,1,4]有序区 []

从[2,3,2,6,5,1,4]中选取最小值1

交换1和2

[1,3,2,6,5,2,4]有序区[1]

从[3,2,6,5,2,4]中选取最小值2

交换2和3

[1,2,3,6,5,2,4]有序区[1,2]

从[3,6,5,2,4]中选取最小值2

交换2和3

[1,2,2,6,5,3,4]有序区[1,2,2]

从[6,5,3,4]中选取最小值3

交换6和3

[1,2,2,3,5,6,4]有序区[1,2,2,3]

从[5,6,4]中选取最小值4

交换4和5

[1,2,2,3,4,6,5]有序区[1,2,2,3,4]

从[6,5]中选取最小值5

交换5和6

[1,2,2,3,4,5,6]有序区[1,2,2,3,4,5,6]

排序完毕

可以发现排序之后蓝色2的下标比红色2大，所以选择排序不稳定

鱿鱼选择排序每次都要扫描一遍数组，时间复杂度O(n)而要进行n次扫描操作，所以时间复杂度为O(n*n)

动图

#include<bits/stdc++.h>
using namespace std;
int main(){
	int a[100000],n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<n-1;i++){
		int mn=i;
		for(int j=i+1;j<n;j++){
			if(a[j]<a[mn]){
				mn=j;
			}
		}
		swap(a[i],a[mn]);
	}
	for(int i=0;i<n;i++){
		cout<<a[i]<<' ';
	}
	return 0;
}

由于效率过低，通过不了此题（提交记录）

2.堆排序

是选择排序的改进版

要了解堆排序，首先得了解堆和完全二叉树

2.1完全二叉树

定义：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

举个栗子

这是完全二叉树

这不是

这也不是

有用的芝士：在完全二叉树中，

节点的左孩子下标= 该节点的下标*2+1，

节点的右孩子下标= 该节点的下标*2+2（第一个元素下标为0）

2.2堆

堆是一种特殊的完全二叉树分为大根堆和小根堆！

大根堆大根堆的每个父节点>=父节点对应的子节点

反之亦然

这个是大根堆

2.3堆排序

2.3.1建堆

分为向上调整算法和向下调整算法

向上调整法建堆时间复杂度：nlogn（~~太弱了~~）

向下调整法建堆时间复杂度：O(n)

建堆过程以向下调整法建大根堆为例

向下调整：如果父节点比大的孩子小，则两者交换位置，然后进行新一轮比较，直到叶子或父节点不小于大的孩子

建堆：对每个非叶子节点进行向下调整即可

建堆的代码

void mswap(int* a,int * b){//交换函数
	int t=*b;
	*b=*a;
	*a=t;
	return;
}
void down(int pa,int n){
	int chl=pa*2+1;//左孩子
	while(chl<n){
		if(chl+1<n&&f[chl+1]>f[chl]){chl++;}//如果右孩子大于左孩子
		if(f[chl]>f[pa]){
			mswap(f+chl,f+pa);
			pa=chl;
			chl=pa*2+1;//开启新一轮比较
		}
		else{
			break;//不满足条件
		}
	}
}
void makeheap(){
	int flag=n/2;//叶子节点不用比较
	for(int i=flag;i>=0;i--){
		down(i,n);
	}
}

2.3.2排序

根据刚才的内容，相信大家都发现了在大（小）根堆中，根节点最大（小）

于是把堆顶移除就可以排好一个元素，但是移除应该把堆顶和最后一个交换，否则会严重破坏堆序性，增加复杂度！

这样写只要把新堆顶进行调整即可~~

所以排序部分就是：

1.移除堆顶

2.向下调整新堆顶

3.重复以上步骤，直到堆空

上代码

#include<bits/stdc++.h>
using namespace std;
int f[100005],n;
void mswap(int* a,int * b){//自己写的交换
	int t=*b;
	*b=*a;
	*a=t;
	return;
}
void down(int pa,int n){
	int chl=pa*2+1;//左孩子
	while(chl<n){//父亲必须是非叶子节点(条件也可以是pa<n/2)
		if(chl+1<n&&f[chl+1]>f[chl]){chl++;}//如果右孩子比左孩子大
		if(f[chl]>f[pa]){
			mswap(f+chl,f+pa);
			pa=chl;
			chl=pa*2+1;//继续向下调整
		}
		else{
			break;//不满足
		}
	}
}
void heapsort(){
	int flag=n/2;
	for(int i=flag;i>=0;i--){
		down(i,n);
	}//建堆
	for(int i=n-1;i>0;i--){
		mswap(f,f+i);
		down(0,i);
	}//排序
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>f[i];
	heapsort();
	for(int i=0;i<n;i++) cout<<f[i]<<' ';
	return 0;//好习惯
}