首页 > 程序开发 > 软件开发 > Java > 正文
快速排序的Java实现
2017-07-17 09:55:13       个评论    来源:Youda的博客  
收藏    我要投稿

快速排序的Java实现

原理:

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

/**
 * 快速排序
 * @author Youda
 *
 */
public class Quick {
	
	
	public static void sort(Comparable[] s,int lo, int hi){
		
		if(lo >= hi){
			return;
		}
		
		int j = partition(s,lo,hi); //拆分
		sort(s,lo,j-1); //排序左半部分
		sort(s,j+1,hi); //排序右半部分
		
	}
	
	
	/**
	 * 拆分,左半部分小于v ,右半部分大于v v = s[lo];
	 * @param s
	 * @param lo
	 * @param hi
	 * @return
	 */
	public static int partition(Comparable[] s, int lo, int hi){
		int i = lo;
		int j = hi +1;
		Comparable v = s[lo];
		
		while(true){
			while(less(s[++i],v)){
				if(i == hi){
					break;
				}
			}
			
			while(less(v,s[--j])){
				if(j == lo){
					break;
				}
			}
			
			if(i >= j){
				break;
			}
			exchange(s, i, j);
			
		}
		exchange(s, lo, j);
		return j;
	}
	
	
	//比较x是否小于y
		public static boolean less(Comparable x, Comparable y){
			return x.compareTo(y)<0;
		}
		
		//交换 x,y
		public static void exchange(Comparable[] src,int x,int y){
			Comparable z = src[x]; src[x] = src[y]; src[y] = z;
		}
		
		
		
		public static void main(String[] args) {
			
			//测试数据
			String[] src = {"a","x","z","i","y","o","l","q","b","d","z","s","c"};
			Integer[] src1 = {100,99,70,98,99,101,3,6,676,45,25,77,80,1,0,46,28,11111,56666,22,6,8,29};
			
			System.out.println("===========原数组==========");
			for(String str:src){
				System.out.print(str+",");
			}
			
			sort(src, 0, src.length-1);//排序
			
			System.out.println();
			System.out.println("==========排序后==========");
			for(String str:src){
				System.out.print(str+",");
			}
			
			
			
			System.out.println();
			System.out.println("==========原数组=========");
			for(int i=0;i<src1.length;i++){ system.out.print(src1[i]+",");="" }="" sort(src1,="" 0,="" src1.length-1);="" system.out.println();="" system.out.println("="=========排序后==========&quot;);" for(int="" i="0;i

排序结果:

\

点击复制链接 与好友分享!回本站首页
上一篇:如何优化JAVA代码及提高执行效率
下一篇:最后一页
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站