快速排序法_JAVA_编程开发_程序员俱乐部

快速排序法：

已数组a[11]为例：
16，9，3，49，8，7，34，10，12，30
quickSort（a[],start,end）
第一步，以a[0]为关键数据key，i为数组开始下标，j为数组结束下标，
key=16 ，i = 0 ，j = 10；

第二步从最后开始，即a[j]开始，j--，向左侧比较，查找第一个比key小的数据，然后将a[0]与a[j]调换
12，9，3，49，8，7，34，10，16，30
key = 16 ，i = 0 ，j = 9；

第三步，从左侧开始比较，j++，查找第一个比key大的数据，并交换a[i]与a[j]位置
12，9，3，16，8，7，34，10，49，30
key = 16 ，i = 3 ，j =9；

第四步，跳至第二步，直至i=j；
（从右侧比较）
12，9，3，10，8，7，34，16，49，30
key = 16 ，i = 3 ，j =8；
（从左侧比较）
12，9，3，10，8，7，16，34，49，30
key = 16 ，i = 6 ，j =8；
（从右侧比较）
j=6=i；跳出循环
此时可以得到这样一个数据，在关键数据key左边的数据都比key小，而右边都比key大；

第五步，递归调用，分别对数据的前后两部分数据进行排序，quickSort（a[],start,i-1）;quickSort（a[],j+1,end）;

代码：

class="java">
package com.sort;

public class QuickSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[]= {16,9,3,49,8,7,34,10,12,30};
		System.out.println("原始数据");
		show(a);
		System.out.println("正在排列");
		quickSort(a,0,a.length-1);
		System.out.println("排列后数据");
		show(a);
	}

	public static void quickSort(int a[],int start,int end){
		int key = a[start];
		int i= start;
		int j= end;
		while(i<j){
			while(i<j && a[j]>=key){
				j--;
			}
			if(true){
				int temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
			//System.out.println("从右侧：");
			//show(a);
			while(i<j && a[i]<=key){
				i++;
			}
			if(true){
				int temp=a[j];
				a[j]=a[i];
				a[i]=temp;
			}			//System.out.println("从左侧：");
			//show(a);
		}
		//a[i]=key;
		//System.out.println("准备进入递归");
		show(a);
		if(i-1>start){
			//System.out.println("左侧递归");
			quickSort(a, start, i-1);
		}
		if(j+1<end){
			//System.out.println("右侧递归");
			quickSort(a, j+1, end);
		}
	}
	
	public static void show(int a[]){
		for(int i=0;i<a.length;i++){
			System.out.print(a[i]+"\t");
		}	
		System.out.println();
	}
}

改进：
由于我们已经将a[0]的值保存在了一个key中，因此我们可以不用每次都交换两个数的值，直到最后i=j时再将key值赋到a[i]中，这样的话可以减少交换次数

package com.sort;

public class QuickSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[]= {16,9,3,49,8,7,34,10,12,30};
		System.out.println("原始数据");
		show(a);
		System.out.println("正在排列");
		quickSort(a,0,a.length-1);
		System.out.println("排列后数据");
		show(a);
	}

	public static void quickSort(int a[],int start,int end){
		int key = a[start];
		int i= start;
		int j= end;
		while(i<j){
			while(i<j && a[j]>=key){
				j--;
			}
			a[i]=a[j];
			//System.out.println("从右侧：");
			//show(a);
			while(i<j && a[i]<=key){
				i++;
			}
			a[j]=a[i];
			//System.out.println("从左侧：");
			//show(a);
		}
		a[i]=key;
		//System.out.println("准备进入递归");
		show(a);
		if(i-1>start){
			//System.out.println("左侧递归");
			quickSort(a, start, i-1);
		}
		if(j+1<end){
			//System.out.println("右侧递归");
			quickSort(a, j+1, end);
		}
	}
	
	public static void show(int a[]){
		for(int i=0;i<a.length;i++){
			System.out.print(a[i]+"\t");
		}	
		System.out.println();
	}
}