Java实现快速排序算法

原作者：老铁123　　　
出处：https://blog.csdn.net/qewgd/article/details/85949755
本文归作者【老铁123】和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

快速排序
对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。

代码实现

public class QuickSortV2 {
	public static void main(String[] args) {
		int[] arr = { 65, 58, 95, 10, 57, 62, 13, 106, 78, 23, 85 };
		System.out.println("排序前：" + Arrays.toString(arr));
		quickSort(arr, 0, arr.length - 1);
		System.out.println("排序后：" + Arrays.toString(arr));
	}

	public static void quickSort(int[] arr, int left, int right) {
		int mid= 0;
		if (left < right) {
			mid= getMid(arr, left, right);
			quickSort(arr, left, mid- 1);
			quickSort(arr, mid+ 1, right);
		}
	}

	private static int getMid(int[] arr, int left, int right) {
		int key = arr[left];
		while (left < right) {
			while (left < right && arr[right] >= key) {
				right--;
			}
			arr[left] = arr[right];
			while (left < right && arr[left] <= key) {
				left++;
			}
			arr[right] = arr[left];
		}
		arr[left] = key;
		return left;
	}
}