복단대학 교 961 - 데이터 구조 - 제4 장 - 정렬 (3) 합병 정렬, 기수 정렬;정렬 알고리즘 복잡 도 총화

961 모든 내용 링크
글 목록

병합 정렬 (병합 정렬)

기수 정렬

정렬 알고리즘 총화

병합 정렬 (병합 정렬)
병합 정렬 과 빠 른 정렬 은 모두 분 치 (분 치) 사상 에 기초 한 것 이다.기본 사상 은 배열 을 두 부분 으로 나 눈 다음 에 이 두 부분 을 정렬 한 다음 에 이 를 합병 하 는 것 이다.이 두 부분 에 대한 정렬 도 병합 정렬 로 재 귀적 으로 진행 된다.
관건 은 어떻게 합병 하 느 냐 에 있다.기본 사상 은 하나의 배열 을 신청 하 는 것 이다. 이 배열 의 크기 는 두 개의 배열 을 합 쳐 야 하 는 총화 이다. 그 다음 에 이 두 배열 의 요 소 를 차례대로 비교 한 다음 에 새로운 배열 에 채 워 야 한다.
예 를 들 면:
배열 A
1
3
5
7
9
↑(i)
배열 B
2
4
6
8
10
↑(j)
합병 후
1
2
3
4
5
6
7
8
9
10
합병 하기 전에 A 배열 은 배열 의 첫 번 째 요 소 를 가리 키 는 i 포인터 가 있 습 니 다.B 배열 은 포인터 j 이 고 첫 번 째 요 소 를 가리킨다.그리고 A [i] 와 B [j] 를 비교 해서 작은 것 을 새 배열 에 넣 고 작은 바늘 을 움 직 입 니 다.예 를 들 어 첫 번 째 A [0] < B [0], 그러면 i = 0 + 1, j 는 움 직 이지 않 는 다.두 배열 의 요소 가 새 배열 에 들 어 갈 때 까지.
자바 코드 는 다음 과 같 습 니 다:

public static void mergeSort(Comparable[] array) {
     
    mergeSort(array, 0 ,array.length - 1);  //            
}

private static void mergeSort(Comparable[] array, int left, int right) {
     
    if (left >= right) return;  //   left>=right，              ，      。

    int mid = (right + left) / 2; //      ，      。
    mergeSort(array, left, mid);  //             
    mergeSort(array, mid + 1, right);  //             
    merge(array, left, right);  //                
}

private static void merge(Comparable[] array, int left, int right) {
     
    int mid = (right + left) / 2;
    Comparable[] temp = new Comparable[mid - left + 1];  //         ，         
    for (int i=0; i <temp.length;i++) {
       //               
        temp[i] = array[left + i];
    }

    int i=0, j = mid + 1;  //      （    ）          
    while (i<temp.length && j < right + 1) {
       //               ，     
        if (temp[i].compareTo(array[j]) < 0) {
       //         ，          left   ，  i++
            array[left] = temp[i];
            i++;
        } else {
     
            array[left] = array[j];  //         ，          left   ，  j++
            j ++;
        }
        left++; //    left++
    }

    for (; i < temp.length; i++) {
       //      ，        ，             。
        array[left] = temp[i];
        left++;
    }

    //         ，       ，         ，   。
}

오류 점:

재 귀적 인 mergeSort 에서 if (left > = right) return;잊 지 마 세 요

mid 를 구 할 때, left + (right - left) / 2 = (left + right) / 2

복잡 도 분석: 공간 복잡 도: O (n) 시간 복잡 도: O (n * log n) 요소 가 아무리 길 어도 하나의 절차 이 고 차이 가 없 을 것 이다.
안정성: 안정.병합 할 때 같은 원소 의 상대 적 인 위 치 를 바 꾸 지 않 습 니 다.
적용 성: 순차 저장 에 만 적 용 됩 니 다.
기수 정렬
기수 정렬 은 다른 정렬 과 다 르 기 때문에 그 는 비교 에 기반 한 정렬 이 아니다.예 를 들 어 이 데 이 터 를 정렬 하 는 것 이다.
89,75,61,77,55,42,78,62,41
① 숫자 로 구성 되 어 있 으 며 ② 한 자리 당 두 자리 수 를 넘 지 않 는 것 이 특징 이다.
숫자 가 10 자리 (기수 (radix) 라 고 부 르 기 때문에 먼저 10 크기 의 배열 을 새로 만 듭 니 다. 이 배열 의 각 칸 을 하나의 통 이 라 고 부 릅 니 다.

그리고 첫 번 째 정렬 을 시작 합 니 다. 첫 번 째 정렬 은 한 자리 에 따라 한 자리 의 값 을 해당 하 는 배열 아래 에 넣 습 니 다.개 비트 가 중복 되면 링크 로 연결 합 니 다. 이 과정 을 분배 라 고 합 니 다. 그림 에서 보 듯 이

0
1
2
3
4
5
6
7
8
9
61
42
75
77
78
89
41
62
55
그 다음 에 배열 의 데 이 터 를 수집 하고 0 부터 차례대로 연결 하 며 이 과정 을 수집 이 라 고 한다.
61->41->42->62->75->55->77->78->89

그리고 두 번 째 순 서 를 시작 합 니 다. 두 번 째 순서 와 마찬가지 로 이번 에는 10 자리 에 따라 배열 에 대응 하 는 아래 표 시 를 넣 었 습 니 다. 결 과 는 그림 과 같 습 니 다.

0
1
2
3
4
5
6
7
8
9
41
55
61
75
89
42
62
77
78
다시 수집 작업 을 진행 하려 면 다음 순서 41 - > 42 - > 55 - > 61 - > 62 - > 75 - > 77 - > 78 - > 89 정렬 이 완료 되 어야 합 니 다.
자바 코드 는 다음 과 같 습 니 다:

public static void radixSort(Integer[] array, int n) {
     
    LinkedList<Integer> numList = new LinkedList<Integer>(); //  array     linkedList ，    
    for (int i = 0; i < array.length; i++) {
     
        numList.add(array[i]);
    }

    LinkedList<Integer>[] lists = new LinkedList[10]; //    10  。          
    for (int i = 0; i < lists.length; i++) {
     
        lists[i] = new LinkedList<>();
    }

    for (int i = 1; i < Math.pow(10, n); i = i *10) {
       //       ，2     ，3   3 
        Integer item = null;
        while (numList.peekFirst() != null) {
       //                  
            item = numList.removeFirst(); //          ，    
            lists[item/i%10].add(item);
        }


        for (int j = 0; j < lists.length; j++) {
      //       ，      ，    ，       
            numList.addAll(lists[j]);
            lists[j].clear();
        }
    }
    for (int i = 0; i < numList.size(); i++) {
       //          ，      
        array[i] = numList.get(i);
    }
}

복잡 도 분석: 공간 복잡 도: 하나의 배열 을 신 청 했 기 때문에 이 배열 의 크기 는 기수 크기 (r) 이기 때문에 공간 복잡 도 는 O (r) 이다.시간 복잡 도: 전체 기수 정렬 은 d 번 의 정렬 (d 는 데이터 의 최대 자릿수) 을 거 쳐 야 합 니 다. 모든 정렬 은 분배 와 수집 두 과정 을 거 쳐 야 합 니 다. 분배 과정 은 n 개 (정렬 배열 크기) 요 소 를 옮 겨 다 니 고 r (기수) 크기 의 배열 을 수집 해 야 합 니 다.그래서 시간 복잡 도 는 O (d (n + r) 이다.
안정성: 안정.수집 과 분배 과정 에서 두 개의 같은 요소 가 상대 적 으로 교환 되 는 것 은 존재 하지 않 는 다.그래서 안정 적 이 야.닭 (기) 너 는 너무 아름답다.
적용 성: 순서 저장 과 체인 저장 에 적용 할 수 있 습 니 다.단, 원소 의 자릿수 와 상대 적 으로 고정 되 고 각 비트 의 기수 크기 만 고정 된다.자모 도 정렬 할 수 있 는데, 그것 의 기 수 는 26 (26 개의 영문 자모) 이다.
정렬 알고리즘 총화
알고리즘 이름
최 적 시간 복잡 도
평균 시간 복잡 도
최 악의 시간 복잡 도
공간 복잡 도
안정성
적용 성
직접 삽입 정렬
O(n)
O(n2)
O(n2)
O(1)
안정시키다
순차 저장 소 와 체인 저장 소
힐 정렬
O(n1.3)
O(n1.3)
O(n2)
O(1)
불안정
순차 기억 장치
거품 정렬
O(n)
O(n2)
O(n2)
O(1)
안정시키다
순차 저장 소 와 체인 저장 소
빠 른 정렬
O(n*log n)
O(n*log n)
O(n2)
O(n)
불안정
순차 기억 장치
단순 선택 정렬
O(n2)
O(n2)
O(n2)
O(1)
불안정
순차 저장 소 와 체인 저장 소
더미 정렬
O(n*log n)
O(n*log n)
O(n*log n)
O(1)
불안정
순차 기억 장치
정렬
O (n*log n)
O (n*log n)
O (n*log n)
O(n)
안정시키다
순차 기억 장치
기수 정렬
O(d*(n+r))
O(d*(n+r))
O(d*(n+r))
O ( r )
안정시키다
순차 저장 과 체인 저장, 요 소 는 기본 이 필요 합 니 다.