快速排序算法详解及Java实现

快速排序算法概述

快速排序是一种非常高效的排序算法，采用分治策略来对一个数组进行排序。其核心思想是选择一个基准值，然后将数组分为两部分，一部分的所有元素都比基准值小，另一部分的所有元素都比基准值大。这个过程称为分区操作。之后，递归地在两个子数组上重复上述过程，直到整个数组有序。

实现步骤

1. 选择一个基准值，通常选择数组的第一个元素。
2. 从数组的右端开始，找到第一个比基准值小的元素，并将其移动到左端。
3. 从数组的左端开始，找到第一个比基准值大的元素，并将其移动到右端。
4. 重复步骤2和3，直到左指针和右指针相遇。
5. 将基准值放置到中间位置。
6. 对基准值左右两侧的子数组递归执行上述步骤，直至所有子数组均有序。

Java代码实现

public static void quickSort(int[] arr, int left, int right) {
if (left int partitiOnIndex= partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
}

private static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left + 1;
int j = right;
while (true) {
while (i <= j && arr[i] <= pivot) i++;
while (i <= j && arr[j] > pivot) j--;
if (i <= j) {
swap(arr, i, j);
} else {
break;
}
}
swap(arr, left, j);
return j;
}

private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}