상위 10 대 자바 알고리즘

빠른 정렬은 Tony Hall 이 개발한 정렬 알고리즘입니다. 평균적으로 n 개 항목을 정렬하려면 n 개 (n log n) 를 비교해야 합니다. 최악의 경우, ο (N2) 비교가 필요하지만, 이런 경우는 흔하지 않다. 실제로 빠른 정렬은 대부분의 아키텍처에서 내부 루프를 효율적으로 구현할 수 있기 때문에 일반적으로 다른 NLOGN 알고리즘보다 훨씬 빠릅니다.

빠른 정렬은 분할 전략을 사용하여 목록을 두 개의 하위 목록으로 나눕니다.

알고리즘 단계:

1 시퀀스에서' pivot' 이라는 요소를 선택합니다.

2 시퀀스 순서를 재정리합니다. 기준 값보다 작은 요소는 모두 기준 앞에 배치되고 기준 값보다 큰 요소는 모두 기준 뒤에 배치됩니다 (같은 숫자는 양쪽에 있을 수 있음). 이 구역을 종료한 후 기준은 시리즈 중간에 있습니다. 이를 조닝 (zoning) 작업이라고 합니다.

3. 참조 값보다 작은 요소 하위 시리즈와 참조 값보다 큰 요소 하위 시리즈를 재귀적으로 정렬합니다.

재귀의 하한선은 시퀀스의 크기가 0 또는 1 이라는 것입니다. 즉, 이미 영원히 정렬되어 있음을 의미합니다. 항상 재귀적이지만 이 알고리즘은 항상 종료됩니다. 각 반복에서 최소한 하나의 요소가 마지막 위치에 배치되기 때문입니다.

알고리즘 2: 힙 정렬 알고리즘

Heapsort 는 힙의 데이터 구조를 이용하여 설계된 정렬 알고리즘입니다. Heap 는 heap 의 특성을 만족하는 거의 완전한 이진 트리 구조입니다. 즉, 하위 노드의 키 값 또는 인덱스는 항상 상위 노드보다 작거나 큽니다.

힙 정렬의 평균 시간 복잡성은 ο (NLOGN) 입니다.

알고리즘 단계:

힙 h 만들기 [0 .. n-1]

교환 힙의 머리 (최대값) 와 꼬리.

3. 힙 크기를 1 으로 줄이고 shift_down(0) 을 호출하여 새 배열의 맨 위 데이터를 적절한 위치로 조정합니다.

4. 힙 크기가 1 이 될 때까지 2 단계를 반복합니다.

알고리즘 3: 병합 정렬

병합 정렬 (대만 주 번역: Merge sort) 은 병합 연산에 기반한 효과적인 정렬 알고리즘입니다. 이 알고리즘은 분할 통치의 매우 전형적인 응용이다.

알고리즘 단계:

1. 병합된 시퀀스를 저장할 두 개의 정렬 시퀀스의 합인 공간을 요청합니다.

2. 두 개의 포인터를 설정합니다. 초기 위치는 각각 두 정렬 순서의 시작 위치입니다.

3. 두 포인터가 가리키는 요소를 비교하고 비교적 작은 요소를 선택하여 병합 공간에 놓고 포인터를 다음 위치로 이동합니다.

4. 포인터가 시퀀스의 끝에 도달할 때까지 단계 3 을 반복합니다.

다른 시퀀스의 나머지 모든 요소를 넣으십시오.