快速排序算法讲解(c基础)

一、快速排序的基本原理

快速排序是一种基于分治策略的高效排序算法。它的基本思想是：

选择一个基准元素（pivot），通过一趟排序将待排序序列分割成两部分，其中一部分的所有元素都比基准元素小，另一部分的所有元素都比基准元素大。然后，分别对这两部分继续进行快速排序，直到整个序列都有序。

二、快速排序的具体实现步骤

1. 选择基准元素

通常可以选择待排序序列中的第一个元素、最后一个元素或者中间元素等作为基准元素。在示例代码中，我们常选取待排序数组的最后一个元素作为基准元素，例如：

隐藏过程

复制

int pivot = arr[high];

2. 划分操作（Partition）

这是快速排序的关键步骤，目的是通过比较和交换元素，将数组划分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。

具体实现过程如下：

设置两个指针，一个指针 i 初始指向待排序序列的第一个元素的前一个位置（即 low - 1），另一个指针 j 从待排序序列的第一个元素（即 low）开始。

展开过程

遍历数组，比较每个元素与基准元素的大小关系。当 j 指向的元素小于基准元素时，将 i 指针先向前移动一位（因为 i 初始位置在第一个元素之前），然后交换 i 和 j 所指向的元素。

展开过程

遍历完整个数组（除了基准元素本身，因为基准元素在最后一个位置，前面的循环到 high - 1 就结束了）后，将基准元素与 i + 1 位置的元素进行交换。这样就完成了一次划分操作，使得基准元素处于正确的位置，左边的元素都小于它，右边的元素都大于它。

展开过程

3. 递归排序

完成一次划分操作后，得到了基准元素的正确位置（假设为 pi），此时数组被分成了两部分：arr[low] 到 arr[pi - 1] 和 arr[pi + 1] 到 arr[high]。然后分别对这两部分递归地调用快速排序函数，直到整个数组都有序。

隐藏过程

复制

if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);
}

三、快速排序的代码示例

以下是完整的快速排序 C 语言代码示例，包含了交换函数 swap、划分函数 partition 和快速排序主函数 quickSort：

隐藏过程

复制

#include <stdio.h>// 交换两个整数的函数
void swap(int *a, int *b) {int t = *a;*a = *b;*b = t;
}// 划分函数，将数组划分为两部分
int partition(int arr[], int low, int high) {int pivot = arr[high];int i = (low - 1);for (int j = low; j <= high - 1; j++) {if (arr[j] < pivot) {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 pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, high, pi + 1);}
}int main() {int arr[] = {5, 4, 3, 2, 1};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);printf("排序后的数组: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

四、快速排序的时间复杂度和空间复杂度

1. 时间复杂度

平均情况：快速排序在平均情况下的时间复杂度为。这是因为每次划分操作大致能将数组分成两部分，需要递归地对两部分进行排序，而递归的深度大约为（以 2 为底），每次划分操作需要遍历数组中的大约个元素，所以总的时间复杂度为。
最坏情况：当选择的基准元素总是数组中的最大或最小元素时，每次划分操作只能将数组分成一个元素和其余元素两部分，这样就需要进行次划分操作，每次划分操作需要遍历数组中的个元素，此时时间复杂度为。不过，通过合理选择基准元素（如随机选择基准元素等方法）可以尽量避免这种最坏情况的发生。