Java 快速排序实现

duduli 贡献于2012-07-18

作者 duduli  创建于2008-12-13 06:06:00   修改者User  修改于2010-05-28 08:13:00字数2065

文档摘要:快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。
关键词:

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 步骤为: 从数列中挑出一个元素,称为 "基准"(pivot), 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。 递回的最底部情形, 是数列的大小是零或一,也就是永远都已经被排序好了。 虽然一直递回下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。 package com.bbs; import java.util.Comparator; import java.util.Random; /** * 快速排序使用分治法(Divide and conquer)策略 * 来把一个序列(list) * 分为两个子序列(sub-lists)。 步骤为: 1.从数列中挑出一个元素,称为 "基准"(pivot), 2.重新排序数列, 所有元素比基准值小的摆放在基准前面, 所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。 在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。 3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。 * @author google */ public class QuickSort { public static void main(String[] args) { int[] intt={5,7,9,3,14}; qsort(intt,0,intt.length-1); for (Integer i:intt) { System.out.println(i); } } public static final Random RND=new Random(); /** * 交换指定元素 * @param ary * @param i * @param j */ public static void swap(int[] ary,int i,int j){ int tmp=ary[i]; ary[i]=ary[j]; ary[j]=tmp; } /** * 获取枢纽元素 * @param ary * @param begin * @param end * @param cmp * @return */ private static int partition(int[] ary,int begin,int end){ //随即定位枢纽的位置 int index=begin+RND.nextInt(end-begin+1); // int index=0; //获取枢纽的值 int pivot=ary[index]; //获取枢纽后, 将其置放到数组的最后一个位置 swap(ary,index,end); //之后循环数组, 与曲扭进行比较, 相当于重新排数组 for(int i=index=begin;ibegin){ //找到枢纽 int index=partition(ary, begin, end); qsort(ary, begin, index-1); qsort(ary, index+1, end); } } public static void sort(int[] ary){ qsort(ary, 0,ary.length-1); } } 下面,我以一个上述main方法中的调用为例,来把每一步算法执行过程图解一下。 当然,这个算法最核心的部分就是查找枢纽的方法。 也就是 /** * 获取枢纽元素 * @param ary * @param begin * @param end * @param cmp * @return */ private static int partition(int[] ary,int begin,int end){ //随即定位枢纽的位置 int index=begin+RND.nextInt(end-begin+1); // int index=0; //获取枢纽的值 int pivot=ary[index]; //获取枢纽后, 将其置放到数组的最后一个位置 swap(ary,index,end); //之后循环数组, 与曲扭进行比较, 相当于重新排数组 for(int i=index=begin;i

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 1 人已下载

下载文档