优雅的快排之分治与递归思想,透彻理解快排

优雅的快排之分治与递归思想,透彻理解快排

引用

CSDN

1.

https://blog.csdn.net/2402_82917618/article/details/139533474

快速排序是一种高效的排序算法，由英国计算机科学家东尼·霍尔提出。它通过分治和递归的思想，将一个数组分成两个子区间，再对子区间进行排序，最终实现整个数组的排序。本文将从基本概念、实现步骤到具体代码，深入浅出地讲解快速排序算法。

如上图所示，快速排序的核心思想是将一个数组分成两个子区间。具体步骤如下：

1. 选择一个基准元素（通常是数组的第一个元素）
2. 通过两个指针（i和j）从数组的两端向中间扫描
3. i指针从左向右移动，直到找到一个大于等于基准元素的值
4. j指针从右向左移动，直到找到一个小于等于基准元素的值
5. 如果i和j没有相遇，则交换它们所指向的元素
6. 重复上述过程，直到i和j相遇或交错
7. 此时，数组就被分成了两个子区间：左边的元素都小于等于基准，右边的元素都大于等于基准

这个过程可以用下图表示：

红线表示第一次分区，蓝线表示对子区间的分区。每次分区后，都会产生两个子区间，这两个子区间都是有序的（将子区间看作一个整体）。为了对整个数组进行排序，只需要对这两个子区间分别进行排序。这就是分治思想的具体体现。

接下来，我们用C语言实现快速排序算法：

#include <stdio.h>

int n, q[100000];

void quick_sort(int q[], int l, int r) {
    if (l == r) return; // 递归结束条件：子区间只有一个元素

    int x = q[l], i = l - 1, j = r + 1; // x是分区的基准
    while (i < j) {
        while (q[++i] < x);
        while (q[--j] > x);
        if (i < j) {
            int t = q[i];
            q[i] = q[j];
            q[j] = t;
        }
    }
    // 递归调用
    quick_sort(q, l, j); // 对左区间
    quick_sort(q, j + 1, r); // 对右区间
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", q + i);
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", q[i]);
    return 0;
}

这段代码实现了快速排序算法的核心逻辑。quick_sort函数接受数组、左边界和右边界作为参数。在函数内部，首先检查递归结束条件（子区间只有一个元素）。然后，通过两个指针（i和j）进行分区操作，并在必要时交换元素。最后，递归调用quick_sort函数对左右两个子区间进行排序。

通过本文的讲解，相信读者已经对快速排序算法有了深入的理解。快速排序以其高效的性能和简洁的实现，成为了计算机科学中最重要的排序算法之一。