快速排序是一种高效的排序算法,由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 index
for (int j = low; j < high; j++) {
// 如果当前元素小于或等于pivot
if (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));
}
}
这些题目覆盖了数组处理、搜索、排序等常见的编程任务,并展示了在处理这些任务时如何写出高效的Java代码。希望这些示例能帮助你在面试中表现出色。如果你有任何疑问,或需要更多的练习题和建议,请随时告诉我。