자바 거품 정렬, 정렬 선택, 정렬 삽입, 힐 정렬

오늘 은 자바 데이터 구 조 를 조금 배 웠 습 니 다. 처음부터 보 았 던 정렬 문 제 를 내 려 다 보 았 습 니 다. 자바 의 기본 적 인 정렬 방법 은 세 가지 가 있 습 니 다. 거품, 선택, 삽입.
예전 에는 정렬 을 선택 하 는 것 이 거품 정렬 이 라 고 생각 했다.책 속 의 해석 을 보고 거품 정렬 과 정렬 선택 을 혼동 해 서 는 안 된다 는 것 을 깨 달 았 다.
소 화 를 통 해 나 는 그들의 원 리 를 조금 알 게 되 었 다.
거품 정렬 은 데이터 a 를 추출 한 다음 에 이 데이터 오른쪽 데이터 b 와 비교 하 는 것 입 니 다. a 가 b 보다 크 면 a 는 오른쪽으로 이동 합 니 다. 즉, b 의 오른쪽 (프로그램 에서 교환 을 통 해 이 루어 질 수 있 습 니 다).두 개의 순환 을 쓰 고 코드 는 다음 과 같다.
 
 

//    
public class BubbleSort
{
	private static int[] total={2,8,1,9,4,11,3,7,5,6,10};
	public static void main(String[] args)
	{
		long start=System.currentTimeMillis();
		//  out >0，    ，                  
		for(int out=total.length-1;out>1;out--)
		{
			for (int i = 0; i < out; i++)
			{
				if(total[i]>total[i+1])
				{
					swap(i,i+1);
				}
			}
		}
		//    
		for(int i=0;i<total.length;i++)
		{
			System.out.print(total[i]+" ");
		}
		long end=System.currentTimeMillis();
		System.out.print("    :"+(end-start));
	}
	public static void swap(int a,int b)
	{
		int temp=total[a];
		total[a]=total[b];
		total[b]=temp;
	}
}

 
 이것 이 바로 거품 서열 이다.
그리고 나 서 나 는 정렬 을 하나의 숫자 a 로 하고 a 와 정렬 되 지 않 은 다른 데 이 터 를 비교 하 는 것 을 이해한다.a 보다 작은 것 이 있 으 면 a 와 위 치 를 교환 합 니 다. 그러면 a 는 정렬 되 지 않 은 데이터 중 가장 작은 것 입 니 다. 코드 는 다음 과 같 습 니 다.
 
 

//    
public class ChooseSort
{
	private static int[] total={2,8,1,9,4,11,3,7,5,6,10};
	public static void main(String[] args)
	{
		long start=System.currentTimeMillis();
		
		for(int i=0;i<total.length-1;i++)
		{
			for(int j=i+1;j<total.length;j++)
			{
				if(total[i]>total[j])
				{
					swap(i,j);
				}
			}
		}
		//    
		for(int i=0;i<total.length;i++)
		{
			System.out.print(total[i]+" ");
		}
		long end=System.currentTimeMillis();
		System.out.print("    :"+(end-start));
	}
	public static void swap(int a,int b)
	{
		int temp=total[a];
		total[a]=total[b];
		total[b]=temp;
	}

} 

 
 정렬 삽입 일부 데이터 부분 은 정렬 된 적 이 있다. 예 를 들 어 왼쪽 1 - 5 번 위치 가 정렬 된 적 이 있다 (작은 위치 에서 큰 위치 로). 6 - 10 위치 가 정렬 되 지 않 으 면 여섯 번 째 위치 데 이 터 를 꺼 낸 다음 에 1 - 5 위치 데 이 터 를 앞으로 이동 할 수 있다 (즉 여섯 번 째 위치 이동). 이동 하기 전에 꺼 낸 여섯 번 째 위치의 데 이 터 를 비교 해 야 한다. 여섯 번 째 위치 보다 큰 데 이 터 는 앞으로 이동 해 야 한다.그렇지 않 으 면 이동 하지 않 고 꺼 낸 여섯 번 째 데 이 터 를 빈 위치 에 다시 채 웁 니 다.코드 는 다음 과 같다.
 
 

//    
public class InsertSort
{
	private static int in;
	private static int[] total={2,8,1,9,4,11,3,7,5,6,10};
	public static void main(String[] args)
	{
		for(int out=1;out<total.length;out++)
		{
			int temp=total[out];
			in=out;
			while(in>0 && total[in-1]>=temp)
			{
				total[in]=total[in-1];
				--in;
			}
			total[in]=temp;
		}
		//    
		for(int i=0;i<total.length;i++)
		{
			System.out.print(total[i]+" ");
		}
	}

}

또 힐 정렬 이라는 정렬 은 정렬 을 삽입 하 는 것 이다.
 

public static<T extends Comparable<? super T>>
			void incrementalSort(T[] a,int first,int last,int space)
	{
		int unsorted,index;
		for(unsorted=first+space;unsorted<=last;unsorted=unsorted+space)
		{
			T firstUnsorted=a[unsorted];
			for(index =unsorted-space;index>=first&&firstUnsorted.compareTo(a[index])<0;index=index-space)
			{
				a[index+space]=a[index];
			}
			a[index+space]=firstUnsorted;
		}
	}
	
	public static<T extends Comparable<? super T>> void shellSort(T[] a,int first,int last)
	{
		int n=last-first+1;
		for(int space=n/2;space>0;space=space/2)
		{
			for(int begin=first;begin<first+space;begin++)
			{
				incrementalSort(a, begin, last, space);
			}
		}
	}

 셸 Sort 를 호출 하면 됩 니 다.