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

本文主要是介绍Java快速排序知识点（含面试大厂题含源码），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

快速排序是一种高效的排序算法，由C. A. R. Hoare在1960年提出。它的基本思想是分而治之（Divide and Conquer）。快速排序的关键在于选取一个“基准值”（pivot），然后将数组分为两个子数组：一个包含所有小于基准值的元素，另一个包含所有大于基准值的元素。这个过程称为“分区”（partitioning）。接下来，独立对这两个子数组进行快速排序，最终合并得到一个完整的有序数组。快速排序以其优越的平均时间复杂度而闻名，尤其是在大规模数据集上。

快速排序的步骤：

选择基准值：从数组中选择一个元素作为基准值。基准值的选择可以有多种方式，例如选择第一个元素、最后一个元素、中间元素，或者随机选择一个元素。
分区操作：重新排列数组，使得所有小于基准值的元素放在基准前面，所有大于基准值的元素放在基准后面。在这个分区结束之后，基准值就处于其最终位置。
递归排序子数组：递归地将小于基准值的子数组和大于基准值的子数组排序。

快速排序的特点：

时间复杂度：平均情况下，快速排序的时间复杂度为O(n log n)，在最坏情况下（例如，当输入数组已经是排序好的）时间复杂度为O(n^2)。但通过一些策略，比如“三数取中”选择基准值，可以大幅度降低最坏情况出现的概率。
空间复杂度：快速排序的空间复杂度为O(log n)，这是因为快速排序是递归实现的，需要消耗调用栈空间。
不稳定排序：快速排序是一种不稳定的排序算法，因为分区过程中相等元素的相对位置可能会改变。
原地排序：快速排序是原地排序，不需要额外的存储空间。

Java实现示例

public class QuickSort {public static void sort(int[] arr, int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high);// 递归排序左子数组sort(arr, low, pivotIndex - 1);// 递归排序右子数组sort(arr, pivotIndex + 1, high);}}private static int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = (low - 1); // smaller element indexfor (int j = low; j < high; j++) {// 如果当前元素小于或等于pivotif (arr[j] <= pivot) {i++;// swap arr[i] and arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// swap arr[i+1] and arr[high] (or pivot)int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;}
}

这段代码演示了快速排序的实现，包括选择基准值、分区操作以及递归调用进行排序。你可以使用这段代码在自己的项目中实现快速排序。如果你有任何疑问，或者需要进一步的解释和帮助，请随时提问。### 面试题1：数组去重与快速排序结合

题目描述：给定一个整数数组，你需要先去除数组中的重复元素，然后对剩余元素进行快速排序。请实现这一功能，并尽可能地优化时间和空间复杂度。

Java实现：

import java.util.Arrays;public class UniqueQuickSort {public static int[] uniqueAndSort(int[] arr) {// 数组去重int n = arr.length;Arrays.sort(arr); // 先排序，便于去重int[] temp = new int[n];int j = 0;for (int i = 0; i < n - 1; i++) {if (arr[i] != arr[i + 1]) {temp[j++] = arr[i];}}temp[j++] = arr[n - 1];// 复制去重后的数组int[] uniqueArr = new int[j];System.arraycopy(temp, 0, uniqueArr, 0, j);// 快速排序quickSort(uniqueArr, 0, uniqueArr.length - 1);return uniqueArr;}private static void quickSort(int[] arr, int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}}private static 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++;// 交换 arr[i] 和 arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 交换 arr[i+1] 和 arr[high]int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;}public static void main(String[] args) {int[] arr = {4, 5, 1, 2, 1, 4, 3, 3, 2, 5};int[] result = uniqueAndSort(arr);System.out.println(Arrays.toString(result));}
}

面试题2：找到未排序数组中的最小和最大值

题目描述：给定一个未排序的整数数组，找到其中最小和最大的元素。尝试找出一个尽可能高效的方法来扫描数组，而不使用内置的排序函数。

Java实现：

public class FindMinMax {public static int[] findMinMax(int[] arr) {int min = arr[0];int max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];} else if (arr[i] < min) {min = arr[i];}}return new int[]{min, max};}public static void main(String[] args) {int[] arr = {12, 123, 45, 67, 1};int[] result = findMinMax(arr);System.out.println("Min = " + result[0] + ", Max = " + result[1]);}
}

面试题3：旋转数组的搜索

题目描述：给定一个按照升序排列的整数数组，数组可能在某个未知的点上进行了旋转（例如，[0,1,2,4,5,6,7] 可能变成 [4,5,6,7,0,1,2]）。编写一个函数搜索给定值 target 如果在数组中找到目标值，则返回它的索引，否则返回 -1。你可以假设数组中不存在重复的元素。

Java实现：

public class SearchInRotatedSortedArray {public static int search(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;}// 前半部分有序if (nums[left] <= nums[mid]) {if (target >= nums[left] && target < nums[mid]) {right = mid - 1;} else {left = mid + 1;}} else {if (target > nums[mid] && target <= nums[right]) {left = mid + 1;} else {right = mid - 1;}}}return -1;}public static void main(String[] args) {int[] nums = {4,5,6,7,0,1,2};int target = 0;System.out.println(search(nums, target));}
}