JAvaデータ構造のヒープソート(HeapSort)の詳細と例

1ヒープソート
ヒープは重要なデータ構造であり、大きなヒープと小さなヒープに分けられ、完全二叉木である.底層が配列でデータを格納する場合、ある要素がシーケンス番号i(Java配列は0からiは0からn-1)であると仮定し、左サブツリーがある場合、左サブツリーの位置は2 i+1、右サブツリーがある場合、右サブツリーの位置は2 i+2、親ノードがある場合、親ノードの位置は(n-1)である/2整頓する.最も大きい任意のサブツリーのルートノードは任意のサブノードより小さくなく、最小のスタックのルートノードは任意のサブノードより大きくありません.
スタックソートとは、スタックというデータ構造の性質を利用して配列をソートすることであり、配列の非降順ソートでは、大根スタックが使用される必要がある.大根スタックの性質から分かるように、最大の値は必ずスタックトップにあるからである.スタックソートは,時間的複雑さがO(nlogn)である不安定なソートアルゴリズムである.
2アルゴリズム思想
(1)最大スタックの構築;(2)トップを選択し、0番目の位置要素と交換する.(3)ステップ(2)の交換によって最も大きな性質、すなわち0番目の位置の要素が最大要素ではなくなった場合、maxHeap調整スタック(沈降法)を呼び出し、実際の状況に応じてステップ(2)を繰り返す必要がある.
スタックソートで最も重要なアルゴリズムはmaxHeapであり、この関数は1つの要素の2つのサブノードが最も大きな性質(すなわち左、右のサブツリーが最大スタック)を満たしていると仮定し、ルート要素だけが最大スタックの性質に違反する可能性があると仮定し、その要素と左右のサブノードの最大要素を探し出し、もしこの要素がすでに最大であれば、木全体が最大スタックであり、プログラムが終了し、そうでなければ、ルート要素と最大要素の位置を交換し、maxHeapを呼び出して最大要素があるサブツリーを構築し続けます.
3 Javaコード

public class HeapSort {
  public static void main(String[] args) {
    int[] arr = {3, 2, 1, 0, -1, -2, -3};
    System.out.println("Before heap:");
    printArray(arr);
    heapSort(arr);
    System.out.println("After heap sort:");
    printArray(arr);
  }

  public static void heapSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
      return;
    }
    buildMaxHeap(arr); //     
    for (int i = arr.length - 1; i >= 1; i--) {
      exchangeElements(arr, 0, i); //      0    
      maxHeap(arr, i, 0); //       ，         ，      
    }
  }

  private static void buildMaxHeap(int[] arr) { //     
    if (arr == null || arr.length <= 1) {
      return;
    }
    int half = arr.length / 2;
    for (int i = half; i >= 0; i--) {
      maxHeap(arr, arr.length, i);
    }
  }

  private static void maxHeap(int[] arr, int heapSize, int index) {
    int left = index * 2 + 1; //       
    int right = index * 2 + 2; //       
    int largest = index; //       
    if (left < heapSize && arr[left] > arr[index]) {
      largest = left;
    }
    if (right < heapSize && arr[right] > arr[largest]) {
      largest = right;
    }
    if (index != largest) { //            
      exchangeElements(arr, index, largest);
      maxHeap(arr, heapSize, largest);
    }
  }

  public static void printArray(int[] arr) { //    
    System.out.print("{");
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i]);
      if (i < arr.length - 1) {
        System.out.print(", ");
      }
    }
    System.out.println("}");
  }

  public static void exchangeElements(int[] arr, int index1, int index2) { //    
    int temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
  }
}

読書に感謝して、みんなを助けることができることを望んで、みんなの当駅に対する支持に感謝します!