快速排序（分治思想）
什么是快速排序
快速排序（Quick Sort）是一种广泛使用的高效排序算法，由计算机科学家托尼·霍尔在1960年提出。它采用分治法（Divide and Conquer）策略，将一个大数组分为两个小数组，然后递归地对这两个小数组进行排序。快速排序在平均情况下具有良好的性能，时间复为 O(nlogn)O(nlogn)，并且在实际应用中通常比其他 O(nlogn)O(nlogn) 的排序算法（如归并排序和堆排序）更快。
核心思想
快速排序的核心思想可以概括为以下几个步骤：
- 选择基准（Pivot）：从数组中选择一个元素作为基准。基准的选择可以影响排序的效率，常见的选择方法包括选择第一个元素、最后一个元素或随机选择。
- 分区（Partition）：通过一趟扫描，将数组分为两个部分：
这个过程称为分区。在分区完成后，基准元素将处于其最终位置。
- 小于等于基准的元素
- 大于基准的元素
- 递归排序：对基准元素左侧和右侧的子数组进行递归调用快速排序。
- 合并结果：由于基准元素已经在正确的位置，最终的排序结果将由所有递归调用的结果自动合并。
两个指针的定义和移动
在快速排序的实现中，我们使用两个指针 i 和 j 来进行分区操作。
i指针从左到右扫描数组，找到第一个大于基准的元素。j指针从右到左扫描数组，找到第一个小于等于基准的元素。- 当
i小于j时，交换i和j指向的元素。
这个过程一直持续到 i 大于等于 j，此时分区操作完成。
根据基准值交换
在分区过程中，当 i 小于 j 时，我们需要交换 i 和 j 指向的元素。这样可以确保左侧的元素都小于等于基准，右侧的元素都大于基准。
让我们来看两道题目带你快速上手
示例一
题目描述
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
quickSort(arr, 0, n-1);
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
public static void quickSort(int[] arr,int l,int r) {
if (l >= r) return;
int x = arr[l+r >> 1];
int i = l - 1, j = r + 1;
while (i < j) {
do ++i;while (arr[i] < x) ;
do --j;while (arr[j] > x);
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
quickSort(arr, l, j);
quickSort(arr, j + 1, r);
}
}
解释
Scanner scanner = new Scanner(System.in);：创建一个Scanner对象，用于读取输入。int n = scanner.nextInt();：读取数组的长度。int arr[] = new int[n];：创建一个长度为n的整数数组。for (int i = 0; i < n; i++) { arr[i] = scanner.nextInt(); }：循环读取数组的元素。quickSort(arr, 0, arr.length-1);：调用quickSort方法对数组进行排序。for (int i = 0; i < n; i++) { System.out.print(arr[i] + " "); }：输出排序后的数组。if (l >= r) return;：如果左边界l大于或等于右边界r，则直接返回，因为这意味着子数组只有一个元素或为空，不需要排序。int x = arr[l];：选择数组的第一个元素作为基准元素。int i = l - 1, j = r + 1;：初始化两个指针i和j，分别指向数组的左边界的前一个位置和右边界的后一个位置。while (i < j) { ... }：进入主循环，直到i和j指针相遇。if (i < j) { ... }：如果i和j指针没有相遇，交换arr[i]和arr[j]的值。do --j; while (arr[j] > x);：j指针从右向左移动，直到找到一个小于或等于基准元素的元素。do ++i; while (arr[i] < x);：i指针从左向右移动，直到找到一个大于或等于基准元素的元素。quickSort(arr, l, j);：递归地对左子数组进行排序（从l到j）。quickSort(arr, j + 1, r);：递归地对右子数组进行排序（从j + 1到r）。
示例二
题目描述
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n,k;
n = sc.nextInt();
k = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
quickSort(arr, 0, n - 1);
System.out.println(arr[k - 1]);
}
public static void quickSort(int[] arr,int l,int r) {
if (l >= r) return;
int x = arr[l];
int i = l - 1, j = r + 1;
while (i < j) {
do ++i; while (arr[i] < x) ;
do --j; while (arr[j] > x);
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
quickSort(arr, l, j);
quickSort(arr, j + 1, r);
}
}
解释
导入Scanner类：
- 用于读取输入数据。
定义类和main方法：
Scanner sc = new Scanner(System.in);：创建Scanner对象从标准输入读取数据。int n, k;：声明两个整数n和k。n = sc.nextInt(); k = sc.nextInt();：读取数组长度n和目标索引k。int[] arr = new int[n];：创建长度为n的整数数组。for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); }：从输入中读取n个整数，存入数组arr。quickSort(arr, 0, n - 1);：调用quickSort方法对数组进行排序。System.out.println(arr[k - 1]);：输出排序后数组的第k个元素（下标从0开始，所以是k-1）。quickSort方法：
- 使用快速排序算法对数组
arr的从l到r部分进行排序。if (l >= r) return;：如果左边界l大于或等于右边界r，则返回（子数组为空或只有一个元素）。int x = arr[l];：选择子数组的第一个元素作为基准。int i = l - 1, j = r + 1;：初始化两个指针，i和j。- 通过
while循环将数组分割为两个部分，所有小于基准值的元素放在左边，所有大于基准值的元素放在右边，并递归地对两边进行快速排序。
总结
快速排序是一种高效的排序算法，它采用分治法的思想，通过递归的方式将数组分为两个子数组，然后对这两个子数组进行排序。通过选择基准、分区和递归调用，快速排序能够在平均情况下以 O(nlogn)O(nlogn) 的时间复杂度完成排序。尽管在最坏情况下可能退化为 O(n2)O(n2)，但通过合理的基准选择和随机化策略，可以有效避免这一问题。快速排序的空间效率和实际性能使其成为排序任务中的热门选择。