Java算法之堆排序代码示例

堆是一种特殊的完全二叉树，其特点是所有父节点都比子节点要小，或者所有父节点都比字节点要大。前一种称为最小堆，后一种称为最大堆。

比如下面这两个：

 那么这个特性有什么作用？既然题目是堆排序，那么肯定能用来排序。想要用堆排序首先要创建一个堆，如果对4 3 6 2 7 1 5这七个数字做从小到大排序，需要用这七个数创建一个最大堆，来看代码：

public class HeapSort {  private int[] numbers;  private int length;  public HeapSort(int[] numbers) {    this.numbers = numbers;    this.length = numbers.length;  }    public void adjust(int nodeId) {    int swapid;    int flag = 0; //是否需要继续向下调整    while(nodeId * 2 <= this.length && flag == 0) {      //首先判断它和左子节点的关系, 并用swapId记录值较小的节点编号(最大堆是记录较大的)      int index = nodeId - 1; //节点对应数组中数字的索引      int leftChild = nodeId * 2 - 1; //左子节点对应数组中数字的索引      int rightChild = nodeId * 2; //右子节点对应数组中数字的索引      if(numbers[index] < numbers[leftChild]) {        swapId = nodeId * 2;      } else {        swapId = nodeId;      }      //如果有右子节点, 再与右子节点比较      if(nodeId * 2 + 1 <= this.length) {        if(numbers[swapId - 1] < numbers[rightChild])          swapId = nodeId * 2 + 1;      }      //如果最小的节点编号不是自己, 说明子节点中有比父节点更小的      if(swapId != nodeId) {        swap(swapId, nodeId);        nodeId = swapId;      } else {        flag = 1;      }    }  }    public void swap(int nodeId1, int nodeId2) {    int t = numbers[nodeId1 - 1];    numbers[nodeId1 - 1] = numbers[nodeId2 - 1];    numbers[nodeId2 - 1] = t;  }    public void createMaxHeap() {    //从最后一个非叶节点到第一个节点依次向上调整    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();  }}