Java快速排序知识点（含面试大厂题和源码）

快速排序（Quick Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）的策略来对一个数组进行排序。快速排序的平均时间复杂度为 O(n log n)，在最坏的情况下为 O(n^2)，但这种情况很少发生。快速排序因其高效性而在实际应用中非常受欢迎。

快速排序的工作原理：

选择基准值：从数组中选择一个元素作为基准值（pivot），选择方法有多种，如第一个元素、最后一个元素、中间元素或随机元素。
分区操作：重新排列数组，所有比基准值小的元素摆放在基准值的前面，所有比基准值大的元素摆放在基准值的后面（相等的可以到任一边）。在这个分区退出之后，基准值所在的位置就是其最终位置。
递归排序：递归地对基准值左侧和右侧的子数组进行快速排序。

快速排序的优缺点：

优点：

在平均情况下，快速排序具有很好的性能，时间复杂度为 O(n log n)。
快速排序是原地排序，不需要额外的存储空间。

缺点：

最坏情况下的时间复杂度为 O(n^2)，但可以通过随机化来避免。
快速排序是不稳定的排序方法，相等的元素可能会在排序后相对位置发生变化。

快速排序的Java实现：

java">public class QuickSort {public 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);}}private int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {QuickSort solution = new QuickSort();int[] arr = {10, 7, 8, 9, 1, 5};solution.quickSort(arr, 0, arr.length - 1);System.out.println("Sorted array: " + Arrays.toString(arr));}
}

在面试中，快速排序是一个重要的知识点，它考察应聘者对分治法策略和递归思想的理解。通过实现快速排序，可以展示你对基本算法和数据结构的掌握程度。希望这些知识点和示例代码能够帮助你更好地准备面试！快速排序是一种流行且高效的排序算法，经常被用于面试中考察应聘者的算法实现能力。以下是三道可能出现在大厂面试中的与快速排序相关的编程题目，以及相应的Java源码实现。

题目 1：快速排序实现

描述：
实现快速排序算法，对给定数组进行排序。

示例：

输入: [3, 6, 8, 10, 1, 2, 1]
输出: 经过排序后的数组

Java 源码：

java">import java.util.Arrays;public class QuickSortImplementation {public 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);}}private int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {QuickSortImplementation solution = new QuickSortImplementation();int[] arr = {3, 6, 8, 10, 1, 2, 1};solution.quickSort(arr, 0, arr.length - 1);System.out.println("Sorted array: " + Arrays.toString(arr));}
}

题目 2：快速排序的变种 - 三数取中法的基准选择

描述：
在快速排序中，基准值的选择对性能有很大影响。使用三数取中法选择基准值，即在数组中随机选择三个元素，然后取它们的中值作为基准值。

示例：

输入: [3, 6, 8, 10, 1, 2, 1]
输出: 经过排序后的数组

Java 源码：

java">import java.util.Random;public class QuickSortMedianOfThree {// 其他方法与上题相同，仅 partition 方法改变private int partition(int[] arr, int low, int high) {Random random = new Random();int pivotIndex = medianOfThree(arr, low, high);swap(arr, pivotIndex, high);int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;}private int medianOfThree(int[] arr, int low, int high) {int mid = low + (high - low) / 2;if (arr[low] > arr[mid]) swap(arr, low, mid);if (arr[low] > arr[high]) swap(arr, low, high);if (arr[mid] > arr[high]) swap(arr, mid, high);swap(arr, mid, high);return high;}// swap 方法与上题相同// main 方法与上题相同
}

题目 3：快速排序优化 - 尾递归优化

描述：
在快速排序中，对较小的子数组使用尾递归优化，以减少递归深度。

示例：

输入: [3, 6, 8, 10, 1, 2, 1]
输出: 经过排序后的数组

Java 源码：

java">public class QuickSortTailRecursion {// quickSort 方法与上题相同private int partition(int[] arr, int low, int high) {// ... 与上题相同}private void swap(int[] arr, int i, int j) {// ... 与上题相同}public static void main(String[] args) {QuickSortTailRecursion solution = new QuickSortTailRecursion();int[] arr = {3, 6, 8, 10, 1, 2, 1};solution.quickSort(arr, 0, arr.length - 1);System.out.println("Sorted array: " + Arrays.toString(arr));}// 添加 tailRecursiveQuickSort 方法进行尾递归优化public void tailRecursiveQuickSort(int[] arr, int low, int high) {while (low < high) {int pivotIndex = partition(arr, low, high);if (pivotIndex - low < high - pivotIndex) {tailRecursiveQuickSort(arr, low, pivotIndex - 1);low = pivotIndex + 1;} else {tailRecursiveQuickSort(arr, pivotIndex + 1, high);high = pivotIndex - 1;}}}
}