Quick Sort in C++: Algorithm Explained

Quick sort is a commonly used sorting algorithm that divides an array into two subarrays recursively and sorts each subarray separately. The specific steps are as follows:

1. Choose a reference value, which can be any element in the array.
2. Divide the array into two parts so that elements on the left are all less than the pivot value, and elements on the right are all greater than the pivot value.
3. Sort the subarrays on the left and right recursively.
4. Merge the left and right subarrays to obtain the final sorted array.

Below is an example of code implementing quicksort in C++.

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int i = low, j = high, pivot = arr[low];
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                arr[i++] = arr[j];
            }
            while (i < j && arr[i] < pivot) {
                i++;
            }
            if (i < j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = pivot;
        quickSort(arr, low, i - 1);
        quickSort(arr, i + 1, high);
    }
}

// 使用方法
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
quickSort(arr, 0, arr.size() - 1);

In the code above, we initially select the first element of the array as the pivot value, then divide the array into two parts based on the pivot value. Then recursively sort the left and right subarrays, ultimately obtaining a sorted array.