복단대학 961 - 데이터 구조 - 제4 장 - 정렬 (1) 정렬 의 기본 개념;정렬 삽입, 힐 정렬
11673 단어 961
글 목록
정렬 의 기본 개념
정렬 은 목록 의 요 소 를 다시 배열 하여 표 의 요 소 를 키워드 에 따라 질서 있 게 하 는 과정 입 니 다.
정렬 알고리즘 은 두 가지 로 나 뉘 는데 안정 적 이 고 불안정 하 며 다음 과 같은 데이터 가 있다 고 가정 합 니 다. 7, 2, 8, 4, 9, 8.이 데이터 에는 8 이 두 개 있 는데, 여 기 는 굵기 로 표시 한다.안정 적 인 정렬 에 있어 정렬 후의 결과 중 두 개의 8 은 위 치 를 바 꾸 지 않 는 다. 즉, 2, 4, 7, 8, 8, 9 이다.그러나 불안정한 정렬 에 대해 정렬 한 후에 두 개의 8 의 순 서 는 '가능 하 다' 는 변화 가 생 겼 다. 예 를 들 어 2, 4, 7, 8, 8, 9 등 이다.
데이터 가 모두 메모리 에 저장 되 었 는 지 여부 에 따라 정렬 을 두 가지 로 나 눌 수 있 습 니 다.
삽입 정렬
정렬 을 삽입 하 는 기본 사상: 정렬 을 기다 리 는 서열 을 두 부분 으로 나 누고 앞 에는 이미 정렬 이 되 어 있 고 뒤 에는 정렬 이 되 어 있 지 않다.정렬 되 지 않 은 시퀀스 중 하 나 를 선택 하여 정렬 된 시퀀스 에 삽입 합 니 다.정렬 되 지 않 은 모든 시퀀스 가 비어 있 을 때 까지.
직접 삽입 정렬
정렬 을 삽입 하 는 사상 에 따라 직접 정렬 알고리즘 을 쉽게 생각 할 수 있다.
질서 [0,... i]
i + 1 (정렬 대기 요소)
i + 2,..., n (무질서 수열)
정렬 사상 을 직접 삽입 하고 첫 번 째 부분 은 질서 있 는 서열 이 며 두 번 째 부분 은 무질서 한 서열 의 첫 번 째 요소 이 고 세 번 째 부분 은 남 은 무질서 한 수열 이다.알고리즘 (작은 것 부터 큰 것 까지 배열) 은 다음 과 같다.
자바 코드 는 다음 과 같 습 니 다:
public static void insertionSort(Comparable[] array) {
if (array == null) return;
for (int i = 1; i < array.length; i++) {
// 1 ,
Comparable temp = array[i];
int j;
// , 0 , temp , 。
for (j = i; j > 0 && temp.compareTo(array[j-1]) < 0; j--) {
array[j] = array[j - 1]; // , j-1 , 。
}
array[j] = temp; // j ,
}
}
복잡 도 분석
적용 성: 이 방식 은 순서 저장 (배열) 과 체인 저장 에 적 용 됩 니 다.무 작위 접근 이 없 기 때문이다.
반절 기 삽입 정렬
직접 삽입 정렬 과 차이 가 많 지 않 습 니 다.직접 정렬 을 삽입 하 는 것 은 비교 하면 서 교환 하 는 것 이 고 반 으로 정렬 을 삽입 하 는 것 은 앞의 질서 있 는 수열 을 반 으로 찾 아 삽입 할 위 치 를 찾 은 다음 에 통일 적 으로 교환 하 는 것 이다.사실 효율 이 떨 어 지 는 것 은 많 지 않다.그러나 반절 삽입 은 체인 메모리 에 적용 되 지 않 는 다.
코드 는 다음 과 같 습 니 다: TODO, 비중 점, 후기 보충
힐 (셸) 정렬
힐 정렬 도 직접 삽입 하 는 특성 (질서 에 가 까 운 서열 시간 복잡 도 O (n) 을 이용 했다.기본 사상 은:
힐 의 정렬 이 이해 하기 어 려 운 점 은 바로 이 그룹 이다. 인접 한 요 소 를 한 그룹 으로 나 누 는 것 이 아니다.서로 떨 어 진 고정 거리의 원 소 를 한 조로 나 누 는 것 이다. 예 를 들 어 아래 표 시 된 0, 3, 6, 9... 의 원 소 를 한 조로 나 누고 해당 하 는 1, 4, 7, 11... 을 한 조로 나 누 는 것 이다.이때 거리 d = 3.전문 적 인 말 은 먼저 정렬 할 시 계 를 L [i, i + d, i + 2d,..., i + kd] 의 '특수' 서브 시트 로 나 누 는 것 이다. 즉, 특정한 '증 량' 과 떨 어 진 기록 을 하나의 서브 시트 로 구성 하고 각 서브 시트 에 대해 직접 정렬 을 한다. 전체 표 의 요소 가 '기본 질서' 가 있 을 때 전체 기록 에 대해 직접 정렬 을 한다.
증분 d 에 대해 서 는 매 라운드 마다 체감 해 야 한다.추천 하 는 방식 은 첫 번 째 n/2, 두 번 째 n/2/2 를 취하 고 매번 2 로 나 누 어 0 까지 하 는 것 이다.그러나 문 제 를 낼 때 서로 다른 d 의 체감 방식 을 제시 하여 매 라운드 의 정렬 결 과 를 구 할 수 있다.
예:
9
6
7
4
1
6
2
9
3
제1 라운드
d=4
1
6
2
4
3
6
7
9
9
제1 라운드
d = 4 의 그룹 번호
1 (1)
6 (2)
2 (3)
4 (4)
3 (1)
6 (2)
7 (3)
9 (4)
9 (1)
이차
d=2
1
4
2
6
3
6
7
9
9
이차
d = 2 의 그룹 번호
1(1)
4(2)
2(1)
6(2)
3(1)
6(2)
7(1)
9(2)
9(1)
제3 차
d= 1
1
2
3
4
6
6
7
9
9
이 예 에서 세 바퀴 를 거 쳐 이 서열 을 질서 있 는 서열 로 배열 했다.그 중에서 그룹 번호 의 괄호 중 같은 대표 가 한 그룹 으로 나 뉘 었 다.시험 에서 따로 조별 상황 을 그 릴 필요 가 없다.여 긴 그냥 이해 하기 편 하 게
자바 로 구현, 코드 는 다음 과 같 습 니 다:
public static void shellSort(Comparable[] array) {
if (array == null) return;
for (int d = array.length / 2; d > 0; d = d / 2) {
// d=n/2, d=n/2/2, , d=0
for (int i = d; i < array.length; i++) {
// i d, i=1
Comparable temp = array[i]; // ,
int j;
for (j = i; j >= d && temp.compareTo(array[j - d]) < 0; j = j - d) {
// -kd ,
array[j] = array[j - d];
}
array[j] = temp;
}
}
}
여기 두 번 째 for 순환 에 주의 하 세 요.힐 정렬 은 여러 그룹 으로 나 뉘 었 지만 실제로 실 행 될 때 첫 번 째 그룹 을 정렬 한 후에 두 번 째 그룹 으로 정렬 하 는 것 이 아니다.1 조 의 첫 번 째 요 소 를 삽입 하여 정렬 한 다음 에 2 조 의 첫 번 째 요 소 를 정렬 한 다음 에 3 조 의 첫 번 째 요 소 를 순서대로 유추 하 는 것 이다.그리고 1 조 의 두 번 째 원소...
복잡 도 분석:
적용 성: 순서 저장 에 만 적 용 됩 니 다.무 작위 접근 특성 을 사용 해 야 하기 때문이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
복단대학 교 961 - 데이터 구조 - 제4 장 - 정렬 (3) 합병 정렬, 기수 정렬;정렬 알고리즘 복잡 도 총화합병 하기 전에 A 배열 은 배열 의 첫 번 째 요 소 를 가리 키 는 i 포인터 가 있 습 니 다.B 배열 은 포인터 j 이 고 첫 번 째 요 소 를 가리킨다.그리고 A [i] 와 B [j] 를 비교 해서 작은 것...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.