堆排序

package com.vmstar.algorithms.heapsort;

import com.vmstar.algorithms.merge.Node;

import java.util.Random;

/**
 * @author star
 * @Date 2017/2/25.
 * @Description: No Description Yet.
 */
public class HeapSortTest {


  public static void main(String[] args){
    Node[] nodes = new Node[6];
    for(int i = 0; i < 6; i++){
      int data = new Random().nextInt(50);
      nodes[i] = new Node(data);
    }

    for(Node node:nodes){
      System.out.println(node);
    }

    System.out.println("+++++++++++++++++++");

    HeapSortTest.sort(nodes);

    for(Node node:nodes){
      System.out.println(node);
    }
  }


  public static void sort(Comparable[] a){
    int length = a.length - 1;
    for(int i = length/2+1; i >= 0; i--){
      sink(a, i, length);
    }

    System.out.println("==========>");
    for(Comparable node:a){
      System.out.println(node);
    }
    System.out.println("<==========");

    while(length >= 0){
      exch(a, 0, length--);
      sink(a, 0, length);
    }
  }

  private static void sink(Comparable[] a, int k, int n){
    while((2 * k + 1) <= n){
      int l = 2 * k + 1;
      if((l + 1 <= n) && more(a[l + 1], a[l])){
        l++;
      }

      if(more(a[l], a[k])){
        exch(a, k, l);
      }
      k = l;
    }
  }

  private static boolean less(Comparable a, Comparable b){
    return a.compareTo(b) < 0;
  }

  private static boolean more(Comparable a, Comparable b){
    return a.compareTo(b) > 0;
  }


  private static void exch(Comparable[] a, int i, int j){
    Comparable temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

}