快速排序(Java版)

作者：追风剑情发布于：2018-10-20 12:25 分类：Algorithms

public class QuickSortTest{
    public static void  main(String[] args){
		int arr[] = {3, 1, 5, 4, 2, 6};
		System.out.println("原数据:");
		printArr(arr);
		
		System.out.println("快速排序过程:");
		quickSort(arr, 0, arr.length-1);
		
		System.out.println("快速排序结束:");
		printArr(arr);
    }
	
	public static void quickSort(int[] arr, int p, int r)
	{
		if (p >= r) //结束递归
			return;
		int q = partition(arr, p, r);
		printArr(arr);
		quickSort(arr, p, q-1); //对左侧排序
		quickSort(arr, q+1, r); //对右侧排序
	}
	
	/**
	 * 将主元arr[r]放到合适的位置
	 * @return 返回主元所在的新位置
	 */
	public static int partition(int[] arr, int p, int r)
	{
		int x = arr[r];//主元
		int i = p;
		for (int j=p; j<r; j++)
		{
			if (arr[j] <= x) {
				exchange(arr, i, j);
				i++;
			}
		}
		//将主元放入正确的位置
		//此时,主元左侧的数据都小于主元,主元右侧的数据都大于主元
		exchange(arr, i, r);
		return i;
	}
	
	/**
	 * 将第r号元素插入到i号位置,其它元素依次后移
	 */
	public static void exchange(int[] arr, int i, int r)
	{
		if (i>=r)
			return;
		int x = arr[r];
		for (int j=r; j>i; j--)
		{
			arr[j] = arr[j-1];
		}
		arr[i] = x;
	}
	
	/**
	 * 打印数组
	 */
	public static void printArr(int[] arr)
	{
		for (int i=0; i<arr.length; i++)
		{
			System.out.print(arr[i]);
			System.out.print(" ");
		}
		System.out.println();
	}
}