자바 에서 배열 의 정렬 방법 에 대한 집합 분석

1. 거품 정렬

public void bubbleSort(int a[]) {

		int n = a.length;

		for (int i = 0; i < n - 1; i++) 
		{
			for (int j = 0; j < n - 1; j++) 
			{

				if (a[j] > a[j + 1]) 
				{
					int temp = a[j];

					a[j] = a[j + 1];

					a[j + 1] = temp;

				}
			}
		}
	}

먼저 배열 의 첫 번 째 수 를 꺼 낸 다음 에 뒤의 수 를 비교 하면 규칙 은 누가 누 구 를 크게 취 하 는 지, 즉 첫 번 째 라운드 에서 가장 큰 값 을 비교 한 것 이다.
2. 정렬 선택

public void selectiveSort(int arr[]) {
		for (int i = 0; i < arr.length; i++) {
			//                          
			for (int j = i + 1; j < arr.length; j++) {
				//                   ，          ，               
				if (arr[i] > arr[j]) {
					int tep = arr[i];//           ，             
					arr[i] = arr[j];
					arr[j] = tep;

				}
			}
		}
	}

3. 빠 른 정렬
* 빠 른 정렬 은 거품 정렬 에 대한 개선 입 니 다.
* 그의 기본 적 인 사상 은 누 워 서 정렬 할 데 이 터 를 독립 된 두 부분 으로 나 누 는 것 이다. 그 중에서 일부분 의 모든 데 이 터 는 다른 부분의 모든 데이터 보다 작은 다음 에 다음 과 같은 방법 으로 이 두 부분의 데 이 터 를 각각 신속하게 정렬 하고 전체 정렬 과정 을 재 귀적 으로 진행 하여 전체 데 이 터 를 질서 있 는 서열 로 바 꿀 수 있다.
* 최 악의 경우 시간 복잡 도 는 O (n2), 최 악의 경우 시간 복잡 도 는 O (nlog2n)
정렬 프로 세 스 분석
정렬 할 배열 이 A [1] 라 고 가정 하면... A [N] 은 먼저 하나의 데이터 (보통 첫 번 째 데 이 터 를 선택 합 니 다) 를 관건 적 인 데이터 로 선택 한 다음 에 그 보다 큰 수 를 모두 앞 에 놓 고 그 보다 큰 수 를 모두 뒤에 놓 습 니 다. 이 과정 을 누 워 서 빠 른 정렬 이 라 고 합 니 다.
* 정렬 할 배열 은 A [0]... A [N - 1],
* 우선 하나의 데이터 (보통 첫 번 째 요 소 를 선택) 를 기준점 으로 선택 하고,
* 그리고 그 보다 작은 모든 수 를 그 앞 에 놓 고 그 보다 큰 모든 수 를 그 뒤에 놓 습 니 다. 이 과정 을 빠 른 정렬 이 라 고 합 니 다.
* 그리고 각각 앞 과 뒤의 데 이 터 를 똑 같은 방식 으로 정렬 합 니 다.
* 주의해 야 할 것 은 빠 른 정렬 은 안정 적 인 정렬 알고리즘 이 아 닙 니 다. 즉, 같은 값 의 상대 적 인 위 치 는 알고리즘 이 끝 날 때 변동 이 생 길 수 있 습 니 다.
정렬 과정 은 다음 과 같이 나 눌 수 있 습 니 다.
1. 두 개의 변수 X, Y 를 설정 하고 정렬 이 시 작 될 때 X: = 1, Y: = N;2. 첫 번 째 배열 요 소 를 관건 적 인 데이터 로 하고 number: = A [1] 에 값 을 부여 합 니 다.3. Y 부터 앞으로 검색 합 니 다. 즉, 뒤에서 앞으로 검색 합 니 다 (Y: = Y - 1). 첫 번 째 number 보다 작은 값 을 찾 으 면 두 가 지 를 교환 합 니 다.4. X 부터 뒤로 검색 합 니 다. 즉, 앞에서 부터 뒤로 검색 합 니 다 (X: = X + 1). number 보다 큰 값 을 찾 으 면 두 가 지 를 교환 합 니 다.4. XY = J 까지 3, 4 단 계 를 반복 합 니 다.
예 를 들 어 정렬 할 배열 A 의 값 은 다음 과 같다. (초기 관건 데이터 number: = 49) A [1]  A[2]  A[3]  A[4]  A[5] A[6]  A[7]： 49   38   65   97   76  13   27 첫 교환 후: 27  38  65  97   76  13   49                   ( 알고리즘 의 세 번 째 단계 에 따라 뒤에서 찾기 시작) 두 번 째 교환 후: 27  38  49  97   76  13   65                  ( 알고리즘 의 네 번 째 단계 에 따라 앞에서 부터 > X 의 값 을 찾 습 니 다. 65 > 49, 둘 을 교환 합 니 다. 이때 I: = 3) 세 번 째 교환 후: 27  38 13  97   76  49   65 (알고리즘 의 다섯 번 째 단계 에 따라 알고리즘 을 다시 실행 하 는 세 번 째 단 계 를 뒤에서 찾 습 니 다) 네 번 째 교환 후: 27  38 13  49  76  97   65 (알고리즘 의 네 번 째 단계 에 따라 앞에서 부터 X 보다 큰 값 을 찾 습 니 다. 97 > 49, 둘 을 교환 합 니 다. 이때 J: = 4)     이때 세 번 째 단 계 를 실행 할 때 I = J 를 발견 하고 한 번 누 우 면 빠 른 정렬 을 끝 냅 니 다. 그러면 한 번 누 우 면 빠 른 정렬 을 거 친 결 과 는 27 입 니 다.  38  13   49   76  97   65. 즉, 49 보다 큰 수 는 모두 49 의 뒤에 있 기 때문에 49 보다 작은 수 는 모두 49 의 앞 에 있다.