快速排序（QuickSort）是一种高效的排序算法，平均时间复杂度为O(n log n)，最坏情况下为O(n^2)。它通过分治法将数组分为较小的子数组来排序。
快速排序代码实现
public class QuickSort { // 主方法，用于调用快速排序方法 public static void main(String[] args) { int[] array = {34, 7, 23, 32, 5, 62}; quickSort(array, 0, array.length - 1); for (int i : array) { System.out.print(i + " "); } } // 快速排序方法 public static void quickSort(int[] array, int low, int high) { if (low < high) { int pivotIndex = partition(array, low, high); // 获取划分点 quickSort(array, low, pivotIndex - 1); // 对左子数组进行递归排序 quickSort(array, pivotIndex + 1, high); // 对右子数组进行递归排序 } } // 划分方法 public static int partition(int[] array, int low, int high) { int pivot = array[high]; // 选择最后一个元素作为枢纽 int i = low - 1; // i是较小元素的索引 for (int j = low; j < high; j++) { // 如果当前元素小于或等于枢纽 if (array[j] <= pivot) { i++; // 交换array[i]和array[j] int temp = array[i]; array[i] = array[j]; array[j] = temp; } } // 交换array[i + 1]和array[high] (或pivot) int temp = array[i + 1]; array[i + 1] = array[high]; array[high] = temp; return i + 1; // 返回划分点索引 } }
示例1：对整数数组进行排序
在主方法中，创建了一个整数数组并调用了quickSort方法对其进行排序。以下是代码的详细解释：
数组初始化：
int[] array = {34, 7, 23, 32, 5, 62};
调用快速排序方法：
quickSort(array, 0, array.length - 1);
打印排序后的数组：
1. for (int i : array) { 2. System.out.print(i + " "); 3. }
- 这段代码遍历排序后的数组并打印每个元素。
代码解释
快速排序方法
public static void quickSort(int[] array, int low, int high) { if (low < high) { int pivotIndex = partition(array, low, high); // 获取划分点 quickSort(array, low, pivotIndex - 1); // 对左子数组进行递归排序 quickSort(array, pivotIndex + 1, high); // 对右子数组进行递归排序 } }
quickSort方法接收三个参数：待排序数组array，子数组的起始索引low和结束索引high。- 如果
low小于high，说明子数组内至少有两个元素需要排序。 - 调用
partition方法获取划分点pivotIndex，然后递归调用quickSort对左子数组和右子数组进行排序。
划分方法
public static int partition(int[] array, int low, int high) { int pivot = array[high]; // 选择最后一个元素作为枢纽 int i = low - 1; // i是较小元素的索引 for (int j = low; j < high; j++) { // 如果当前元素小于或等于枢纽 if (array[j] <= pivot) { i++; // 交换array[i]和array[j] int temp = array[i]; array[i] = array[j]; array[j] = temp; } } // 交换array[i + 1]和array[high] (或pivot) int temp = array[i + 1]; array[i + 1] = array[high]; array[high] = temp; return i + 1; // 返回划分点索引 }
partition方法接收三个参数：待划分数组array，子数组的起始索引low和结束索引high。
选择子数组的最后一个元素作为枢纽元素pivot。
初始化索引i为low - 1，用于记录小于或等于枢纽元素的区域。
遍历子数组中的每个元素，如果当前元素array[j]小于或等于枢纽元素，则将其与array[i]交换位置。
最后，将枢纽元素放置在正确的位置，并返回其索引。
