手把手带你认识快速排序（2）——实现

手把手带你认识快速排序（二）——实现

上篇写了下对快速排序的一个简单认识。但是，我个人是比较喜欢代码的，总感觉说的再好，不如看代码爽，下面我就给大家看一下快速排序的代码，我是用的java写的。

public class QuickSort {
	public static void main(String[] args)throws Exception{
		int[] a={5,6,4,1,2,3,7,8,9};
		Sort(a,0,8);	
		for(int i=0; i<a.length; i++){
			System.out.println(a[i]);	
		}		
	}
	
	//利用递归进行排序
	public static void Sort(int[] array, int left, int right) {
		
		if(right<=left)	//如果自写中只有0或1个记录，就不需排序
			return;
		int pivot=SelectPivot(left,right);	//选择轴值
		Swap(array,pivot,right);		//分割前，将轴值换到末端（初端也可以）
		pivot=Partition(array,left,right);	//获取分割后，轴值所在的位置
		Sort(array,left,pivot-1);		//对左子序列进行递归快速排序
		Sort(array,pivot+1,right);	//对右子序列进行递归快速排序
						
	}
	
	//交换数组中的两个元素
	private static void Swap(int[] array, int index1,int index2) {
		int tmp=array[index1];
		array[index1]=array[index2];
		array[index2]=tmp;
		
	}
	
	//选择轴值
	private static int SelectPivot(int left,int right) {
		return (left+right)/2;	//选取中间记录作为轴值，提取出来，方便日后修改
	}
	
	//分割函数，返回分割后轴值所在的位置
	private static int Partition(int[] array, int left, int right) {
		int l=left;
		int r=right;
		int tempRecord=array[r];
		
		while(l != r){	//当l与r相遇时，推出循环
			
			//模拟左指针l的操作，l指针向右移动，越过比轴值小的数，直道找到一个大于轴值额记录
			while(array[l] <=	tempRecord && r>l) 
				l ++;
			
			//在l与r未相遇之前，将比轴值大的数放到右边，如果再次进行交换，那么会增加两条语句，再加上下面的，一共会增加4条语句。这个对于一个为大数组而设计的快速排序来说，这个伤我感觉还是比较大的	
			if(l<r) {
				array[r] = array[l];
				r --;
			}
			
			//模拟右指针r的操作，r指针向左移动，越过比轴值大的数，直道找到一个小于轴值额记录
			while(array[r] >= tempRecord && r>l)
				r--;
			
			//在l与r未相遇之前，将比轴值小的数放到左边
			if(l<r){
				array[l]=array[r];
				l++;
			}	
		} //end while
		
		array[l]=tempRecord;
		return l;
		
	} 
	
}

2楼lfmilaoshi4小时前: 把很多的排序，统一到一个方法，如何n米老师

1楼lidaasky昨天 21:21: 犀利

手把手带你认识快速排序（2）——实现

相关推荐