快速排序算法的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快速排序
　　　 obj　待排序的數組
　　　 left 數組的下界
　　　 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中選取樞紐元，選取方法為取數組第一個、中間一個、最後一個元素 中中間的一個。將樞紐元置於倒數第二個位置，三個中最大的放在數組最後一個位置，最 小的放在第一個位置
　　　 obj 要選擇樞紐元的數組
　　　 left 數組的下界
　　　 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;
　　　 }
}