一、什么是快速排序快速排序Quick Sort是一种高效的分治排序算法由 Tony Hoare 在 1959 年提出。它的核心思想是选择一个基准值Pivot将数组分为两部分比基准值小的元素放在左边比基准值大的元素放在右边然后递归地对左右两部分进行排序直到整个数组有序。简单来说快速排序就像 “分地盘”选一个基准值把数组分成 “小的” 和 “大的” 两部分基准值放到正确的位置左边全是比它小的右边全是比它大的重复这个过程直到所有元素都排好序。二、快速排序的核心步骤快速排序的核心步骤可以分为以下几步选择基准值从数组中选择一个元素作为基准值通常选择最后一个元素分区Partition将数组中比基准值小的元素交换到左边比基准值大的元素留在右边递归排序对基准值左边和右边的子数组分别递归进行快速排序。三、快速排序的代码实现1. Python 版本直观易懂def partition(arr, low, high): # 选择最后一个元素作为基准值 pivot arr[high] # i指针标记小于基准值的分界线 i low - 1 # j指针从左到右逐个比较 for j in range(low, high): if arr[j] pivot: i 1 # 交换把小数换到i的位置 arr[i], arr[j] arr[j], arr[i] # 交换把基准值放到正确的位置 arr[i 1], arr[high] arr[high], arr[i 1] # 返回基准值的位置 return i 1 def quicksort(arr, low, high): if low high: # 分区得到基准值的位置 p partition(arr, low, high) # 递归排序左边 quicksort(arr, low, p - 1) # 递归排序右边 quicksort(arr, p 1, high) # 测试 arr [10, 7, 8, 9, 1, 5] n len(arr) quicksort(arr, 0, n - 1) print(排序后的数组, arr) # 输出[1, 5, 7, 8, 9, 10]2. C 语言版本更贴近底层#include stdio.h // 交换两个元素 void swap(int* a, int* b) { int temp *a; *a *b; *b temp; } // 分区函数 int partition(int arr[], int low, int high) { // 选择最后一个元素作为基准值 int pivot arr[high]; // i指针标记小于基准值的分界线 int i low - 1; // j指针从左到右逐个比较 for (int j low; j high; j) { if (arr[j] pivot) { i; // 交换把小数换到i的位置 swap(arr[i], arr[j]); } } // 交换把基准值放到正确的位置 swap(arr[i 1], arr[high]); // 返回基准值的位置 return i 1; } // 快速排序函数 void quicksort(int arr[], int low, int high) { if (low high) { // 分区得到基准值的位置 int p partition(arr, low, high); // 递归排序左边 quicksort(arr, low, p - 1); // 递归排序右边 quicksort(arr, p 1, high); } } // 打印数组 void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {10, 7, 8, 9, 1, 5}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); quicksort(arr, 0, n - 1); printf(排序后); printArray(arr, n); // 输出1 5 7 8 9 10 return 0; }四、快速排序的时间复杂度和空间复杂度平均时间复杂度O (n log n)因为每次分区将数组分成两部分递归深度为 log n每层处理 n 个元素最坏时间复杂度O (n²)当数组已经有序时每次分区只能分成一个元素和剩下的元素递归深度为 n空间复杂度O (log n)递归调用栈的深度稳定性不稳定因为交换操作可能会改变相同元素的相对位置。五、快速排序的优化为了避免最坏情况的发生可以对快速排序进行以下优化随机选择基准值每次随机选择一个元素作为基准值避免数组有序时的最坏情况三数取中选择数组的第一个、中间和最后一个元素的中位数作为基准值提高分区的平衡性尾递归优化只递归排序较小的子数组减少递归调用栈的深度插入排序优化当子数组的大小小于某个阈值如 10时使用插入排序代替快速排序因为插入排序在小规模数据上效率更高。六、快速排序的实际应用场景快速排序是实际开发中最常用的排序算法之一常见场景包括大规模数据排序快速排序的平均时间复杂度为 O (n log n)适合大规模数据排序内存受限场景快速排序是原地排序算法不需要额外的内存空间通用排序需求大多数编程语言的标准库排序函数如 C 的std::sort、Python 的sorted都使用快速排序或其优化版本。七、总结快速排序是一种高效的分治排序算法它的核心思想是选择一个基准值将数组分为两部分然后递归地对左右两部分进行排序。快速排序的平均时间复杂度为 O (n log n)空间复杂度为 O (log n)是实际开发中最常用的排序算法之一。希望这篇文章能帮助你理解快速排序的原理和实现