JAVA排序算法实现代码-堆(Heap)排序

xpjjy

/**
* JAVA排序算法实现代码-堆(Heap)排序。
*
* @author 老紫竹 JAVA世纪网(java2000.net)
*
*/
public class Test {
  public static int[] Heap = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 }; // 预设数据数组
  public static void main(String args[]) {
    int i; // 循环计数变量
    int Index = Heap.length; // 数据索引变量
    System.out.print("排序前: ");
    for (i = 1; i  Index - 1; i++)
      System.out.printf("%3s", Heap);
    System.out.println("");
    HeapSort(Index - 2); // 堆排序
    System.out.print("排序后: ");
    for (i = 1; i  Index - 1; i++)
      System.out.printf("%3s", Heap);
    System.out.println("");
  }
  /**
   * 建立堆
   */
  public static void CreateHeap(int Root, int Index) {
    int i, j; // 循环计数变量
    int Temp; // 暂存变量
    int Finish; // 判断堆是否建立完成
    j = 2 * Root; // 子节点的Index
    Temp = Heap[Root]; // 暂存Heap的Root 值
    Finish = 0; // 预设堆建立尚未完成
    while (j = Index && Finish == 0) {
      if (j  Index) // 找最大的子节点
        if (Heap[j]  Heap[j + 1])
          j++;
      if (Temp >= Heap[j])
        Finish = 1; // 堆建立完成
      else {
        Heap[j / 2] = Heap[j]; // 父节点 = 目前节点
        j = 2 * j;
      }
    }
    Heap[j / 2] = Temp; // 父节点 = Root值
  }
  public static void HeapSort(int Index) {
    int i, j, Temp;
    // 将二叉树转成Heap
    for (i = (Index / 2); i >= 1; i--)
      CreateHeap(i, Index);
    // 开始进行堆排序
    for (i = Index - 1; i >= 1; i--) {
      Temp = Heap[i + 1]; // Heap的Root值和最后一个值交换
      Heap[i + 1] = Heap[1];
      Heap[1] = Temp;
      CreateHeap(1, i); // 对其余数值重建堆
      System.out.print("排序中: ");
      for (j = 1; j = Index; j++)
        System.out.printf("%3s",Heap[j]);
      System.out.println("");
    }
  }
}

运行结果
排序前: 32 1 9 5 7 12 0 4
排序中: 12 7 9 5 1 4 0 32
排序中: 9 7 4 5 1 0 12 32
排序中: 7 5 4 0 1 9 12 32
排序中: 5 1 4 0 7 9 12 32
排序中: 4 1 0 5 7 9 12 32
排序中: 1 0 4 5 7 9 12 32
排序中: 0 1 4 5 7 9 12 32
排序后: 0 1 4 5 7 9 12 32


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/76697/showart_1659343.html