C++ 中快排的递归和非递归实现

下面是关于C++中快排的递归和非递归实现的详细攻略。

快速排序

快速排序是一种基于分治的排序算法，其主要思想是将待排序序列划分为三部分，左边是小于等于基准值的部分，右边是大于等于基准值的部分，中间是分界点，基准值一般选取序列的第一个数或者随机选取一个数。然后对左右两个部分递归调用快排算法，直到每个小部分只有一个数或为空。

递归实现

递归实现快速排序的核心是 partition 函数，它负责将待排序数组划分成左右两部分并返回分界点位置。以下是 C++ 代码：

int partition(int nums[], int left, int right) {
    int pivot = nums[left]; // 选取第一个数作为枢轴
    int i = left + 1, j = right;
    while (i <= j) {
        if (nums[i] > pivot && nums[j] < pivot) {
            swap(nums[i++], nums[j--]);
        }
        if (nums[i] <= pivot) i++;
        if (nums[j] >= pivot) j--;
    }
    swap(nums[left], nums[j]);
    return j;
}

void quicksort(int nums[], int left, int right) {
    if (left >= right) return;
    int pivotIndex = partition(nums, left, right);
    quicksort(nums, left, pivotIndex - 1);
    quicksort(nums, pivotIndex + 1, right);
}

partition 函数中，i 和 j 指针分别从左右两端开始扫描，只要 i 所指向的数大于枢轴（即该数应该在右边部分），j所指向的数小于枢轴（即该数应该在左边部分），就将他们交换位置。最终 j就是分界点的位置，将枢轴值与其交换即将数组划分为两部分。

quicksort 函数中的 if (left >= right) return; 是递归终止条件。 pivotIndex是分界点，根据分界点将数组划分为两部分，分别递归调用 quicksort 函数。

非递归实现

快排递归实现算法虽然简单易懂，但是递归调用会占用大量的函数调用栈空间，对于大规模数据来说，如果采用递归实现会导致栈溢出，因此需要采用非递归实现。

非递归实现快速排序需要用到栈，可以手动模拟函数调用栈的操作。以下是 C++ 代码：

void quicksort(int nums[], int left, int right) {
    stack<int> stk;
    if (left < right) {
        stk.push(right);
        stk.push(left);
        while (!stk.empty()) {
            int l = stk.top(); stk.pop();
            int r = stk.top(); stk.pop();
            int p = partition(nums, l, r);
            if (l < p - 1) {
                stk.push(p - 1);
                stk.push(l);
            }
            if (p + 1 < r) {
                stk.push(r);
                stk.push(p + 1);
            }
        }
    }
}

使用栈模拟函数调用栈的过程就是在分治过程中选用堆栈换取递归的便利性。将堆栈初始化为整个序列，然后逐步缩小范围，最终使序列有序。

示例说明

下面用两个示例说明递归和非递归实现快速排序的过程。

假设有一个数组 arr = [3, 1, 5, 2, 4, 6, 7]，首先是递归实现：

选取第一个数 3 作为枢轴，执行 partition 操作后，得到数组状态为 arr = [2, 1, 3, 5, 4, 6, 7]，分界点为2，左边是 [2, 1]，右边是 [5, 4, 6, 7]
对左边的 [2, 1]，选取第一个数 2 作为枢轴，执行 partition 操作后，得到数组状态为 arr = [1, 2, 3, 5, 4, 6, 7]，分界点为1，左边是 [1],右边是 [2, 3, 5, 4, 6, 7]
对右边的 [2, 3, 5, 4, 6, 7]，选取第一个数 2 作为枢轴，执行 partition 操作后，得到数组状态为 arr = [1, 2, 3, 4, 5, 6, 7]，分界点为4，左边是 [2, 3, 4], 右边是 [5, 6, 7]

最终数组 arr 已经有序。

再来看非递归实现。按照相同的过程，使用栈来模拟分治的过程：

选取第一个数 3 作为枢轴，执行 partition 操作后，得到数组状态为 arr = [2, 1, 3, 5, 4, 6, 7]，分界点为2，左边是 [2, 1]，右边是 [5, 4, 6, 7]，将 [5, 4, 6, 7] 和 [2, 1] 两个区间分别入栈
取出栈顶区间 [5, 4, 6, 7]，选取第一个数 5 作为枢轴，执行 partition 操作后，得到数组状态为arr = [2, 1, 3, 4, 5, 6, 7]，分界点为5，左边是 [4]，右边是 [6, 7]。将右边的区间 [6, 7] 和原来的区间 [5, 4, 6, 7] 继续入栈，栈内状态为 [7, 6, 2, 1]
取出栈顶区间 [7, 6]，选取第一个数 7 作为枢轴，执行 partition 操作后，得到数组状态为 arr = [2, 1, 3, 4, 5, 6, 7]，区间已经有序，不需要入栈。取出栈顶区间 [5, 4, 6]，选取第一个数 5 作为枢轴，执行 partition 操作后，得到数组状态为 arr = [2, 1, 3, 4, 5, 6, 7]，分界点为4，左边是 [4]，右边是 [6]，将右边的区间 [6] 和原来的区间 [5, 4, 6] 继续入栈。栈内状态为 [6, 2, 1]
取出栈顶区间 [6]，这是一个只有一个元素的区间，不需要排序。