자바 는 쌓 기 정렬 과 도 해 를 실현 합 니 다.

더미 정렬 기본 소개
1.쌓 기 정렬 은 쌓 기 라 는 데이터 구 조 를 이용 하여 디자인 한 정렬 알고리즘 이다.쌓 기 정렬 은 선택 정렬 이다.가장 나 쁘 고 가장 좋 으 며 평균 시간 복잡 도 는 모두 O(nlogn)이 고 불안정 정렬 이다.
2.더 미 는 다음 과 같은 성질 을 가 진 완전 이 진 트 리 입 니 다.모든 노드 의 값 은 좌우 아이의 노드 의 값 보다 크 거나 같 습 니 다.큰 꼭대기 더미 라 고 부 릅 니 다.주의:노드 를 요구 하지 않 는 왼쪽 아이의 값 과 오른쪽 아이의 값 의 크기 관계 입 니 다.
3.모든 결점 의 값 은 그 좌우 아이의 결점 의 값 보다 작 거나 같 아서 작은 지붕 더미 라 고 부른다.
4.큰 무더기 의 예 를 들 어 설명 한다.

큰 지붕 더미 의 특징:arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2] // i 몇 번 째 노드 에 대응 하고 i 는 0 부터 번 호 를 매 긴 다.
5.작은 지붕 더미 예 를 들 어 설명 한다.

작은 지붕 더미:arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2] // i 몇 번 째 노드 에 대응 하고 i 는 0 부터 번 호 를 매 긴 다.
6.일반적인 상승 순 서 는 큰 지붕 더 미 를 사용 하고 내 림 순 서 는 작은 지붕 더 미 를 사용한다.
정렬 기본 사상
1.정렬 대기 서열 을 하나의 큰 지붕 더미 로 구성한다.
2.이때 전체 서열 의 최대 치 는 바로 지붕 의 뿌리 노드 이다.
3.이 를 마지막 요소 와 교환 하면 끝 이 최대 치 입 니 다.
4.그리고 남 은 n-1 개의 요 소 를 하나의 더미 로 재 구성 하면 n 개의 요소 의 작은 값 을 얻 을 수 있 습 니 다.이렇게 반복 적 으로 집행 하면 질서 있 는 서열 을 얻 을 수 있다.
큰 무 더 기 를 구축 하 는 과정 에서 요소 의 개수 가 점점 줄 어 들 고 마지막 에 질서 있 는 서열 을 얻 는 것 을 볼 수 있다.
정렬 도해 쌓 기
단계 1
구조 초기 더미.주어진 무질서 한 서열 을 큰 꼭대기 로 구성 하 다.
1.주어진 무질서 서열 구 조 는 다음 과 같다 고 가정 한다.

2.이때 우 리 는 마지막 비 엽 결점 부터(엽 결점 은 자연히 조정 할 필요 가 없다.첫 번 째 비 엽 결점 arr.length/2-1=5/2-1=1,즉 아래 의 6 결점)왼쪽 에서 오른쪽으로,아래 에서 위로 조정 한다.

3.두 번 째 비 엽 노드 4 를 찾 습 니 다.[4,9,8]에서 9 요소 가 가장 크 고 4 와 9 가 교환 되 기 때 문 입 니 다.

4.이때 교환 으로 인해 자근[4,5,6]의 구조 가 혼 란 스 럽 고 계속 조정 되 었 다.[4,5,6]에서 6 이 가장 크 고 4 와 6 을 교환 했다.

이때 우 리 는 무질서 한 서열 을 큰 꼭대기 로 만 들 었 다.
단계 2
쌓 인 요소 와 끝 요 소 를 교환 하여 끝 요 소 를 최대 로 합 니 다.그리고 더 미 를 계속 조정 한 다음 에 더 미 를 마지막 요소 와 교환 하여 두 번 째 로 큰 요 소 를 얻 을 수 있 습 니 다.이렇게 교환,재건,교환 을 반복 한다.
1.쌓 아 올 린 원소 9 와 끝 원소 4 를 교환 합 니 다.

2.구 조 를 재 조정 하여 쌓 인 정 의 를 계속 만족 시 킵 니 다.

3.쌓 인 요소 8 과 마지막 요소 5 를 교환 하여 두 번 째 로 큰 요 소 를 얻 을 수 있 습 니 다.

4.후속 과정 을 계속 조정 하고 교환 하 며 이렇게 반복 적 으로 진행 하면 최종 적 으로 전체 순서 가 질서 가 있 게 된다.

코드 구현

      public static void headSort(int[] arr){
        //     ，               
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjust(arr,i,arr.length);
        }
        //              ，       ，       
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            adjust(arr,0,i);
        }
    }
    /**
     *
     * @param arr      
     * @param i          
     * @param length
     */
    public static void adjust(int[] arr,int i,int length){
        int temp = arr[i];
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            if((k + 1) < length && arr[k] < arr[k + 1])
                k++;
            if(arr[k] > temp){
                arr[i] = arr[k];
                i = k;
            }else
                break;
        }
        arr[i] = temp;
    }

총결산
이 글 은 여기까지 입 니 다.당신 에 게 도움 을 줄 수 있 기 를 바 랍 니 다.또한 당신 이 우리 의 더 많은 내용 에 관심 을 가 져 주 실 수 있 기 를 바 랍 니 다!