快速排序（快排）实现及原理

一、算法概述

快速排序（Quick Sort）是由Tony Hoare在1960年提出的一种分治算法，平均时间复杂度为O(n log n)，最坏情况下为O(n²)。它是目前实践中最高效的通用排序算法之一。

核心思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后递归地对这两部分记录继续进行排序。

二、算法原理

1. 基本步骤

1. 选择基准（pivot）：从数组中选择一个元素作为基准
2. 分区操作（partition）：将数组分为两部分，小于基准的放在左边，大于基准的放在右边
3. 递归排序：对左右两个子数组递归地进行快速排序

2. 关键特性

• 不稳定排序：相同元素的相对位置可能改变
• 原地排序：只需要O(log n)的额外空间（递归栈）
• 适应性：对于部分有序数组效率较高

优化点：基准选择策略（随机化、三数取中等）能显著影响算法性能，避免最坏情况

三、代码实现

Java实现

public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {// 获取分区点索引int pivotIndex = partition(arr, low, high);// 递归排序左子数组quickSort(arr, low, pivotIndex - 1);// 递归排序右子数组quickSort(arr, pivotIndex + 1, high);}}private static int partition(int[] arr, int low, int high) {// 选择最右元素作为基准（可优化为随机选择）int pivot = arr[high];// 小于基准的边界索引int i = low - 1;