两种选择类排序算法(简单选择排序，堆排序)

选择类排序：

1.简单选择排序

//不稳定 
void SelectSort(int a[],int n){
int min,i,j,t;
//n-1趟循环 
for(i=0;i<n-1;i++){
//找出当前区间最小的关键字的位置 
min = i;
for(j=i+1;j<n;j++){
if(a[j]<a[min]) min=j;
}
if(i!=min){
t=a[min];
a[min]=a[i];
a[i]=t;
}
}
}

2.堆排序

• 递归版

/**
堆排序(小根堆)
根节点小于左右子树的根节点
**
/**
堆元素的下坠
实现思路：检查当前节点是否满足堆的性质，如果不满足，调整当前节点的位置 递归的进行
**/
void HeapDown(int a[],int i,int n){ //i为元素坐标 
//递归版本 
int t = i;
if(2*i<=n&&a[2*i]<a[t]) t = 2*i;
if(2*i+1<=n&&a[2*i+1]<a[t]) t=2*i+1;
if(t!=i){
int u = a[i];
a[i] = a[t];
a[t] = u;
HeapDown(a,t,n);
}
//堆排序 0不存放元素 
void HeapSort(int a[],int n){
//建立初堆 
for(int i=n/2;i>0;i--){
HeapDown(a,i,n);
}
//进行堆排序
while(n>0){
//头尾节点互换
int t = a[1];
a[1]=a[n];
a[n]=t;
HeapDown(a,1,--n);
}
}

• 非递归版

void HeapDown(int a[],int i,int n){ //i为元素坐标 
//顺着左孩子向下 找
a[0]=a[i];
for(int k=2*i;k<=n;k*=2){
if(k+1<=n&&a[k+1]<a[k]) k++; //找最小 
if(a[k]>a[0]) break; //如果最小都比根大 退出 
else{ //否则交换节点的值 
a[i]=a[k];
i=k;
}
}
a[i]=a[0];
}

最后

以上就是正直短靴为你收集整理的两种选择类排序算法(简单选择排序，堆排序)的全部内容，希望文章能够帮你解决两种选择类排序算法(简单选择排序，堆排序)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。