快速排序算法的JAVA实现

package Utils.Sort;  
  
/** 
 
*快速排序，要求待排序的数组必须实现Comparable接口 
 
*/  
  
public class QuickSort implements SortStrategy  
  
{    private static final int CUTOFF = 3;             //当元素数大于此值时采用快速排序  
  
       /** 
 
       *利用快速排序算法对数组obj进行排序，要求待排序的数组必须实现了Comparable接口 
 
       */  
  
       public void sort(Comparable[] obj)  
  
       {   if (obj == null)  
  
              {  throw new NullPointerException("The argument can not be null!");  
  
              }  
  
              quickSort(obj, 0, obj.length - 1);  
  
       }  
  
       /** 
 
       *对数组obj快速排序 
 
       *@param obj　待排序的数组 
 
       *@param left 数组的下界 
 
       *@param right 数组的上界 
 
       */  
  
       private void quickSort(Comparable[] obj, int left, int right)  
  
       {    if (left + CUTOFF > right)  
  
              {     SortStrategy ss = new ChooseSort();  
  
                     ss.sort(obj);  
  
              }  else  
  
              {   //找出枢轴点，并将它放在数组最后面的位置  
  
                     pivot(obj, left, right);  
  
                     int i = left, j = right - 1;  
  
                     Comparable tmp = null;  
  
                     while (true)  
  
                     {    //将i, j分别移到大于/小于枢纽值的位置  
  
                            //因为数组的第一个和倒数第二个元素分别小于和大于枢纽元，所以不会发生数组越界  
  
                            while (obj[++i].compareTo(obj[right - 1]) < 0)    {}  
  
                            while (obj[--j].compareTo(obj[right - 1]) > 0)      {}  
  
                           //交换  
  
                            if (i < j)  
  
                            {  tmp = obj[i];  
  
                                   obj[i] = obj[j];  
  
                                   obj[j] = tmp;  
  
                            }  
  
                            else    break;  
  
                     }  
  
                     //将枢纽值与i指向的值交换  
  
                     tmp = obj[i];  
  
                     obj[i] = obj[right - 1];  
  
                     obj[right - 1] = tmp;  
  
                     //对枢纽值左侧和右侧数组继续进行快速排序  
  
                     quickSort(obj, left, i - 1);  
  
                     quickSort(obj, i + 1, right); }  
  
       }  
  
       /** 
 
       *在数组obj中选取枢纽元，选取方法为取数组第一个、中间一个、最后一个元素中中间的一个。将枢纽元置于倒数第二个位置，三个中最大的放在数组最后一个位置，最小的放在第一个位置 
 
       *@param obj 要选择枢纽元的数组 
 
       *@param left 数组的下界 
 
       *@param right 数组的上界 
 
       */  
  
       private void pivot(Comparable[] obj, int left, int right)  
  
       {  int center = (left + right) / 2;  
  
              Comparable tmp = null;  
  
              if (obj[left].compareTo(obj[center]) > 0)  
  
              {  tmp = obj[left];  
  
                     obj[left] = obj[center];  
  
                     obj[center] = tmp;  
  
              }  
  
              if (obj[left].compareTo(obj[right]) > 0)  
  
              {  tmp = obj[left];  
  
                     obj[left] = obj[right];  
  
                     obj[right] = tmp;  
  
              }  
  
              if (obj[center].compareTo(obj[right]) > 0)  
  
              { tmp = obj[center];  
  
                     obj[center] = obj[right];  
  
                     obj[center] = tmp;  
  
              }  
  
              //将枢纽元置于数组的倒数第二个  
  
                tmp = obj[center];  
  
              obj[center] = obj[right - 1];  
  
              obj[right - 1] = tmp;  
  
       } }