快速排序算法的JAVA实现

王朝java/jsp·作者佚名  2006-02-01
窄屏简体版  字體: |||超大  

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;

}

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航