快速排序Java代码简洁实现
学习过数据结构的同学们都知道，快速排序算法是一种时间复杂度为O(nlogn)的排序算法，在各种排序算法中算是较为高效的方法，企业面试中也经常有手撕快排的环节。本文将阐述算法的基本思想，并用Java代码的形式实现快速排序代码。
算法思想
快速排序主要采用分治的基本思想，每次将一个位置上的数据归位，此时该数左边的所有数据都比该数小，右边所有的数据都比该数大，然后递归将已归位的数据左右两边再次进行快排，从而实现所有数据的归位。
举例
我们有一组待排序数据：
❝5 2 6 9 1 3 4 8 7 10
❞
我们首先拿到数组中的首个数字k=5，并且设置两个指针i和j。将i设置指向数组的起始数字5，j设置指向数组的末尾数字10。首先将j指向的数字与k比较，如果比k小，则将i和j指向的数字交换，如果不小于k则j指针不断向前移动。我们可以看到本例中j的移动过程是10->7->8->4，此时4比5小，则交换4和5，变成了如下序列：
❝4 2 6 9 1 3 5 8 7 10
❞
每次交换后，另一个指针开始移动，i指针不断向后移动，寻找比5大的数字。i的移动过程是4->2->6，此时6比5大，则交换5和6，变成了如下序列：
❝4 2 5 9 1 3 6 8 7 10
❞
再次轮到j指针向前移动，移动过程是6->3，此时3比5小，则交换3和5，变成了如下序列：
❝4 2 3 9 1 5 6 8 7 10
❞
再次轮到i指针向后移动，移动过程是3->9，此时9比5大，则交换9和5，变成了如下序列：
❝4 2 3 5 1 9 6 8 7 10
❞
再次轮到j指针向前移动，移动过程是9->1，此时1比5小，则交换1和5，变成了如下序列：
❝4 2 3 1 5 9 6 8 7 10
❞
此时i指针和j指针相遇，数字5归位。再利用上述思想递归将5左右两边的序列进行排序，最终所有数字归位即可结束。
Java代码实现
public class QuickSort {private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public void quickSort(int[] arr, int start, int end) {if (start >= end)return;int k = arr[start];int i = start, j = end;while (i != j) {while (i < j && arr[j] >= k)--j;swap(arr, i, j);while (i < j && arr[i] <= k)++i;swap(arr, i, j);}quickSort(arr, start, i - 1);quickSort(arr, i + 1, end);}public static void main(String[] args) {int[] arr = {5, 2, 6, 9, 1, 3, 4, 8, 7, 10};new QuickSort().quickSort(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}}