Java 实现快速排序（Java实现快速排序一个数组）

快速排序的思想跟二分排序很相似，都是将一个问题拆分成两个小问题的形式。主要步骤有如下三个：

分解：将数组分解成A[0,p - 1] <= A[p] 且 < [p + 1, arr.lenth]这样的形式。

解决：通过递归调用快速排序，解决两个被分解的子数组的排序问题。

合并：这里的partition就是对数组进行就地重排，所以不需要合并就已经是排序好了的。

快速排序核心的就是partition将数组分割成两个子数组，实现思想及流程如下图：

快速排序方法调用partition将数组分成两个子数组后，又递归调用排序方法，将已经分解的两个子数组又重新分解成子数组，进行排序，最后成功的排序。具体代码如下：

public static void quickSort(int[] arr, int p, int r) {
 if (p < r) {
 int q = partition(arr, p , r);
 quickSort(arr, p, q - 1);
 quickSort(arr, q + 1, r);
 }
}
/**
 * 将一个数组分成<=a[x] 和>=a[x] 两部分，返回x
 * @param arr
 * @param p
 * @param r
 * @return
 */
public static int partition(int[] arr,int p, int r) {
 int x = arr[r];
 int i = p - 1;
 for (int j = p; j <= r - 1; j++) {
 if (arr[j] <= x) {
 i = i + 1;
 int temp = arr[j];
 arr[j] = arr[i];
 arr[i] = temp;
 }
 }
 arr[r] = arr[i + 1];
 arr[i + 1] = x;
 return i + 1;
}