Java语言快速排序算法的实现

package com.yql.test;

public class QuickSort {
     //快速排序算法平均运行时间O(NlogN)，最坏的情形性能为O(N*N)
	public void quickSort(String[] strDate, int left, int right) {
		String middle, tempDate;
		int i, j;
		i = left;
		j = right;
		//选取枢纽元为中间的，时间证明这种选取枢纽元得方法 （三数中值分割算法）比较好
		middle = strDate[(i + j) / 2];
		
		do{ 
		    //直到找到左边第一个大于或等于枢纽元的数值时执行右边查询
			while(strDate[i].compareTo(middle)<0&&i<right)
				i++;
			//直到找到右边第一个小于或等于枢纽元的数值执行下面的交换
			while(strDate[j].compareTo(middle)>0&&i>left)
				j--;
			//当ij没有交叉时，交换数组i,j位置的值
			if(i<=j){
				tempDate=strDate[i];
				strDate[i]=strDate[j];
				strDate[j]=tempDate;
				i++;
				j--;
			}
		}while(i<=j);//只要ij没有交错就一直执行
	    //ij交错时，如果i比最右边的小 ，给右边的数值排序
		if(i<right){
		   quickSort(strDate,i,right);	
		}
		//ij交错时，如果j比最左边的大，给左边的数值排序
		if(j>left){
			   quickSort(strDate,left,j);	
			}
	}
	
	public static void main(String[] args) {
		//准备需要排序的数据
		String[] strVoid = new String[] { "11", "66", "22", "0", "55", "22",
				"0", "32" };
		QuickSort sort = new QuickSort();
		//排序 
		sort.quickSort(strVoid, 0, strVoid.length - 1);
		//打印排好了序列的数组
		for(int i=0;i<strVoid.length;i++){
			System.out.println(strVoid[i]+"  ");
		}
	}
}

 

评论

1 楼 jf19880423 2012-08-14  

执行以后发现是 0, 0, 32, 11, 22, 22, 55, 66， 这个排序算法是不是有错误