Java 데이터 구조 정렬 알고리즘 (1) 트리 선택 정렬

이 글에서는 주로 Java 데이터 구조 정렬 알고리즘의 트리 선택 정렬을 소개합니다. 구체적인 예를 기반으로 Java 트리 선택 정렬의 원리, 구현 기술 및 관련 주의 사항을 분석합니다. 도움이 필요한 친구는 이 문서를 참조할 수 있습니다. 예제에서는 Java 데이터 구조의 트리 선택 정렬 알고리즘을 설명합니다. 참고를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

여기에서는 선택 정렬 중 하나인 트리 선택 정렬에 대해 설명합니다.

간단한 선택 정렬에서 각 비교는 이전 비교를 사용하지 않습니다. 비교 연산의 시간 복잡도는

O(N^2)

입니다. 비교 횟수를 줄이려면 비교 과정에서 크기 관계를 저장해야 합니다. 트리 선택 정렬은 단순 선택 정렬보다 개선되었습니다.

트리 선택 정렬: 토너먼트 Sort)이라고도 알려져 있으며 토너먼트 아이디어를 기반으로 한 선택 정렬 방법입니다. 먼저 n개 레코드의 키워드에 대한 쌍 비교를 수행한 다음 n/2개의 작은 레코드 간의 쌍 비교를 수행하고 가장 작은 레코드가 선택될 때까지 이를 반복합니다.

알고리즘 구현 코드는 다음과 같습니다.

package exp_sort;
public class TreeSelectSort {
 public static int[] TreeSelectionSort(int[] mData) {
  int TreeLong = mData.length * 4;
  int MinValue = -10000;
  int[] tree = new int[TreeLong]; // 树的大小
  int baseSize;
  int i;
  int n = mData.length;
  int max;
  int maxIndex;
  int treeSize;
  baseSize = 1;
  while (baseSize < n) {
   baseSize *= 2;
  }
  treeSize = baseSize * 2 - 1;
  for (i = 0; i < n; i++) {
   tree[treeSize - i] = mData[i];
  }
  for (; i < baseSize; i++) {
   tree[treeSize - i] = MinValue;
  }
  // 构造一棵树
  for (i = treeSize; i > 1; i -= 2) {
   tree[i / 2] = (tree[i] > tree[i - 1] ? tree[i] : tree[i - 1]);
  }
  n -= 1;
  while (n != -1) {
   max = tree[1];
   mData[n--] = max;
   maxIndex = treeSize;
   while (tree[maxIndex] != max) {
    maxIndex--;
   }
   tree[maxIndex] = MinValue;
   while (maxIndex > 1) {
    if (maxIndex % 2 == 0) {
     tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex + 1] ? tree[maxIndex]
       : tree[maxIndex + 1]);
    } else {
     tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex - 1] ? tree[maxIndex]
       : tree[maxIndex - 1]);
    }
    maxIndex /= 2;
   }
  }
  return mData;
 }
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
  TreeSelectionSort(array);
  for (int i = 0; i < array.length; i++) {
   System.out.print(array[i] + " ");
  }
  System.out.println("\n");
 }
}

알고리즘 분석: 트리 선택 정렬에서 가장 작은 키워드를 제외하고 가장 작은 선택된 키워드는 모두 나뭇잎으로 구분됩니다. 노드 간, n 리프 노드를 포함하는 완전한 이진 트리의 깊이는 log2n+1이므로 트리 선택 정렬에서는 더 작은 키워드가 선택될 때마다 log2n 비교가 필요하므로 시간 복잡도는 O(nlog2n)입니다. , 이동 레코드 수가 비교 횟수를 초과하지 않으므로 전체 알고리즘 시간 복잡도는 O(nlog2n)입니다. 단순 선택 정렬 알고리즘과 비교하면 비교 횟수의 크기가 줄어들고 n-1입니다. 중간 비교 결과를 저장하는 추가 저장 공간이 추가됩니다.

보충: 여기에서는 트리 선택 정렬을 위한 향상된 알고리즘, 즉

Heap sort

알고리즘을 소개합니다. 힙 정렬은 많은 공간을 차지하는 트리 선택 정렬 알고리즘의 단점을 보완합니다. 힙 정렬을 사용하는 경우 레코드 크기의 보조 공간이 하나만 필요합니다.

알고리즘의 아이디어는 다음과 같습니다.

정렬할 레코드의 키워드를

array

r[1...n]에 저장하고 r을 완전한 이진 트리의 순차 표현으로 간주합니다. 각 노드는 A 레코드를 나타냅니다. 첫 번째 레코드 r[1]은 이진 트리의 루트로 사용됩니다. 다음 각 레코드 r[2...n]은 레이어별로 순서대로 배열됩니다. 임의의 노드 r[i]의 왼쪽 자식은 r[2*i]이고 오른쪽 자식은 r[2*i+1]입니다.

힙 정의:

각 노드의 키 값은 다음 조건을 충족합니다. r[i].key >= r[2i].key 및 r[i].key >= r[2i+1 ].key (i=1,2,…[i/2])

위 조건을 충족하는 완전 이진 트리를 반대로 큰 루트 힙이라고 합니다. 이 완전 이진 트리에 있는 노드의 키가 자식 및 오른쪽 자식의 키워드에 해당하는 힙을 작은 루트 힙이라고 합니다.

힙 정렬 프로세스에서는 주로 두 가지 문제를 해결해야 합니다. 첫 번째는 힙 정의에 따라 초기 힙을 구축하는 것이고, 두 번째는 가장 큰 요소를 제거한 후 힙을 다시 빌드하여 가장 큰 요소를 얻는 것입니다.

힙 정렬은 힙의 특성을 이용하여 레코드 순서를 정렬하는 것입니다.

1. 주어진 시퀀스에 대한 힙을 생성합니다.

2. 요소 및 마지막 요소)

3. 나머지 요소 재구성 힙을 수행합니다(첫 번째 요소 필터링).
4. 모든 요소가 출력될 때까지 2단계와 3단계를 반복합니다.

참고:

"필터링"은 [n/2]번째 노드에서 시작하여 루트 노드까지 레이어별로 뒤로 이동해야 합니다.

알고리즘 분석:

1. 깊이가 k인 힙의 경우 "필터링"에 필요한 키워드 비교 횟수는 최대 2(k-1)

2입니다. [log2n]+1, 처음에 힙을 구축하는 데 필요한 키워드 비교 횟수는 최대 n* [log2n];

3입니다. 힙을 n-1번 다시 작성하려면 필요한 키워드 비교 횟수는 다음을 초과하지 않습니다. n-1)*2 [log2n];

따라서 최악의 경우 힙 정렬의 시간 복잡도는 O(nlog2n)이 되는데, 이는 힙 정렬의 가장 큰 장점입니다.

【관련 권장 사항】

1.

Java

2.java 데이터 구조 정렬 알고리즘의 자세한 예제 튜토리얼(2) 병합 정렬

3 java 데이터 구조 정렬 알고리즘 선택 정렬

4. java 데이터 구조 정렬 알고리즘 (4) 선택 정렬

위 내용은 Java 데이터 구조 정렬 알고리즘 (1) 트리 선택 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!