快速排序（Quick Sort）是一种高效的排序算法，由英国计算机科学家东尼·霍尔（Tony Hoare）于 1960 年发明。本文将详细讲解快速排序算法的原理和实现，并通过 C++ 语言展示其代码实现。
快速排序算法的基本思想是分治法（Divide and Conquer），其核心步骤如下：
1. 选择一个基准元素（pivot），通常选择序列中的第一个或最后一个元素。
2. 将序列分为两部分，一部分是小于等于基准元素的元素，另一部分是大于基准元素的元素。
3. 递归地对这两部分序列进行快速排序。
快速排序的时间复杂度平均为 O(nlogn)，最坏情况下为 O(n^2)，但这种情况很少出现。
下面我们将通过 C++ 语言实现快速排序算法。
首先，我们需要一个交换两个元素的函数：
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) {
// pi 是分区后的基准元素索引
int pi = partition(arr, low, high);
// 递归地对两部分序列进行快速排序
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
到此为止，我们的程序就写完了，来看看全部的代码合在一起长什么样子吧。
#include <iostream>
using namespace std;
void swap(int* a, int* b);
int partition(int arr[], int low, int high);
void quickSort(int arr[], low, int high);
void printArray(int arr[], int size);
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
printArray(arr, n);
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
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, pi + 1, high);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << " ";
}