Java快速排序定义
快速排序（Quick Sort）是一种常用的排序算法，主要就是通过分治的策略将一个大问题分解为小问题，并逐步解决小问题，最终得到整体的解。
Java快速排序实现原理
快速排序的基本思想，主要分为如下步骤：
下面我们来对如下数据进行快速排序：
8，2，5，0，7，4，6，1
第一步：首先我们随机选择一个基准值
从待排序的数组中选择一个元素作为基准值，通常选择数组的第一个元素、最后一个元素或者随机选择。
如下图所示：
第二步：分区操作
将数组中的其他元素与基准值进行比较，并按照小于基准值和大于基准值的规则将数组分为两个部分。
通常将小于基准值的元素放在基准值的左侧，大于基准值的元素放在基准值的右侧。
比如，先排右边，与其他元素依次比较，大的放右边，小的放左边。
如下图所示：
然后我们以同样的方式排左边的数据，如下图所示:
第三步：递归排序合并结果
对分区后的两个子数组递归地应用快速排序算法，直到子数组的大小为1或0，即已经有序。
比如，继续排 0 和 1，如下图所示 ：
由于只剩下一个数，所以就不用排了。
现在的数组序列是下图这个样子：
右边以同样的操作进行，即可排序完成。
看完了上面的图解，我们再综合起来看一个快速排序的全过程。
如下动图所示：
快速排序的关键在于分区操作，其核心思想是通过每一次分区操作将基准值放置到正确的位置，并且保证基准值左侧的元素都小于基准值，右侧的元素都大于基准值。
这样在递归排序时，只需要对基准值左右两侧的子数组进行排序即可。
Java快速排序代码示例
下面是一个使用Java实现的快速排序算法示例：
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2};
System.out.println("原始数组：");
printArray(arr);
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后数组：");
printArray(arr);
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1); // 对左半部分进行快速排序
quickSort(arr, pivotIndex + 1, high); // 对右半部分进行快速排序
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // 选取最后一个元素作为基准值
int i = low - 1; // i用于指向小于基准值的元素的位置
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j); // 将小于基准值的元素交换到左侧
}
}
swap(arr, i + 1, high); // 将基准值放到正确的位置
return i + 1; // 返回基准值的位置
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
输出结果示例：
原始数组： 5 3 8 4 2 排序后数组： 2 3 4 5 8
Java快速排序总结
Java快速排序的基本思想是选择一个基准值（通常是数组中的一个元素），将小于基准值的元素放在左侧，大于基准值的元素放在右侧，然后对左右两个部分递归地进行快速排序。
mikechen
mikechen睿哥，10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获知最新一线技术干货！
