c++ 快速排序算法【过程图解】

C++ 快速排序算法【过程图解】

快速排序是一种常用的排序算法，其基本原理是通过分治的思想将待排序序列分成若干子序列，使得每个子序列都是有序的。具体实现时，首先选择一定的元素作为基准值，然后将比基准值小的元素全部放在基准值的左边，比基准值大的元素全部放在基准值的右边，这样就将序列分成了分别包含较小元素和较大元素的两个子序列。然后，递归地对子序列进行排序，最终将整个序列排序完成。

下面是使用 C++ 语言实现快速排序的代码示例：

#include <iostream>
#include <algorithm>
using namespace std;

// 定义交换函数
void swap(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}

// 定义快速排序函数
void quick_sort(int A[], int start, int end) {
    if (start >= end) {
        return; // 递归终止条件
    }
    int pivot = A[start]; // 定义基准值
    int left = start + 1; // 定义左指针
    int right = end; // 定义右指针
    while (left <= right) {
        if (A[left] < pivot) {
            left++; // 如果左指针中的元素小于基准值，向右移动左指针
        } else if (A[right] > pivot) {
            right--; // 如果右指针中的元素大于基准值，向左移动右指针
        } else {
            swap(A[left], A[right]); // 如果左指针中的元素大于基准值且右指针中的元素小于基准值，交换两个指针所指向的元素
            left++; // 继续向右移动左指针
            right--; // 继续向左移动右指针
        }
    }
    swap(A[start], A[right]); // 将基准值和右指针所指向的元素交换
    quick_sort(A, start, right - 1); // 递归排序左子序列
    quick_sort(A, right + 1, end); // 递归排序右子序列
}

int main() {
    int A[] = {3, 1, 4, 7, 2, 5, 8, 6};
    int n = sizeof(A) / sizeof(int);
    quick_sort(A, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
    return 0;
}

上面的代码中，首先定义了一个 swap() 函数来实现交换操作。然后定义了 quick_sort() 函数，该函数的参数包括待排序数组 A[]、起始位置 start 和结束位置 end。在 quick_sort() 函数中，首先判断递归是否应当结束，如果起始位置已经大于等于结束位置，则说明该子序列已经有序，递归终止；否则，选择序列中的第一个元素作为基准值 pivot，然后定义两个指针 left 和 right，分别指向序列的首尾元素，开始进行元素交换。当 left 指针所指向的元素小于基准值时，left 指针向右移动；当 right 指针所指向的元素大于基准值时，right 指针向左移动；当 left 和 right 指针分别指向的元素大小关系和基准值大小关系不同时，交换两个元素。最后将基准值和 right 指针所指向的元素交换，然后递归对子序列进行排序。

下面分别对两个示例说明：

示例一

对数组 {3, 1, 4, 7, 2, 5, 8, 6} 进行快速排序，过程如下：

1. 选择 3 作为基准值，指针 left 指向 1，指针 right 指向 6。
2. 从左向右找到第一个大于等于基准值 3 的元素 7 和 left 指针交换位置，此时序列为 {7, 1, 4, 3, 2, 5, 8, 6}，指针 right 指向 5。
3. 从右向左找到第一个小于等于基准值 3 的元素 2 和 right 指针交换位置，此时序列为 {7, 1, 4, 2, 3, 5, 8, 6}，指针 left 指向 4。
4. 继续重复步骤 2 和 3，直到 left 和 right 指针相遇为止，此时序列为 {2, 1, 3, 4, 7, 5, 8, 6}，并且 left 和 right 指针重合的位置是 3。
5. 将基准值 3 和位置 3 上的元素交换位置，此时序列为 {2, 1, 3, 4, 7, 5, 8, 6}。
6. 对左子序列 {2, 1}、右子序列 {4, 7, 5, 8, 6} 分别重复上述步骤，直到整个序列有序。

最终，排序后的序列为 {1, 2, 3, 4, 5, 6, 7, 8}。

示例二

对数组 {3, 2, 1, 4, 5} 进行快速排序，过程如下：

1. 选择 3 作为基准值，指针 left 指向 2，指针 right 指向 4。
2. 从左向右找到第一个大于等于基准值 3 的元素 4。
3. 从右向左找到第一个小于等于基准值 3 的元素 2。
4. 交换元素 4 和 2 的位置，此时序列为 {2, 4, 1, 3, 5}。
5. 继续重复步骤 2 和 3，直到 left 和 right 指针相遇为止。
6. 将基准值 3 和位置 2 上的元素交换位置，此时序列为 {2, 3, 1, 4, 5}。
7. 对左子序列 {2, 1}、右子序列 {4, 5} 分别重复上述步骤，直到整个序列有序。

最终，排序后的序列为 {1, 2, 3, 4, 5}。