복단대학 교 961 - 데이터 구조 - 제4 장 - 정렬 (2) 거품 정렬, 빠 른 정렬;정렬

961 모든 내용 링크
글 목록

교환 정렬

거품 정렬

빠 른 정렬

정렬 선택

간단하게 정렬 선택

더미 정렬

교환 정렬
교환 정렬 은 두 요소 의 위 치 를 교환 한 다음 에 이 루어 지 는 정렬 입 니 다.정렬 과정 에서 두 요 소 를 자주 교환 해 야 하 는 위치 입 니 다.
거품 정렬
이것 은 비교적 기본 적 인 정렬 알고리즘 이 므 로 배우 지 않 아 도 스스로 생각 할 수 있 을 것 이다.대체적인 원 리 는 기포 가 위로 솟 아 오 르 는 것 과 같다.기본 사상 은 마지막 요소 부터 순서대로 앞의 요소 와 비교 하고 앞의 요소 보다 작 으 면 두 요소 가 위 치 를 교환 하여 첫 번 째 요소 와 비교 할 때 까지 하 는 것 이다.그리고 다음 라운드 에 들 어가 서 마지막 요소 부터 비교 하기 시 작 했 습 니 다. 이번 에는 두 번 째 요 소 를 비교 하고 아까 의 동작 을 반복 하 며 순서대로 유추 합 니 다.

public static void bubbleSort(Comparable[] array) {
     
    if (array == null) return;

    //             0 ，            1 ，    ， n    ，     
    for (int i = 0; i < array.length - 1; i++) {
     
        boolean flag = false; //   flag，         ，        ，      ，        
        //        ，      ，     i  。
        for (int j = array.length - 1; j > i; j--) {
     
            if (array[j].compareTo(array[j - 1]) < 0) {
      //          ，       ，        
                Comparable temp = array[j - 1];
                array[j - 1] = array[j];
                array[j] = temp;
                flag = true;
            }
        }
        if (!flag) return;  //                    ，      ，          
    }
}

오류 점:

flag 를 추가 하 는 것 을 잊 지 마 세 요. 만약 에 특정한 라운드 가 교환 되 지 않 았 다 면 질서 가 있 고 후속 적 인 대 비 를 할 필요 가 없습니다

1 층 for 순환, i

2 층 for 순환, j > i 는 j > 0 보다 크 더 라 도 최종 결과 에 영향 을 주지 않 지만 매 라운드 쓸데없는 대 비 를 많이 하여 효율 에 큰 영향 을 미친다.

복잡 도 분석:

시간 복잡 도: 가장 좋 은 시간 복잡 도 는 O (n) 이 고 평균 시간 복잡 도와 최 악의 시간 복잡 도 는 O (n ^ 2)

이다.

공간 복잡 도: O (1)

안정성: 안정 적.두 원소 가 교 환 될 때, 같 으 면 교환 이 일어나 지 않 는 다
적용 성: 순서 저장 과 체인 저장 이 모두 가능 합 니 다.
빠 른 정렬
빠 른 정렬 도 교환 을 이용 합 니 다. 기본 사상 은 매번 하나의 요 소 를 최종 위치 에 두 는 것 입 니 다. 즉, 배열 이 순 서 를 정 한 후에 있어 야 할 위치 입 니 다.구체 적 인 방법 은 먼저 하나의 요 소 를 '중추 (pivot)' (예 를 들 어 첫 번 째 요 소 를 선택) 로 선정 한 다음 에 첫 번 째 비교 교환 을 통 해 배열 을 세 부분 으로 나 누 었 다. '중추 보다 작다', '중추', '중추 보다 크다' 는 과정 을 파 티 션 이 라 고 부른다.그리고 중추 보다 작은 부분 과 중추 보다 큰 부분 에 대해 다시 같은 조작 을 한다.최종 적 으로 빠 른 정렬 이 완료 되 었 습 니 다.
예 를 들 어 무질서 수열 8975339012 에 대해 빠 른 정렬 을 한다.
8
9
7
5
3
3
9
0
1
2
제1 라운드
7
5
3
3
0
1
2
8 (pivot)
9
9
이차
5
3
3
0
1
2
7(pivot)
8
9(pivot)
9
제3 차
3
3
0
1
2
5(pivot)
7
8
9
9
제4 라운드
0
1
2(pivot)
3
3
5
7
8
9
9
이 예 에서:

1 차 는 8 을 중심 으로 선택 한 다음 에 8 을 최종 위치 에 놓 았 다. 왼쪽 은 모두 8 보다 작고 오른쪽 은 모두 8 보다 크다.

2 차 는 8 왼쪽 과 오른쪽 요 소 를 재 귀적 으로 1 작업 을 수행 할 것 이다.그래서 2 차 왼쪽 중 추 는 7 이 고 오른쪽 중 추 는 9 이다.

이후 순차 유추

Java 코드:

public static void quickSort(Comparable[] array) {
     
    if (array == null) return;
    quickSort(array, 0, array.length - 1); //            
}

private static void quickSort(Comparable[] array, int left, int right) {
     
    if (left >= right) return; //            ，             ，    。      ，           。
    //   [left,right]          partition  ，            ，       ，           
    int position = partition(array, left, right);
    quickSort(array, left, position - 1);  // partition ，            
    quickSort(array, position + 1, right); //             
}

private static int partition(Comparable[] array, int left, int right) {
     
    int pivotPosition = left;  //   left   ，     left    ，         
    Comparable pivot = array[left];  //     
    left++;  // left          ，  +1
    while (left <= right) {
       //  left  right     ，  ，left right         ，                   。
        if (array[left].compareTo(pivot) > 0) {
       //   left      ，  right    ，  right      ， -1
            Comparable temp = array[left];
            array[left] = array[right];
            array[right] = temp;
            right--;
        } else {
       //   left         ，       ，left      。
            left++;
        }
    }

    //       ，right              ，right          。
    //        right     。                    ，              。
    //    right = left - 1，  right     left-1
    Comparable temp = array[pivotPosition];
    array[pivotPosition] = array[right];
    array[right] = temp;
    return right; //        
}

오류 점:

재 귀적 인 quickSort 에서 if (left > = right) return;이 코드 는 무시 하기 쉬 워 서 재 귀 무한 순환 을 초래 합 니 다

partition 의 while 순환, left < = right 는 등호 가 누락 되 기 쉬 우 며, left 와 right 가 겹 치면 순환 이 뛰 어 나 마지막 요소 가 partition 에 의 해 되 지 않 았 다 고 생각 합 니 다.

partition 의 과정 은 다양 하 다. 즉, left 와 right 포인터 의 이동 방식, 초기 위치 등 여러 가지 쓰기 가 가능 하 다.결과 만 맞 으 면 돼.

복잡 도 분석:

공간 복잡 도: 가장 좋 은 상황, 즉 매번 partition 작업 을 한 후에 중심 은 중간 위치 에 있 습 니 다. 이렇게 재 귀 작업 창고 의 최대 깊이 는 log n 이기 때문에 가장 좋 은 공간 복잡 도 는 O (log n) 이 고 평균 상황 도 마찬가지 입 니 다.그러나 요소 가 처음에 질서 가 있 었 다 면 매번 partition 작업 을 한 후에 중심 은 맨 왼쪽 에 있 었 고 재 귀 호출 스 택 의 깊이 는 n - 1 이 었 기 때문에 최 악의 공간 복잡 도 는 O (n)

였 다.

시간 복잡 도: 최 악의 상황 과 공간 효율 이 유사 하고 가장 좋 은 시간 복잡 도 는 O (n * log n) 이 며 최 악의 시간 복잡 도 는 O (n ^ 2)

이다.
안정성: 불안정.파 티 션 을 진행 하 는 과정 에서 두 개의 같은 요소 의 상대 적 인 위치 가 바 뀔 수 있 습 니 다.
적용 성: 순차 저장 에 만 적 용 됩 니 다.
정렬 선택
정렬 을 선택 하 는 사고방식 은 매번 배열 에서 가장 작은 요 소 를 선택 하여 배열 의 앞 에 놓 는 것 이다.
단순 선택 정렬
정렬 을 선택 하 는 사상 을 직접 이용 하 는 것 은 다른 꾀 가 없다.기본 사상: 배열 의 0 위 부터 배열 의 정렬 되 지 않 은 배열 에서 가장 작은 요 소 를 선택 하여 이 위치 와 교환 합 니 다.뒤 는 이런 식 으로 유추 하 다
Java 코드:

public static void selectSort(Comparable[] array) {
     
    for (int i=0; i <array.length - 1; i ++) {
     
        int min = i;
        for (int j=i+1; j<array.length; j++) {
     
            if (array[min].compareTo(array[j]) > 0) min = j;
        }

        if (i != min) {
     
            Comparable temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
    }
}

오류 점:

1 차 층 for 순환, i

순환 이 끝 날 때의 if (i! = min) 판단 은 추가 하지 않 아 도 된다. 만약 에 똑 같 으 면 바 꿔 도 아무것도 없다

복잡 도 분석: 공간 복잡 도: O (1) 시간 복잡 도: 가장 좋 고 최 악, 평균 시간 복잡 도 는 모두 O (n ^ 2)
안정성: 불안정.배열 이 {2, 2, 1} 이 라 고 가정 하면 간단하게 정렬 한 후에 {1, 2, 2} 이 됩 니 다.2 의 상대 적 위치 에 변화 가 생 겼 다
적용 성: 순서 저장 과 체인 저장 에 적 용 됩 니 다.
더미 정렬
쌓 기 정렬 은 이러한 데이터 구 조 를 쌓 는 데 사용 되 는 응용 이다.쌓 기 정렬 의 기본 사상 은 배열 을 큰 뿌리 더미 로 구축 하 는 것 이다.그리고 큰 뿌리 에 쌓 인 요 소 를 팀 에서 내 고 다시 큰 뿌리 로 쌓 은 다음 에 팀 을 나 간다.
구체 적 으로 쌓 기 작업 은 앞의 장절 의 '우선 대기 행렬 과 쌓 기' 를 복습 합 니 다.
자바 코드 는 다음 과 같 습 니 다:

public static void heapSort(Comparable[] array) {
     
    int size = array.length; //     

    //       : i<=size/2-1     ，       （i>size/2-1）
    //        ：           ，     ，           。
    for (int i = size / 2 - 1; i >= 0; i--) {
     
        percolateDown(array, i, size);
    }

    while (size > 0) {
     
        //               ，             ，       -1
        Comparable temp = array[size - 1];
        array[size - 1] = array[0];
        array[0] = temp;
        size--;

        percolateDown(array, 0, size); //            ，     
    } //      ，    
}

private static void percolateDown(Comparable[] array, int i, int size) {
     
    Comparable x = array[i];  //         

    while (i <= size / 2 - 1) {
     
        int child = i * 2 + 1; //         
        if (child + 1 < size && array[child].compareTo(array[child + 1]) < 0) {
     
            child++; //         ，         ，  child        
        }
        if (x.compareTo(array[child]) < 0) {
      //   x           ，     
            array[i] = array[child]; //                   
            i = child; // i         ，     
        } else {
     
            //   x           ，     ，    
            break;
        }
    } //          ，     ，     ，     
    array[i] = x; //      ，        
}

오류 점:

이 무 더 기 는 0 부터 계산 하기 때문에 아이 노드 의 계산 공식 은 i 이다.×2 + 1 (왼쪽 아이), i×2 + 2 (우 아이)

잎 노드 공식: i < = size / 2 - 1 은 잎 노드 이 고 그렇지 않 으 면 분기 노드 (i > size / 2 - 1)

쌓 을 때 for 순환, i > = 0, 등 호 를 무시 할 수 없습니다. 쌓 인 요소 도 거 르 기 때 문 입 니 다.

쌓 인 꼭대기 에서 원 소 를 꺼 낼 때마다 쌓 인 size 를 1

줄 이 는 것 을 잊 지 마 세 요.

아래 필터 코드 에서 좌우 아이의 큰 시간 을 판단 하고 부모 노드 를 교체 하기 전에 부모 노드 와 아이의 노드 의 크기 를 판단 하 는 것 을 잊 지 마 세 요.나 는 매번 잊 기 쉽다.만약 아버지의 노드 가 그의 아이 보다 크다 면 더 이상 거 르 지 않 아 도 된다.

아이의 크기 를 판단 한 후에 i 값 이 아이의 노드 를 가리 키 는 것 을 잊 지 마 세 요.

복잡 도 분석: 공간 복잡 도: 추가 공간 을 사용 하지 않 았 습 니 다.공간 복잡 도 O (1) 시간 복잡 도: 쌓 는 데 소요 되 는 시간 O (n) 를 다음 에 n - 1 회 아래로 조정 하고 매번 조 정 된 시간 복잡 도 는 O (h) 이 며 h 는 나무 높이 이다.그래서 가장 좋 고 최 악의 경우 정렬 시간 복잡 도 는 O (n * log n) 이다.
안정성: 불안정.첫 번 째 노드 와 바닥 요 소 를 교환 해 야 하기 때문이다.그래서 상대 적 인 위치 변화 가 생 길 수 있 습 니 다.예 를 들 어 {1, 2, 2} 은 큰 뿌리 더 미 를 구축 한 후에 {2, 2, 1} 이 고 마지막 에 내 려 와 {1, 2, 2} 이 되 었 다.