석 주 - 데이터 구조 - 선택 & 쌓 기 정렬

1. 정렬 선택
예전 에 내 가 가장 좋아 했 던 것 은 순 서 를 선택 하 는 것 이 었 다. 왜냐하면 그것 은 가장 쉽게 이해 할 수 있 기 때문이다. 현재 요소 의 뒤에서 가장 작은 요 소 를 선택 하여 교환 하 는 것 이다.
void SelectionSort(int a[],int n)
{
	int i,j,min; //min            
	for(i=0;i<n-1;i++)
	{	
		min=i; 
		for(j=i+1;j<n;j++)
		{
			if(a[min]>a[j]) min=j; //                     
		}
		if(min!=i) Swap(a[i],a[min]);   //   ->   
	}
} 

2. 쌓 기 정렬
쌓 기 정렬 은 빠 른 정렬 의 개선 으로 거품 처럼 빠르다.단일 변수 i * = 2 와 관련 되 기 때문에 i 의 아래 표 지 는 1 부터 만 시작 할 수 있 고 쌓 기 순 서 는 2 단계 로 나 눌 수 있 습 니 다.
 무더기로 쌓다
마지막 분기 노드 (length / 2) 부터 아이의 노드 와 비교 하여 큰 것 을 찾 으 면 교환 합 니 다.이렇게 정점 에 이 르 면 큰 무 더 기 를 얻 을 수 있다.
void HeapSort(int a[],int n)
{
	//        (length/2)  ,         ,
	//           ,       
	for(int i=n/2;i>0;i--)
	{
		AdjustDownFill(a,i,n); 
	}
	//    
	for(int i=n;i>1;i--)
	{
		Swap(a[i],a[1]);
		AdjustDownFill(a,1,i-1); 
	} 
} 

더 미 를 조정 할 때 정점 은 가장 큰 노드 로 말단 노드 와 교환 합 니 다.말단 노드 는 최대 노드 가 되 고 말단 노드 를 부 드 럽 게 삭제 합 니 다.정점 에서 아래로 계속 조정 하여 새로운 지붕 더 미 를 얻다.이렇게 반복 하면 한 노드 가 남 을 때 까지 하면 된다.
다음은 교환 에 기초 한 사상 이다.
void AdjustDownSwap(int a[],int k,int n)
{
	for(int i=k*2;i<=n;i*=2) //       
	{
		if(i<n && a[i]<a[i+1]) i++; //     ,    
		if(a[i]<=a[k]) break; //     ,     
		Swap(a[k],a[i]);  //       
	}
}

빠 른 정렬 과 마찬가지 로 교환 하 는 사상 은 자 리 를 채 우 는 사고 로 개선 할 수 있다.
void AdjustDownFill(int a[],int k,int n)
{
	a[0]=a[k];
	for(int i=k*2;i<=n;i*=2) //       
	{
		if(i<n && a[i]<a[i+1]) i++; //     ,    
		if(a[i]<=a[0]) break; //     ,     
		a[k]=a[i]; //         
		k=i; //            
	}
	a[k]=a[0]; //     a[0]          
}

좋은 웹페이지 즐겨찾기