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!");

              }

       }

       *对数组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);

                     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;

                            }

                     }

                     //将枢纽值与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 right 数组的上界

       */

       private void pivot(comparable[] obj, int left, int right)

       {  int center = (left + right) / 2;

              comparable tmp = null;

              {  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;

       } }