当前页面位置: » 丰搜网 » 文档中心 » 详细内容
快速排序算法的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;
} }
