1.引子
快速排序算法可能是最优秀的排序算法了,此算法是1960年C.A.Hoare发明出来的,它被列为20世纪十大算法之一。快速排序也属于广义上的冒泡排序,这是简单冒泡排序法的优化升级。两者都是通过比较大小、交换元素来排序的,不过它增大了元素的比较和移动的跨度。这使得快速排序避免了一些额外的计算,进而实现更高的排序效率。
2.基本思路
从数组中取出一个元素作为基准值, 将较大的记录直接移动到基准值的后面,较小的元素移动到基准值的前面, 通过一趟排序将待排序的数组分割成了独立的两部分,再然后递归地对这两个组分别做排序。
组划分操作会事先选取一个随机元素作为基准值,并将交换是最前边。然后再比较其他元素,把小于基准值的元素向前交换到last索引位置,大于基准值的元素向后交换到i索引位置。从for循环开始的地方,从1至last的元素小于基准值,从last+1至i-1的元素大于等于基准值,而i至n-1的元素还未检查。接下来会递归检查i至n-1的元素,在所有元素划分完毕后,就交换索引0和last的元素,把基准值放回了原来的位置,这样就完成了所有元素的排序工作
- 基准元素交换开始时
- 检查交换元素过程中
- 检查交换元素最后一步
3.实现代码
1)比较器接口
//泛型比较器接口,确定两元素的前后关系
public interface Cmp<T>
{
/*
* 如果x应该排在前,返回值为1;
* 如果x,y两者相等,返回值为0;
* 如果y应该排在前,返回值为-1.
*/
int copmare(T obj1, T obj2);
}
2)数组元素的比较器实现类
//实现比较器接口
final class IntegerCmp implements Cmp<Integer>
{
@Override
public int copmare(Integer x, Integer y)
{
return x.compareTo(y);
}
}
3) 快速排序工具类
import java.util.Random;
public final class SortDemo<T>
{
private static Random rd = new Random();
//array为待排序的数组名,left/right为需要排序的索引范围,cmp为数组元素的比较器对象
public static <T> void sort(T[] array, int left, int right, Cmp<T> cmp)
{
//left等于right时表明完成了所有的排序,不需要再递归排序了,方法结束
if (left >= right)
return;
int rdIndex=rand(left,right);
//将数组最左边的元素与一随机索引rdIndex对应的元素互换,设置基准值
swap(array,left, rdIndex);
int last = left;
//分隔成两部分
for (int i = left + 1; i <= right; i++)
{
if (cmp.copmare(array[i], array[left]) < 0)
{
swap(array, ++last, i);
}
}
//恢复原来的基准值
swap(array, left, last);
//对左侧部分递归排序
sort(array, left, last - 1, cmp);
//对右侧部分递归排序
sort(array, last + 1, right, cmp);
}
public static <T> void sort(T[] array, Cmp<T> cmp)
{
sort(array, 0, array.length - 1, cmp);
}
//产生一个在left至right之间的一个随机数(不包括边界left、right)
private static int rand(int left, int right)
{
return left + Math.abs(rd.nextInt() % (right - left + 1));
}
//互换索引位置i 、j的元素
private static <T> void swap(T[] array, int i, int j)
{
T temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
4.测试结果
public static void main(String[] args)
{
Integer[] nums = new Integer[10000000];
Cmp<Integer> cmp = new IntegerCmp();
for (int endIndex = nums.length - 1, i = endIndex; i >= 0; i--)
{
nums[i] = endIndex - i;
}
Integer[] partNums = new Integer[50];
System.arraycopy(nums, 1992, partNums, 0, partNums.length);
System.out.println(Arrays.toString(partNums));
long startTime = System.currentTimeMillis();
SortDemo.sort(nums, cmp);
long endTime = System.currentTimeMillis();
System.arraycopy(nums, 100009, partNums, 0, partNums.length);
System.out.println(Arrays.toString(partNums));
System.out.println("对10000000个数字排序用时" + (endTime - startTime) + "毫秒");
}
- 控制台输出