java实现快速排序：

java实现快速排序：

首先来看一个问题：我们快排第一步是找一个基准值 ，然后右边值都大于基准值，左边值都小于基准值。通常我们选取最后一个或者第一个值为我们的基准值。下边我们选取最后一个值作为基准值

题目一：给定一个整型数组，然后以最后一个数为基准，将大于基准值的放右边，小于基准值放到左边。最后数组的情况就是，在基准值两边，一边是全部大于基准值，一边是全部小于基准值;

我们使用三个指针来区分三块，一块是小于区域，中间是等于区域，右边是大于区域。开始的时候，小于和大于区域都是在数组外边，要是存在一个符合要求的，就放到相应区域，同时该区域长度就增加1。如果是有一个小于的，首先交换当前值和less后边那个值，那么小于的区域的指针就++less,同时也会推着中间部分往右边跑，所以当前指针cur++;如果是满足大于区域，就把当前cur指向的数和大于那边的区域的边界more前边的那个数值交换，同时大于区域增加，就是--more,但是这里我们的cur就不变化。

代码：

package test2018926;

public class QuickSort {
	public static void main(String[] args) {
		Integer[] arr = { 1, 2, 7, 5, 4, 3 };
		partition(arr, 0, arr.length - 1);
	}

	public static Integer[] partition(Integer[] arr, int L, int R) {

		// 使用三个指针来将我们的数据分成三类，
		int cur = L;// 这个指向当前数据
		int less = L - 1;// 小数的前面一个
		int more = R + 1;// 大数的后边一个
		int num = arr[arr.length - 1];// 以最后一个值为基准来排出大于和小于
		Integer[] arr1 = new Integer[2];
		while (cur < more) {
			// System.out.println(cur);
			if (arr[cur] > num) {
				swap(arr, cur, --more);
			} else if (arr[cur] < num) {
				swap(arr, cur++, ++less);// less位置增加一个，就会推着cur向后
			} else {
				cur++;
			}
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]);
		}
		arr1[0] = less + 1;
		arr1[1] = more - 1;
		return arr1;
	}

	// 交换数组位置
	private static void swap(Integer[] arr, Integer m, Integer n) {
		int temp = arr[m];
		arr[m] = arr[n];
		arr[n] = temp;
	}
}

控制台打印：

 

 

下边讲解我们的快排：快排就是不断细分，对一个小部分都进行上边相同的操作。

开始分为两边，然后对两边分别再分两边，一直分到最小，就是分成单个为止。

package test2018926;

public class QuickSort {
	public static void main(String[] args) {
		Integer[] arr = { 1, 2, 7, 5, 4, 3 };
		quickSort(arr, 0, arr.length - 1);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]);
		}
	}

	public static void quickSort(Integer[] arr, int L, int R) {
		if (L < R) {
			Integer[] p = partition(arr, L, R);// 返回的是相同数值区域的两个边界
			quickSort(arr, L, p[1] - 1);
			quickSort(arr, p[0] + 1, R);

		}

	}

	public static Integer[] partition(Integer[] arr, int L, int R) {

		// 使用三个指针来将我们的数据分成三类，
		int cur = L;// 这个指向当前数据
		int less = L - 1;// 小数的前面一个
		int more = R + 1;// 大数的后边一个
		int num = arr[arr.length - 1];// 以最后一个值为基准来排出大于和小于
		Integer[] arr1 = new Integer[2];
		while (cur < more) {
			// System.out.println(cur);
			if (arr[cur] > num) {
				swap(arr, cur, --more);
			} else if (arr[cur] < num) {
				swap(arr, cur++, ++less);// less位置增加一个，就会推着cur向后
			} else {
				cur++;
			}
		}
		for (int i = 0; i < arr.length; i++) {
			// System.out.print(arr[i]);
		}
		arr1[0] = less + 1;
		arr1[1] = more - 1;
		return arr1;
	}

	// 交换数组位置
	private static void swap(Integer[] arr, Integer m, Integer n) {
		int temp = arr[m];
		arr[m] = arr[n];
		arr[n] = temp;
	}
}

控制台打印：