选择排序（堆排序、简单选择排序）

文章目录

一、 选择排序思路

二、简单选择排序

三、 堆排序

一、 选择排序思路

二、简单选择排序

/*简单选择排序*/

void SelectSort(int A[],int n)
{
   
	for(int i=0;i<n-1;i++)
	{
   
		int min=i;
		for(int j=i+1;j<n;j++)
		{
   
			if(A[j]<A[min])
				min=j;
		}
		if(min!=i)
		swap(A[i],A[min]);
	}
}

三、堆排序

• 一、由一个无序序列建一个堆
• 二、在输出堆顶元素以后，调整剩余元素称为一个新的堆

/*建堆*/

void BuildMaxHeap(int A[],int len){
   
	for(int i=len/2;i>0;i--)
		AdjustDown(A,i,len);
}

/*向下过滤*/
void AdjustDown(int A[],int k,int len){
   
	A[0]=A[k];
	for(int i=2*k;i<=len;i*=2){
   
		if(i<len&&A[i]<A[i+1])
			i++;
		if(A[0]>=A[i])
			break;
		else{
   
			A[k]=A[i];
			k=i;
		}
	}
	A[k]=A[0];
}
/*向上过滤*/
void AdjustUp(int A[],int k,int len){
   
	A[0]=A[k];
	int i=k/2;
	while(i>0&&A[i]<A[0]){
   
		A[k]=A[i];
		k=i;
		i=k/2;
	}
	A[k]=A[0];
}