快速排序算法的递归,迭代法实现(C++)

tags: DSA C++ Sort

思路

分治法

主要分成下面三个步骤:

1. 选定基准值(默认是数组首元素), 这里称为pivot
2. 找到基准值待放置的位置(排序之后的位置), 将大于基准值的元素放在基准值后面, 小于的放在前面
3. 递归上述过程.

代码(递归)

下面这种方法是算法导论给出的, 先写子数组处理函数, 再给出递归过程. pivot取最右边元素:

int Partition(vector<int> &arr, int l, int r) {
    /*i: the number of left side of x */
    int x = arr[r], i = l - 1;
    for (int j = l; j < r; ++j)
        if (arr[j] <= x) swap(arr[++i], arr[j]);
    swap(arr[++i], arr[r]);
    return i; // 返回pivot插入的位置
}
// 递归实现快速排序算法
void QuickSort1(vector<int> &arr, int l, int r) {
    if (l >= r) return;
    int m = Partition(arr, l, r);
    QuickSort1(arr, l, m - 1);
    QuickSort1(arr, m + 1, r);
}

我改成了pivot取中间元素的情况:

int Partition(vector<int> &arr, int l, int r) {
    /*i: the number of left side of x */
    int mid = l + (r - l) / 2; // 选pivot
    int pivot = arr[mid], i = l - 1;
    for (int j = l; j <= r; ++j) {
        if (j == mid) continue;
        if (arr[j] <= pivot) swap(arr[++i], arr[j]);
    }
    swap(arr[++i], arr[mid]);
    return i; // 返回pivot插入的位置
}
// 函数主体不变

以及经典的取首元素方法:

int Partition(vector<int> &arr, int l, int r) {
    /*i: the number of left side of x */
    int x = arr[l], i = l;
    for (int j = l + 1; j <= r; ++j)
        if (arr[j] <= x) swap(arr[++i], arr[j]);
    swap(arr[i], arr[l]);
    return i; // 返回pivot插入的位置
}

代码(迭代法)

用数组模拟栈, 放入左右边界(实际的递归变量), 参考​​¹​​​,​​²​​.

/* arr --> Array to be sorted,
    l  --> Starting index,
    r  --> Ending index */
void QuickSort2(vector<int> &arr, int l, int r) {
    int stack[r - l + 1];
    // 栈顶指针(索引)
    int top = -1;

    stack[++top] = l;
    stack[++top] = r;
    // 栈空, 说明每一个子区间都被处理完了
    while (top >= 0) {
        r = stack[top--];
        l = stack[top--];

        int p = Partition(arr, l, r);
        // pivot 左边元素入栈
        if (p - 1 > l) {
            stack[++top] = l;
            stack[++top] = p - 1;
        }
        // pivot 右边元素入栈
        if (p + 1 < r) {
            stack[++top] = p + 1;
            stack[++top] = r;
        }
    }
}

相当经典, 下面我用STL给出了一种比较简洁的写法:

void QuickSort(vector<int> &arr) {
    int l{}, r = arr.size() - 1;
    stack<pair<int, int>> st;
    st.push(make_pair(l, r));
    while (!st.empty()) {
        tie(l, r) = st.top();
        st.pop();
        int p = Partition(arr, l, r);
        if (p - 1 > l) st.push(make_pair(l, p - 1));
        if (p + 1 < r) st.push(make_pair(p + 1, r));
    }
}

ref

1. ​​Iterative Quick Sort - GeeksforGeeks​​; ↩︎
2. ​​迭代的快速排序（Iterative Quick Sort）_K.Sun的博客-迭代版快速排序​​; ↩︎