快捷導(dǎo)航

Java算法之堆排序代碼示例

更新時(shí)間：2017年11月07日 11:11:52 作者：分享是最好的記憶

這篇文章主要介紹了Java算法之堆排序代碼示例，具有一定參考價(jià)值，需要的朋友可以了解下。

堆是一種特殊的完全二叉樹(shù)，其特點(diǎn)是所有父節(jié)點(diǎn)都比子節(jié)點(diǎn)要小，或者所有父節(jié)點(diǎn)都比字節(jié)點(diǎn)要大。前一種稱(chēng)為最小堆，后一種稱(chēng)為最大堆。

比如下面這兩個(gè)：

那么這個(gè)特性有什么作用？既然題目是堆排序，那么肯定能用來(lái)排序。想要用堆排序首先要?jiǎng)?chuàng)建一個(gè)堆，如果對(duì)4 3 6 2 7 1 5這七個(gè)數(shù)字做從小到大排序，需要用這七個(gè)數(shù)創(chuàng)建一個(gè)最大堆，來(lái)看代碼：

public class HeapSort {
  private int[] numbers;
  private int length;
  public HeapSort(int[] numbers) {
    this.numbers = numbers;
    this.length = numbers.length;
  }
  /**
   * 調(diào)整二叉樹(shù)
   * 如果父節(jié)點(diǎn)編號(hào)為x, 那么左子節(jié)點(diǎn)的編號(hào)是2x, 右子節(jié)點(diǎn)的編號(hào)是2x+1
   * 節(jié)點(diǎn)編號(hào)從1開(kāi)始, 對(duì)應(yīng)數(shù)組中的索引是編號(hào)-1
   * @param nodeId 節(jié)點(diǎn)編號(hào), 從1開(kāi)始
   */
  public void adjust(int nodeId) {
    int swapId;
    int flag = 0; //是否需要繼續(xù)向下調(diào)整
    while(nodeId * 2 <= this.length && flag == 0) {
      //首先判斷它和左子節(jié)點(diǎn)的關(guān)系, 并用swapId記錄值較小的節(jié)點(diǎn)編號(hào)(最大堆是記錄較大的)
      int index = nodeId - 1; //節(jié)點(diǎn)對(duì)應(yīng)數(shù)組中數(shù)字的索引
      int leftChild = nodeId * 2 - 1; //左子節(jié)點(diǎn)對(duì)應(yīng)數(shù)組中數(shù)字的索引
      int rightChild = nodeId * 2; //右子節(jié)點(diǎn)對(duì)應(yīng)數(shù)組中數(shù)字的索引
      if(numbers[index] < numbers[leftChild]) {
        swapId = nodeId * 2;
      } else {
        swapId = nodeId;
      }
      //如果有右子節(jié)點(diǎn), 再與右子節(jié)點(diǎn)比較
      if(nodeId * 2 + 1 <= this.length) {
        if(numbers[swapId - 1] < numbers[rightChild])
          swapId = nodeId * 2 + 1;
      }
      //如果最小的節(jié)點(diǎn)編號(hào)不是自己, 說(shuō)明子節(jié)點(diǎn)中有比父節(jié)點(diǎn)更小的
      if(swapId != nodeId) {
        swap(swapId, nodeId);
        nodeId = swapId;
      } else {
        flag = 1;
      }
    }
  }
  /**
   * 交換兩個(gè)節(jié)點(diǎn)的值
   * @param nodeId1
   * @param nodeId2
   */
  public void swap(int nodeId1, int nodeId2) {
    int t = numbers[nodeId1 - 1];
    numbers[nodeId1 - 1] = numbers[nodeId2 - 1];
    numbers[nodeId2 - 1] = t;
  }
  /**
   * 創(chuàng)建最大堆
   */
  public void createMaxHeap() {
    //從最后一個(gè)非葉節(jié)點(diǎn)到第一個(gè)節(jié)點(diǎn)依次向上調(diào)整
    for(int i = this.length / 2; i >= 1; i--) {
      adjust(i);
    }
  }
  public static void main(String[] args) {
    int[] numbers = new int[] { 4, 3, 6, 2, 7, 1, 5 };
    for(int x = 0; x < numbers.length; x++) {
      System.out.print(numbers[x] + " ");
    }
    System.out.println();
    HeapSort heap = new HeapSort(numbers);
    heap.createMaxHeap();
  }
}

對(duì)本例中的數(shù)列，從this.length / 2到1，共執(zhí)行了三輪循環(huán)。

第一輪：

第二輪：

第三輪：

調(diào)整完成后，當(dāng)前的二叉樹(shù)已經(jīng)符合最大堆的特性，可以用來(lái)從小到大排序。堆排序的原理是，交換堆頂和最后一個(gè)節(jié)點(diǎn)的數(shù)字，即把最大的數(shù)字放到數(shù)組最后，然后對(duì)除了最大數(shù)的前n-1個(gè)數(shù)從新執(zhí)行調(diào)整過(guò)程，使其符合最大堆特性。重復(fù)以上過(guò)程直到堆中只剩下一個(gè)數(shù)字。

public void sort() {
  while(this.length > 1) {
    swap(1, this.length);
    this.length--;
    adjust(1);
  }
  for(int x = 0; x < numbers.length; x++) {
    System.out.print(numbers[x] + " ");
  }
}

堆排序的時(shí)間復(fù)雜度和快速排序的平均時(shí)間復(fù)雜度一樣，是O(nlogn)。

總結(jié)

以上就是本文關(guān)于Java算法之堆排序代碼示例的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站：java實(shí)現(xiàn)的各種排序算法代碼示例、Java遺傳算法之沖出迷宮等，有什么問(wèn)題可以隨時(shí)留言，小編會(huì)及時(shí)回復(fù)大家的。感謝朋友們對(duì)本站的支持！

您可能感興趣的文章: