QuickSort Algorithm in C++ Guide

QuickSort is a commonly used sorting algorithm, which involves dividing the data into two independent parts during each round of sorting, with one part containing all data smaller than the other. The process is then repeated recursively on each of these two parts until the entire sequence is sorted.

Here is an example code of implementing the Quick Sort algorithm using C++.

#include<iostream>
using namespace std;

// 交换数组中两个元素的位置
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分割函数，以pivot为基准将数组分割成两部分
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = low - 1;  // i指向小于基准的元素

    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 pivot_index = partition(arr, low, high);
        quickSort(arr, low, pivot_index - 1);
        quickSort(arr, pivot_index + 1, high);
    }
}

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

    quickSort(arr, 0, n - 1);

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

    return 0;
}

In the code above, the swap function is used to exchange the positions of two elements in an array, the partition function is used to divide the array into two parts, and the quickSort function is used to recursively perform quicksort on the two parts.

In the main function, we define an array named arr to be sorted, then call the quickSort function to sort it. Finally, we output the sorted array.