거품, 선택, 삽입, 이분 정렬 알고리즘

3871 단어 데이터 구조
거품 정렬:
먼저, 거품 정렬 은 거품 정렬 이 라 고도 부 릅 니 다. 여기 서 정렬 두 가지 거품 정렬 을 정 리 했 습 니 다. 하 나 는 일반적인 거품 정렬 입 니 다. 하 나 는 최적화 한 후에 거품 이 나 는 것 입 니 다. 거품 정렬 은 첫 번 째 로 다른 모든 수 를 비교 하 는 것 입 니 다. 한 번 의 비 교 를 통 해 이 데이터 의 가장 큰 데 이 터 를 찾 아 첫 번 째 로 모두 비교 (n - 1 번) 해 야 합 니 다. 그 다음 에 첫 번 째 숫자 부터 두 번 째 큰 숫자 (n - 2 번) 를 찾 습 니 다.이런 식 으로 유추 하 다.
첨부 코드 는 다음 과 같 습 니 다:
        public void swap(int[]a, int i, int j){
		int temp = a[i];
		a[i]=a[j];
		a[j]=temp;
	}
	public void print(int a[]){
		for(int x:a){
			System.out.print(x+" ");
		}
		System.out.println();
	}
        1.1    
	@Test
	public void bubbleSort(){
		int a[]={21,25,49,25,16,8};
		print(a);
		
		for(int i=0;ia[j+1]){
					swap(a,j,j+1);
				}
			}
		}
		print(a);
	}

최적화 후의 거품 정렬 이란 정렬 과정 에서 특정한 데이터 가 교환 되 지 않 은 것 을 발견 한 후에 정렬 할 필요 가 없다 는 것 이다.
첨부 코드 는 다음 과 같 습 니 다:
        @Test
	public void bubbleSort2(){
		int a[]={21,25,49,25,16,8};
		print(a);
		
		for(int i=0;ia[j+1]){
					swap(a,j,j+1);
					boo=true;
				}
			}
			if(!boo){
				break;
			}
		}
		print(a);
	}

정렬 선택:
여기 서 정렬 을 선택 하면 저도 정리 한 두 가지 정렬 알고리즘 중 하 나 는 일반적인 선택 정렬 입 니 다. 하 나 는 최적화 된 선택 정렬 이 있 고 정렬 을 선택 하 는 사고 도 간단 합 니 다. 즉, 모든 숫자 가 뒤의 숫자 와 비교 하 는 것 입 니 다. 여기 서 저 는 여러분 의 '핸드폰 바 꾸 기' 를 예 로 들 겠 습 니 다.
일반 선택 정렬:
첨부 코드 는 다음 과 같 습 니 다:
   @Test
   public void selectSort(){
	   int a[]={21,25,49,25,16,8,-1,0,23,44};
	   print(a);
	   
	   for(int i=0;ia[j]){
				   k=j;//          
			   }
		   }
		   if(i!=k){
			   swap(a,i,k);
		   }
	   }
	   print(a);
   }

최적화 후 정렬 선택:
첨부 코드 는 다음 과 같 습 니 다:
   @Test
   public void selectSort0(){
	   int a[]={21,25,49,25,16,8,-1,0,23,44};
	   print(a);
	   
	   for(int i=0;ia[j]){
				   swap(a,i,j);//   :           a[i]  
			   }
		   }
	   }
	   print(a);
   }

삽입 정렬:
정렬 알고리즘 을 삽입 하 는 것 은 순서대로 모든 요 소 를 질서 있 는 서열 에 삽입 하 는 것 입 니 다. (처음에 첫 번 째 요 소 는 움 직 이지 마 세 요. 질서 가 있 는 것 으로 볼 수 있 습 니 다. 따라서 배열 할 때 2 ~ n 번 째 숫자 만 고려 하고 뒤에서 삽입 합 니 다. 앞의 숫자 가 삽입 할 숫자 보다 크 면 앞의 숫자 를 한 자리 뒤로 이동 합 니 다. 여기 서 저 는 2 점 과 삽 입 된 정렬 알고리즘 을 결합 시 켰 습 니 다!
일반적인 삽입 정렬:
첨부 코드 는 다음 과 같 습 니 다:
 @Test
   public void insertSort(){
	   int a[]={21,25,49,25,16,8,-1,0,23,44};
	   print(a);	   
	   //                 (    , 1      ,       。          2~n  
	   for(int i=0;itemp){//       " j    "   "temp(     )"  ,  a[j]       
			   a[j+1]=a[j];
			   j--;
			   if(j<0){
				   break;
			   }
		   }		   
		   //     ,  temp a[j]        (j -1)。  temp   a[j+1]		   
		   a[j+1]=temp;//  j   
	   }
	   print(a);
   }

★ 2 점 은 반드시 질서 가 있어 야 한다. 질서 가 있 으 면 2 점 을 고려 해 야 한다.
이분법 은 데 이 터 를 두 단락 으로 나 누 는 것 이다. 먼저 삽입 해 야 할 수 와 질서 있 는 중간 위치의 수 를 비교 하면 반 의 비 교 량 을 줄 일 수 있다. 여기 서 나 는 삽입 정렬 알고리즘 과 이분의 정렬 알고리즘 을 결합 시 켰 다.
첨부 코드 는 다음 과 같 습 니 다:
   @Test
   public void insertSort2(){
	   int a[]={21,25,49,25,16,8,-1,0,23,44};
	   print(a);	   
	   //                 (    , 1      ,       。          2~n  
	   for(int i=0;itemp){//temp    
				   high = mid-1;
			   }else{//temp    
				   low = mid+1;
			   }
		   }//   ,low   --     high   		   
		   //    (high+1)   ,  high+1                
		   //  ,     
		   for(int j=i;j>high;j--){
			  a[j+1]=a[j]; 
		   }		  
		   //     ,  temp a[j]        (j -1)。  temp    a[j+1]
		   a[high+1]=temp;//  j   
	   }
	   print(a);
   }

좋은 웹페이지 즐겨찾기