How to implement the Quick Sort algorithm in C++?

One way to implement the quick sort algorithm in C++ is through recursion. Below is an example code demonstrating the implementation of the quick sort algorithm.

#include <iostream>
using namespace std;

// 交换两个元素的值
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]; // 选取最后一个元素作为基准元素
    int i = low - 1; // i 表示小于基准元素的子数组的最后一个元素的索引

    for (int j = low; j < high; 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 pivotIndex = partition(arr, low, high); // 获取基准元素的索引
        quickSort(arr, low, pivotIndex - 1); // 对基准元素的左边子数组进行快速排序
        quickSort(arr, pivotIndex + 1, high); // 对基准元素的右边子数组进行快速排序
    }
}

int main()
{
    int arr[] = { 5, 3, 8, 6, 2, 7, 1, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    cout << "排序后的数组：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

This code starts by defining a swap function to swap the values of two elements in an array. Then, it defines a partition function to divide the array into two subarrays and return the index of the pivot element. Finally, it defines a quickSort function that uses recursion to perform quick sorting.

In the main function, we define an array called arr to be sorted and calculate the length of the array. We then call the quickSort function to sort the array quickly and output the sorted array.

The code above represents a simple implementation of quick sort. There are many details and optimization methods for quick sort that can be adjusted and optimized according to actual needs.