빠 른 정렬 알고리즘 및 최적화 (자바 구현)

빠 른 정렬 사상: 1. 기준 찾기: high, low, temp 를 정의 하고 tmp = low 값 을 먼저 양보 합 니 다. high 위치 에서 tmp 보다 작은 값 을 찾 습 니 다. 없 으 면 high – 있 으 면 low 값 을 high 값 과 같 게 한 다음 에 low 위치 에서 tmp 보다 큰 값 을 찾 습 니 다. 없 으 면 low + 가 있 으 면 high 값 을 low 값 과 같 게 한 다음 에 high 위치 에서 tmp 보다 작은 값 을 찾 습 니 다. 이런 식 으로 유추 합 니 다.high 와 low 가 만 나 서 low 로 돌아 갈 때 까지 (이때 의 기준) 기준 을 찾 는 전 과정 은 tmp 값 (즉 기준 치) 과 비교 합 니 다. 한 번 에 기준 을 찾 으 면 기준 왼쪽 은 기준 보다 작은 수 이 고 기준 오른쪽 은 기준 보다 큰 수 이지 만 필요 없습니다.2. 기준 에 따라 정렬 을 계속 해 야 하 는 지 여 부 를 판단 합 니 다. 기준 양측 에 하나의 요소 만 남 았 을 때 기준 을 찾 지 않 아 도 됩 니 다 (기 존 순서)
빠 른 정렬 시간 복잡 도 O (n * log2n) 가 가장 느 린 O (n ^ 2)
빠 른 정렬 의 시간 복잡성 분석: 정렬 은 대체적으로 다음 그림 에서 보 듯 이 1 부터 8 까지 정렬 할 수 있다 고 가정 하면 빠 른 정렬 은 log 2 (8) = 3 번 으로 매번 n 개 수 를 한 번 처리 하기 때문에 그의 시간 복잡 도 는 n * log 2 (n) 이다.따라서 정렬 문제 의 시간 복잡 도 는 정렬 데이터 에 대한 총 조작 횟수 라 고 볼 수 있다.

public class Fastsort {

public static int partion(int[] array,int low,int high){
	int tmp = array[low];
	while(low= tmp){
			--high;
		}
		if(low >= high){
			break;
		}else{
			array[low] = array[high];
			}
		while(low=high){
			break;
		}else{
			array[high]=array[low];
		}
	}
	    array[low]=tmp;
	    return low;
}

기준 세 가지 방법 찾기:
고정 위치 법: low 값 은 마지막 기준 값 입 니 다. 만약 에 low 값 이 모든 요소 의 최소 값 (또는 요소 가 질서 가 있 음) 이 라면 처음으로 기준 을 찾 는 과정 은 아무것도 하지 않 은 것 과 같 습 니 다.

       //1.      
       public static void Quick(int array[],int low,int high){
	      int par = partion(array,low,high);//     
	      if(par>low+1){//    
	      Quick(array,low,par-1);
	      }
	      if(par

무 작위 기준 법: 요소 에서 무 작위 로 하나의 수 를 찾 고 low 에 부여 하여 고정 위치 법의 부족 한 점 을 피한다.

      //2.    
   public static void new_Quick1(int array[],int low,int high){
	   Random rand = new Random();
	    int randNumber = rand.nextInt(high-low+1) + low;
	    swap(array,low,randNumber);
	    
	   int par = partion(array,low,high);//     
	   if(par>low+1){//    
		new_Quick1(array,low,par-1);
	}
	   if(par

3 점 추출 기준: low 와 high 아래 표 시 된 중간 값 mid 를 찾 아 mid 값 을 low 위치 에 두 고 low 값 을 mid 위치 에 두 면 가능 한 한 중간 크기 의 값 을 tmp 값 (기준 값) 으로 만 들 수 있 습 니 다.

      //3.      
 		/*    ：       low、mid、high       ，               */ 
 		public static int med(int[] array,int low,int high) { 
 			int mid = low + ((high - low) >> 1);//            
 			//            
 			if (array[mid] > array[high]) {    //  : array[mid] <= array[high]
 				swap(array,mid,high);
 				} 
 			if (array[low] > array[high]) {    //  : array[low] <= array[high] 
 				swap(array,low,high);
 				} 
 			if (array[mid] > array[low]) {    //  : array[low] >= array[mid]  
 				swap(array,mid,low); 
 				} 
 			//  ，array[mid] <= array[low] <= array[high] 
 			return array[low]; 
 			//low                
 			//         low         ，           } 
 			}
 		public static void new_Quick2(int[] array,int low,int high){  
 	        med(array,low,high);  
 	        int par = partion(array,low,high);  
 	        if(par > low+1){  
 	        new_Quick2(array,low,par-1);  
 	        }  
 	        if(par < high-1){  
 	        new_Quick2(array,par+1,high);  
 	        }  
 	    }  

빠 른 배열 최적화 1: 요소 가 적 을 때 직접 삽입 합 니 다.

 //  1.         
 	public static void insrtSort(int[] array,int low,int high){
 		int temp = 0;
 		int j;
 		for(int i = low+1;i <=high;i++){
 			temp = array[i];// i         。
 			for(j =i-1;j >= 0;j--){
 				if(array[j] > temp){
 					array[j+1]=array[j];
 				} else {//            ，      temp  。
 					break;
 				}
 			}
 			array[j+1] = temp;
 		}
 	}
 	public static void new_Quick3(int[] array,int low,int high){
 		if(high-low+1 < 10){
 			insrtSort(array,low,high);
 			return;
 		}else{
 			swap(array,low,(int)(Math.random())%(high-low)+low);
 			int par = partion(array,low,high);
 			if(par > low+1){
 			new_Quick3(array,low,par-1);
 			}
 			if(par < high-1){
 			new_Quick3(array,par+1,high);
 			}
 		}
 	}

빠 른 배열 최적화 2: 같은 요 소 를 모 아 기준 좌우 양측 과 기준 이 같은 요 소 를 모 은 다음 에 기준 이 같은 요소 의 양 끝 이외 의 요 소 를 계속 정렬 합 니 다.

	//  2.       
 		public static void new_Quick4(int[] array,int low,int high){
 			int[] a;
 			int par = partion(array,low,high);
 			int left = par-1;
 			int right = par+1;
 			a=focusNum(array,low,high,par,left,right);
 			left = a[0];
 			right = a[1];
 			if(par > low+1){
 			new_Quick4(array,low,left);
 			}
 			if(par < high-1){
 			new_Quick4(array,right,high);
 			}
 		}
 		private static int[] focusNum(int[] array, int low, int high, int par,
 				int left, int right) {
 			//  
 			int tmp = 0;
 			int par_left = par-1;
 			int par_right = par+1;
 		    
 			//   
 			for(int i = par-1;i >= low;i--){
 				if(array[i] == array[par]){
 					if(i != par_left){
 						tmp = array[par_left];
 						array[par_left] = array[i];
 						array[i] = tmp;				
 						par_left--;
 					}else{
 						par_left--;
 					}
 					
 				}
 			}
 			left = par_left;
 			//   

 			for(int i = par+1;i <= high;i++){
 				if(array[i] == array[par]){
 					if(i != par_right){
 						tmp = array[par_right];
 						array[par_right] = array[i];
 						array[i] = tmp; 						
 						par_right++;
 					}else{
 						par_right++;
 					}
 					
 				}
 			}
 			right = par_right;
 			int[] a = new int[2];
 			a[0] = left;
 			a[1] = right;
 			return a;
 		}