C 언어의 모든 고전 정렬 방법의 실현 코드

실행 결과 가 정확 하 다
빠 른 정렬 이 어렵 습 니 다.

전체 코드

#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#include<malloc.h>
void swap(int *a,int *b);
void select_sort(int arr[],int n);
void tra_arr(int arr[],int n);
void insert_sort(int arr[],int n); 
void shell_sort(int arr[],int n);
void perc_down(int arr[],int i,int n);
void heap_sort(int arr[],int n);
void merge(int arr[],int temp_arr[],int left_start,int right_start
			,int right_end);
void m_sort(int arr[],int temp_arr[],int left,int right);
void merge_sort(int arr[],int n);
int get_pri(int arr[],int left,int right);
void q_sort(int arr[],int left,int right);
void quick_sort(int arr[],int n);
int main(){
	int arr[100]={
		10,9,8,7,6,5,4,3,2,1
	};
	select_sort(arr,10);
	printf("
        
");
	tra_arr(arr,10);
	
	int arr1[100]={
		10,9,8,7,6,5,4,3,2,1
	};
	insert_sort(arr1,10);
	printf("
      
");
	tra_arr(arr1,10);
	
	int arr2[100]={
		10,9,8,7,6,5,4,3,2,1
	};
	shell_sort(arr2,10);
	printf("
      
");
	tra_arr(arr2,10);
	
	int arr3[100]={
		10,9,8,7,6,5,4,3,2,1
	};
	heap_sort(arr3,10);
	printf("
     
");
	tra_arr(arr3,10);
	
	int arr4[100]={
		 10,9,8,7,6,5,4,3,2,1
	};
	merge_sort(arr4,10);
	printf("
      
");
	tra_arr(arr4,10);
	
	int arr5[100]={
		 10,9,8,7,6,5,4,3,2,1
	};
	quick_sort(arr5,10);
	printf("
      
");
	tra_arr(arr5,10);
	
	return 0;
}
void swap(int *a,int *b){
	//     ，             ，     *,
	//       ，   *,       ，      
	int t=*a;
	*a=*b;
	*b=t;
}
//       
void select_sort(int arr[],int n){
	int min;
	//            ，        
	for(int i=0;i<n;i++){
		min=i;
		
		for(int j=i+1;j<n;j++){
			if(arr[i]>arr[j]){
				min=j;
			}
		} 
		//       for，            
		swap(&arr[i],&arr[min]) ;
	} 
}
//    
void insert_sort(int arr[],int n){
	int temp,j;
	for(int i=1;i<n;i++){
		temp=arr[i];
		for(j=i;j>0&&arr[j-1]>temp;j--){
			//  
			arr[j]=arr[j-1];
		}
		//              
		arr[j]=temp; 
	}
} 
//    
void shell_sort(int arr[],int n){
	int in,i,j,temp;
	//            ，         
	//    ，            ，       
	//    2                   
	//    SED  HIB      ,       
	//     for      ,         
	
	for(in=n/2;in>0;in=in/2){
		for(i=in;i<n;i++){
			temp=arr[i];
			for(j=i;j>=in;j=j-in){
				if(arr[j-in]>temp){
					//   
					arr[j]=arr[j-in];
				}
				else{
					//arr[j-in]<temp，      
					break;
				}
			}
			//     ，         
			arr[j]=temp; 
		}
	} 
} 
//       
//i  ，n heap    
//           
void perc_down(int arr[],int i,int n){
	int child,temp;
	//    ，          
	//   i   ， i             
	//              ，         
	for(temp=arr[i];(2*i+1)<n;i=child){
		child=2*i+1;
		//            ，       
		//      
		if(child!=(n-1)&&arr[child]<arr[child+1]){
			child++;
		}
		if(temp<arr[child]){
			arr[i]=arr[child];
		}
		else{
			//                。 
			break;
		}
		
	} 
	//      ，                     
	arr[i]=temp; 
} 
void heap_sort(int arr[],int n){
	int i;
	//  
	for(i=n/2;i>=0;i--){
		perc_down(arr,i,n);
	}
	//                ，      
	for(i=n-1;i>0;i--){
		//                
		swap(&arr[0],&arr[i]);
		//      
		perc_down(arr,0,i);
	}
}
//    
//   ，               
void merge(int arr[],int temp_arr[],int left_start,int right_start
			,int right_end)
{
	int i,temp_start,elem_num,left_end;
	temp_start=left_start;
	left_end=right_start-1;
	elem_num=right_end-left_start+1;
	//     
	while(left_start<=left_end&&right_start<=right_end){
		if(arr[left_start]<=arr[right_start]){
			temp_arr[temp_start++]=arr[left_start++];
		}
		else{
			temp_arr[temp_start++]=arr[right_start++];
		}
	}	
	while(left_start<=left_end){
		temp_arr[temp_start++]=arr[left_start++];
	}		
	while(right_start<=right_end){
		temp_arr[temp_start++]=arr[right_start++];
	}
	//     ，  ，               ，        
	for(i=0;i<elem_num;i++,right_end--) {
		arr[right_end]=temp_arr[right_end];
	}
} 
//   ，      ，       
void m_sort(int arr[],int temp_arr[],int left,int right){
	//tra_arr(arr,10);
	int center;
	//      
	if(left<right){
		center=(right+left)/2;
		m_sort(arr,temp_arr,left,center);
		m_sort(arr,temp_arr,center+1,right);
		merge(arr,temp_arr,left,center+1,right);
	} 
} 
//   ，       
void merge_sort(int arr[],int n){
	int *temp_arr;
	temp_arr=(int*)malloc(n*sizeof(int));
	m_sort(arr,temp_arr,0,n-1);
	free(temp_arr);
} 

//    
//  ，         ,   “  ” （  ） 
int get_pri(int arr[],int left,int right){
	int center=(left+right)/2;
	if(arr[left]>arr[center]){
		swap(&arr[left],&arr[center]);
	}
	if(arr[left]>arr[right]){
		swap(&arr[left],&arr[right]);
	}
	if(arr[center]>arr[right]){
		swap(&arr[center],&arr[right]);
	}
	//          ，                   
		swap(&arr[center],&arr[right-1]);
		
	return arr[right-1];
	
} 
//  ，      
void q_sort(int arr[],int left,int right){
	int i,j,pri;
	//          ，         ，     
	if(right-left>=3){
		//   
		pri= get_pri(arr,left,right);
		//             i,j
		i=left;
		j=right-1;
		//    
		while(1){
			//    i        ，     
			while(arr[++i]<pri);
			//     i        ，    
			while(arr[--j]>pri);
			//    ，       ， i j        
			//  
			if(i<j){
				swap(&arr[i],&arr[j]);
			} 
			else{
				break;
			}
		} 
		swap(&arr[i],&arr[right-1]);
		//  i       ,  i            
		//                  
		q_sort(arr,left,i-1);
		q_sort(arr,i+1,right); 
	}
	//              
	//         
	else{
		/*       
		              
		    ，              
		         left     ，  left       
		  0，     n      */ 
		insert_sort(arr+left,right-left+1);
	}
	
} 
//      
void quick_sort(int arr[],int n){
	q_sort(arr,0,n-1);
} 
//    
void tra_arr(int arr[],int n){
	for(int i=0;i<n;i++){
		printf("%d  ",arr[i]);
	}
	printf("
");
} 

이상 은 C 언어의 모든 고전 정렬 방법의 실현 코드 에 대한 상세 한 내용 입 니 다.C 언어 정렬 방법 에 관 한 자 료 는 우리 의 다른 관련 글 을 주목 하 세 요!