JAVAソートヒープソート

以下のエディターは、比較ソートとヒープソートに関する古い決まり文句を提供します。編集者はこれがとても良いものだと思ったので、皆さんの参考として今から共有します。エディターをフォローして見てみましょう

ヒープのソートには、バイナリ ツリーの完全な知識が必要です。ソートされるシーケンス {10, 2, 11, 8, 7} については、次の図に示すように、完全な二分木とみなします。

ヒープは、ラージ ルート ヒープとスモール ルート ヒープに分割されます。ラージ ルート ヒープは、各ルート ノードがその子ノードよりも大きいことを意味します (L(i) >= L(2i) && L(i) > = L(2i + 1))、小さなルート ヒープは、各ルート ノードがその子ノードよりも小さいことを意味します (L(i)

この記事では、例として大規模なルート ヒープの構築を使用して説明します。 。

ヒープソートの最初のステップ - 初期ヒープの構築。初期ヒープを構築するにはどうすればよいですか?定義上、キー ポイントは各ルート ノードにあります。ソートされる上記のシーケンスの完全な二分木を観察すると、ノード 2 とノード 10 に注目が必要なノードである子ノードがあることがわかります。

ノード 2 を見つけるには?完全な二分木の性質によれば、それが葉ノード、つまり最後のノードの親ノードであることがわかります。ルート ノードを除くすべてのノードの親ノードの番号は ⌊in / 2⌋ です。 n = 5 とすると、ノード 2 の数は ⌊5 / 2⌋ = ② であることが簡単にわかります。左右の子ノードのサイズと比較して調整します。

最後にルートノード10が残りますが、ノード2の番号は②、②-1=①であることがわかり、ルートノード10の番号が求まります。左右の子ノードのサイズと比較して調整します。

調整が完了すると、「大きなルート ヒープ」が形成されていることがわかります。この例でソートされる列は比較的単純ですが、それを観察するために、より複雑なソートされる列が与えられます。大規模なルート ヒープを構築するプロセス。ソートされるシーケンス {53, 17, 78, 09, 45, 65, 87, 32} の場合、それを完全な二分木として扱います。

同様に、注意を払う必要があるノードを見てみましょう。

最初の例によれば、ノード 09 の番号は ⌊8 / 2⌋ = ④ として、ノード 78 の番号は ④ - 1 = ③... などとして簡単に見つけることができます。つまり、調整する必要があるノードの位置は ⌊n / 2⌋ からルートノード①が終了するまで (⌊n / 2) 減少します。 ⌋ ~ 1)。今すぐ調整を始めてください。

4回目の調整後、ノード53は大きなルートヒープの定義を満たしておらず、その右側の子ノードがそれよりも大きいことが判明しました。さらなる下方修正が必要だ。

すべての上方調整が完了した後に戻って下方調整するのではなく、下方調整が必要かどうかを判断するために上方調整を行うたびに下方調整を行う必要があることに注意してください。このようにして、大きなルート ヒープが確立され、ソートされる列配列の状況が変化しました: {87, 45, 78, 32, 17, 65, 53, 09}。次に、どのように分類するかという問題です。大きなルート ヒープのルート ノードを最後のノードと交換し、依然として大きなルート ヒープを満たすようにバイナリ ツリーを調整します。

ルートノードと最後のノードを呼び出した後、ソート対象の列の最大値が配列{..., 87}の最後の位置に配置されていることがわかります。このとき、最初のソートは です。ノード 87 を除いて、他のノードは大規模なルート ヒープの条件を満たしていないため、残りのノードは大規模なルート ヒープになるように調整する必要があります。ソート処理は提供されなくなりました。Java および Python3 でのコード実装は次のとおりです。

Java

package com.algorithm.sort.heap;

import java.util.Arrays;

/**
 * 堆排序
 * Created by yulinfeng on 6/20/17.
 */
public class Heap {
  
  public static void main(String[] args) {
    int[] nums = {53, 17, 78, 09, 45, 65, 87, 32};
    nums = heapSort(nums);
    System.out.println(Arrays.toString(nums));
  }
  
  /**
   * 堆排序
   * @param nums 待排序数组序列
   * @return 排好序的数组序列
   */
  private static int[] heapSort(int[] nums) {
  
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
      heapAdjust(nums, i, nums.length);
    }
    for (int i = nums.length - 1; i > 0; i--) {
      int temp = nums[i];
      nums[i] = nums[0];
      nums[0] = temp;
      heapAdjust(nums, 0, i);
    }
    return nums;
  }
  
  /**
   * 调整堆
   *
   * @param nums  待排序序列
   * @param parent   待调整根节点
   * @param length 数组序列长度
   */
  private static void heapAdjust(int[] nums, int parent, int length) {
    int temp = nums[parent];
    int childIndex = 2 * parent + 1;  //完全二叉树节点i从编号1开始的左子节点位置在2i，此处数组下标从0开始，即左子节点所在数组索引位置为：2i + 1
    while (childIndex < length) {
      if (childIndex + 1 < length && nums[childIndex] < nums[childIndex + 1]) {
        childIndex++;  //节点有右子节点，且右子节点大于左子节点，则选取右子节点
      }
      if (temp > nums[childIndex]) {
        break; //如果选中节点大于其子节点，直接返回
      }
      nums[parent] = nums[childIndex];
      parent = childIndex;
      childIndex = 2 * parent + 1;  //继续向下调整
    }
    nums[parent] = temp;
  }
}

Python3

#堆排序
def heap_sort(nums):

  for i in range(int(len(nums) / 2 - 1), -1, -1):
    heap_adjust(nums, i, len(nums))
  
  for i in range(len(nums) - 1, -1, -1):
    temp = nums[i]
    nums[i] = nums[0]
    nums[0] = temp
    heap_adjust(nums, 0, i)
  
  return nums

#调整堆
def heap_adjust(nums, parent, length):
  
  temp = nums[parent]
  childIndex = 2 * parent + 1
  while childIndex < length:
    if childIndex + 1 < length and nums[childIndex] < nums[childIndex + 1]:
      childIndex += 1
    if temp > nums[childIndex]:
      break
    nums[parent] = nums[childIndex]
    parent = childIndex
    childIndex = 2 * parent + 1
  
  nums[parent] = temp
    
nums = [53, 17, 78, 09, 45, 65, 87, 32]
nums = heap_sort(nums)
print(nums)

上記の決まり文句の比較ソートとヒープソートは、すべて編集者が共有した内容であり、参考になれば幸いです。皆さんもスクリプトハウスを応援していただければ幸いです。

以上がJAVAソートヒープソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。