도문 상세 설명 JAVA 빠 른 정렬 실현

고속 성의 정렬 알고리즘
공간 을 낭비 하지 않 고 빨리 정렬 할 수 있 는 알고리즘 이 있 습 니까?바로'빠 른 정렬'입 니 다!이 이름 만 들 어도 고 급 스 럽 지 않 아 요?
우리 가 지금'6,1,2,7,9,3,4,5,10'이라는 10 개의 수 를 정렬 하고 있다 고 가정 해 보 자.우선 이 서열 에서 마음대로 하나의 수 를 기준 으로 한다(이 명사 에 놀 라 지 마라.바로 참조 할 수 있 는 숫자 이다.조금 있 으 면 그것 이 무엇 을 하 는 지 알 게 될 것 이다).편 의 를 위해 서 는 첫 번 째 6 을 기준 으로 합 시다.그 다음 에 이 서열 에 있 는 모든 기준 수 보다 큰 수 를 6 의 오른쪽 에 놓 고 기준 수 보다 작은 수 를 6 의 왼쪽 에 놓 아야 한다.아래 와 같은 배열 이다.
3 1 2 5 4 6 9 7 10 8
초기 상태 에서 숫자 6 은 서열 의 1 위 에 있다.우리 의 목 표 는 6 을 서열 중간의 어느 위치 로 옮 기 는 것 이다.이 위치 가 k 라 고 가정 하 는 것 이다.지금 이 k 를 찾 아야 합 니 다.그리고 k 위 를 분계 점 으로 하고 왼쪽 의 수 는 모두 6 보다 적 으 며 오른쪽 의 수 는 모두 6 보다 큽 니 다.생각해 봐,너 는 이 정도 까지 할 수 있 는 방법 이 있 니?
정렬 알고리즘
방법 은 사실 매우 간단 하 다.각각 초기 서열 인'6,1,2,7,9,3,4,5,10,8'양 끝 에서'탐측'을 시작한다.먼저 오른쪽 에서 왼쪽으로 6 보다 작은 수 를 찾 은 다음 에 왼쪽 에서 오른쪽으로 6 보다 큰 수 를 찾 은 다음 에 그들 과 교환 합 니 다.여 기 는 두 개의 변수 i 와 j 를 사용 하여 각각 서열 의 가장 왼쪽 과 가장 오른쪽 을 가리 킬 수 있다.우 리 는 이 두 변 수 를 위해 듣 기 좋 은 이름 인'보초병 i'와'보초병 j'를 지 었 다.처음에 보초병 i 가 서열 의 맨 왼쪽(즉 i=1)을 가리 키 고 숫자 6 을 가리킨다.보초병 j 가 서열 의 맨 오른쪽(즉=10)을 가리 키 고 숫자 를 가리킨다.
 
우선 보초병 j 가 출동 하기 시작 했다.이곳 에 설 치 된 기준 수 는 가장 왼쪽 숫자 이기 때문에 보초병 j 가 먼저 출동 하도록 해 야 한 다 는 점 이 매우 중요 하 다(왜 그런 지 스스로 생각해 보 세 요).보초병 j 는 6 보다 작은 숫자 를 찾 을 때 까지 한 걸음 한 걸음 왼쪽으로 옮 겼 다.다음 보초병 i 는 6 이상 의 숫자 가 멈 출 때 까지 오른쪽으로 한 걸음 더 움 직 였 다.마지막 으로 보초병 j 는 숫자 5 앞 에 멈 추 었 고 보초병 i 는 숫자 7 앞 에 멈 추 었 다. 
 
 
현재 보초병 i 와 보초병 j 가 가리 키 는 원소 의 값 을 교환 합 니 다.교환 후의 순 서 는 다음 과 같다.
6 1 2 5 9 3 4 7 10 8 
 
 
여기 서 첫 교환 이 끝 났 습 니 다.그 다음 에 보초병 j 가 계속 왼쪽으로 움 직 이기 시작 했다.그 는 4(기준 6 보다 작 아 요 구 를 충족 시 키 는 것)를 발견 하고 멈 추 었 다.보초병 i 도 계속 오른쪽으로 움 직 였 다.그 는 9(기준 6 보다 크 고 요 구 를 만족 시 키 는 것)를 발견 하고 멈 추 었 다.이때 다시 교환 합 니 다.교환 후의 순 서 는 다음 과 같 습 니 다.
6 1 2 5 4 3 9 7 10 8
2 차 교환 이 끝나 고'탐사'가 계속 됐다.보초병 j 는 계속 왼쪽으로 움 직 였 다.그 는 3(기준 6 보다 작 고 요 구 를 만족 시 키 는 것)을 발견 한 후에 다시 멈 추 었 다.보초병 i 계속 오른쪽으로 이동,큰일 났 어!이때 보초병 i 와 보초병 j 가 만 났 고 보초병 i 와 보초병 j 는 모두 3 앞으로 걸 어 갔다.이때'탐지'가 끝났다 는 뜻 이다.우 리 는 기준 수 6 과 3 을 교환 할 것 이다.교환 후의 순 서 는 다음 과 같다.
3 1 2 5 4 6 9 7 10 8
 
 

이로써 1 차 탐측 이 진정 으로 끝났다.이때 기준 수 6 을 분계 점 으로 하고 6 왼쪽 의 수 는 모두 6 보다 적 으 며 6 오른쪽 의 수 는 모두 6 보다 크다.아까 의 과정 을 돌 이 켜 보면 보초병 j 의 사명 은 기준 수 보다 적은 수 를 찾 는 것 이 고 보초병 i 의 사명 은 기준 수 보다 큰 수 를 찾 는 것 이다.i 와 j 가 만 날 때 까지.
OK,설명 완료.현재 기준 수 6 은 이미 제자리 로 돌 아 왔 는데,그것 은 마침 서열 의 6 위 에 있다.이때 우 리 는 원래 의 서열 을 6 을 분계 점 으로 두 개의 서열 로 나 누 었 고 왼쪽 의 서열 은'3,1,2,5,4'이 며 오른쪽 서열 은'9,7,10,8'이다.다음은 이 두 서열 을 각각 처리 해 야 한다.6.왼쪽 과 오른쪽 서열 이 아직 혼 란 스 러 워 서 요.그러나 괜 찮 습 니 다.우 리 는 이미 방법 을 익 혔 습 니 다.그 다음 에 아까 의 방법 을 모 의 해서 각각 6 왼쪽 과 오른쪽의 서열 을 처리 하면 됩 니 다.이제 6 왼쪽 서열 을 처리 하 겠 습 니 다.
왼쪽 서열 은'3,1,2,5,4'다.이 서열 을 3 을 기준 으로 조정 하여 3 왼쪽 의 수 를 모두 3 보다 적 게 하고 3 오른쪽 의 수 는 모두 3 보다 많 게 하 십시오.자,이제 붓 을 들 어 볼 게 요.
만약 당신 이 시 뮬 레이 션 한 것 이 틀 리 지 않 았 다 면,조정 이 끝 난 후의 순 서 는 다음 과 같 아야 합 니 다.
2 1 3 5 4
OK,지금 3 은 귀 위 했 습 니 다.다음은 3 왼쪽 서열 인'21'과 오른쪽 서열 인'54'를 처리 해 야 한다.서열'21'을 2 를 기준 으로 조정 하고 처리 가 끝 난 후의 서열 은'12'이 며 이 2 는 이미 제자리 로 돌 아 왔 다.서열'1'은 하나의 숫자 만 있 고 어떠한 처리 도 할 필요 가 없다.이로써 우 리 는 서열'21'을 모두 처 리 했 고 서열 은'12'이다.서열'54'의 처리 도 이 방법 을 본 떠 서 마지막 으로 얻 은 서열 은 다음 과 같다.
1 2 3 4 5 6 9 7 10 8
시퀀스 인'97108'에 대해 서도 새로운 하위 시퀀스 를 분리 할 수 없 을 때 까지 아까 의 과정 을 모 의 했다.최종 적 으로 이러한 서열 을 얻 게 될 것 이다.다음 과 같다.
1 2 3 4 5 6 7 8 9 10
여기까지 정렬 이 완전히 끝 났 습 니 다.세심 한 학생 들 은 빠 른 정렬 의 모든 라운드 처 리 는 바로 이 라운드 의 기준 수 를 제자리 로 돌려 모든 숫자 가 제자리 로 돌아 갈 때 까지 정렬 이 끝났다 는 것 을 알 게 되 었 을 것 이다.아래 의 위의 패기 있 는 그림 은 전체 알고리즘 의 처리 과정 을 묘사 합 니 다. 

왜 그 럴 까요?
빠 른 정렬 이 빠 릅 니 다.거품 정렬 보다 매번 교환 이 점프 식 이기 때 문 입 니 다.정렬 할 때마다 기준점 을 설정 하고 기준점 보다 작은 수 를 모두 기준점 의 왼쪽 에 놓 으 며 기준점 보다 큰 수 를 모두 기준점 의 오른쪽 에 놓 습 니 다.이렇게 하면 매번 교환 할 때마다 거품 정렬 처럼 매번 인접 한 수 사이 에서 만 교환 할 수 있 고 교환 하 는 거리 가 훨씬 크다.그래서 전체적인 비교 와 교환 횟수 가 적어 지면 서 속도 가 자 연 스 럽 게 높 아 졌 다.물론 최 악의 경우 에 도 인접 한 두 수 를 교환 한 것 으로 보인다.따라서 빠 른 정렬 의 최 악의 시간 복잡 도와 거품 정렬 은 모두 O(N2)이 고 평균 시간 복잡 도 는 O(NLogN)이다.사실 빠 른 순 서 는'이분'이라는 사상 에 기초 한 것 이다.우 리 는 나중에 또'이분'사상 을 만 날 것 이 니 그때 다시 이야기 하 자.먼저 코드 를 올 리 면 다음 과 같다.
코드 구현:

public class QuickSort {
    public static void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i=low;
        j=high;
        //temp     
        temp = arr[low];
 
        while (i<j) {
            //    ，      
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //    ，      
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //         
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
 
        }
        //       i j         
         arr[low] = arr[i];
         arr[i] = temp;
        //        
        quickSort(arr, low, j-1);
        //        
        quickSort(arr, j+1, high);
    }
 
 
    public static void main(String[] args){
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        quickSort(arr, 0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

출력
1
2
2
3
4
4
7
7
8
9
10
19
62
총결산
JAVA 의 빠 른 정렬 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 JAVA 의 빠 른 정렬 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!