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