快速排序（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 << " ";

}