快速排序

package com.vmstar.algorithms.quick;

import com.vmstar.algorithms.merge.Node;

import java.util.Random;

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

  public static void sort(Comparable[] a){
    sort(a, 0, a.length - 1);
  }

  private static void sort(Comparable[] a, int lo, int hi){

    if(hi <= lo){
      return;
    }

    int partition = partition(a, lo, hi);
    sort(a, lo, partition - 1);
    sort(a, partition + 1, hi);
  }

  private static int partition(Comparable[] a, int lo, int hi){
    int i = lo;
    int j = hi + 1;

    Comparable v = a[lo];

    while (true){
      while (less(a[++i], v)){
        if(i == hi){
          break;
        }
      }

      while (less(v, a[--j])){
        if(j == lo){
          break;
        }
      }

      if(i >= j){
        break;
      }

      exch(a, i, j);
    }

    exch(a, lo, j);
    return j;
  }

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

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

  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("+++++++++++++++++++");

    Quick.sort(nodes);

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