快速排序----Java实现

快排是由冒泡排序改进而得的。冒泡一次交换只能消除一个逆序，而快排的一次交换可以消除多个逆序，从而大大加快排序的速度。

算法步骤：

在待排序的n个记录（元素）中任取一个记录（通常取第一个记录）作为枢轴（或者叫支点，就是先随便取一个数），设它的值为key。快排就是在每一趟排序后，把所有值小于key的记录交换到key前面，而把比key大的记录交换到key的后面，最后将key放到“中间”（分界处）位置。这样待排序的记录就被分成了两个子表（就是左边比key小的重新作为一个表，右边比key大的也作为一个新的表）。然后分别对左右子表重复上述步骤，直至每一个子表只有一个记录。

根据上述描述可以很容易发现这是一个递归，即把一个原表进行一定的排序操作后拆成左右两个子表再递归进行排序操作，直至子表中只有一个记录时，结束递归。

如何将一个原表拆分成左边比枢轴key小的，右边比枢轴key大的两个子表：

1. 选择待排序表中的第一个记录作为枢轴，开一个临时变量存储枢轴key的值。附设两个指针low和high分别指向表的上界和下界（即指向左右两端）

2. 从表的最右侧位置一次向左搜索，找到第一个值小于枢轴key的记录并和枢轴key交换。具体操作：当low<high时，若high所指记录的值大于枢轴key，则high左移（high--），否则将high所指记录与枢轴记录进行交换

3. 然后再从表的最左侧位置，一次向右搜索找到第一个值大于枢轴key的记录和枢轴进行交换。具体操作：当low<high时，若low所指位置的值小于key，则low右移（low++），否则将low所指记录与枢轴key交换

4. 重复2，3步骤，直至low和high相等为止，此时low和high的位置就是枢轴key应该所在的“中间”位置，然后将key放入该位置，这时原表就被分为两个子表了。因为key的位置要最后才确定，而且每次交换不是low与key交换就是high与key交换，所以我们只需一开始用临时变量将key的值存起来，然后交换过程中就只需low或者high的单向移动即可。

拆分为两个子表后，然后再根据条件判断是否子表中只含有一个记录了，若只有一个记录则返回，若还有多个记录，则需继续递归，直至子表中的记录只有一个为止。

示例代码：

package practice;
import java.util.Scanner;
/**
 * MyArray类，只含有一个静态方法和一个程序入口<br>
 * 该类构造函数私有，所以无法继承
 * @author tiny_spot
 */
public class MyArray {
	private MyArray() {}//构造函数私有，即不允许被继承
	/**
	 * quickSort函数对数组使用快速排序进行排序
	 * @param a 数组形参
	 * @param low 想要排序的最左端索引
	 * @param high 想要排序段的最右段的索引
	 */
	public static void quickSort(int a[] ,int low ,int high) {
		/*
		 * low和high分别作为数组的上界和下界（即指针指向两端）
		 * key表示整个数组的枢轴，取最左端第一个元素作为枢轴
		 */
		int key=a[low] ,tlow=low ,thigh=high;
		while(low < high) {
			while(low<high && a[high]>=key) high--;
			a[low] = a[high];//将比枢轴值小的元素移至低端
			while(low<high && a[low]<=key) low++;
			a[high] = a[low];//将比枢轴值大的元素移至高端
		}//while循环结束后，原表被分为两个子表
		a[low] = key;//将枢轴放入它应该在的位置，这时low之前的元素都小于枢轴值，low之后的元素都大于枢轴
		if(tlow < low)//如果此时枢轴的位置未到数组边缘，则继续递归
			quickSort(a, tlow, low-1);//对左子表递归排序
		if(low < thigh)//若枢轴位置不在最右端，对右子表递归排序
			quickSort(a, low+1, thigh);
	}
	public static void main(String args[]) {
		int n;//数组元素个数
		Scanner s = new Scanner(System.in);
		n = s.nextInt();//从键盘敲入n
		int a[] = new int[n];//定义数组长度为n
		for(int i = 0 ; i < n ; i++)
			a[i] = s.nextInt();//循环输入n个整数
		MyArray.quickSort(a ,0 ,a.length-1);//调用方法进行排序
		for(int i = 0 ; i < a.length ; i++)//输出排序后的元素
			System.out.print(a[i]+" ");
	}
}