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

摘要:给你一个数组,要求你对其按照从小到大的顺序进行排序. 你是怎么做的呢?英国计算机科学家东尼.霍尔在英国国家物理实验室工作的时候提出一种名为快速排序的排序算法,它可以高效地将一个数组进行快速排序.那么霍尔是怎么想到的?接下来根据从y总那里学到的以及个人的理解来介绍这个著名的排序.先简单介绍一下,快排就是对一个数组在整体上分成有序的两个子区间,这就是分治.然后,每个子区间在通过同样的方法分成有序的两个子区间,这就是递归.注意:这里所指的有序是针对区间而言的,就是将区间看作是一个整体.而区间本身未必是有序的.

这就是一个将一个数组分成两部分的一个模型图,这是一个名为q的数组,小写的L和r分别是这个数组的左右边界,小写的 i 和 j 分别是两个指针,其实就是int型变量,用来表示数组的下标,小写的x是一个int型的变量,存储左边界的数组元素数据,以作为划分区间的基准.图中的第一步是:先将i 加1指向第一个元素,如果这个元素小于x ,i 继续向中间移动,如果所指向元素>= x, 则 i 停下来.  第二步 : 去移动指针j , 先将j 减1 , 指向末尾元素 ,如果元素大于x , 则j 指针向中间继续移动,直到所指向的元素<=x,这时候判断i 与 j 是否相遇过 ,如果没有则交换所指向的数据 , i 继续向中间移动 直到所指向元素>=x , 然后j 继续向中间移动,直到所指向元素<=x, 如果i 和 j 没有相遇 ,交换数据 ,继续向中间移动 , 直到i 和 j  相遇 或者穿过 , 即i >= j . 图中显示的是相遇 , 是因为i 停下来时所指向的元素等于x, 当j 过来时也会在这里停下来 , 如果i 最终停下来所指向的元素大于x , j 就不会在这里停下来 而是继续向左移动  , 穿过i , 因为i 左边的数据都是<= x 的, j 一旦穿过i 所指向的下一个元素就是<= x , j 就会停下来 . 不管是相遇还是穿过 , 这个数组就已经分成了两个我们想要的子区间 , 左边区间的数据都是<= x 的, 右边区间的数据都是>= x 的, j 就可以作为区间的分界点 ,j 所指向的元素及其左边的元素都是<= x 的 , j 右边的元素都是>=x的 . 这样的两个子区间就是有序的(注意:将子区间看作一个整体),要想对数组q 进行排序 , 只需对这两个子区间进行排序,因为只要将每个子区间都排好序,整个数组就是有序的.  这就是分治 , 将对一个数组的排序分成对两个子区间的排序. 同理 , 将对其中任何一个子区间的排序在分成对两个更小的子区间的排序. 依次类推, 直到子区间的数组只有一个元素 , 即左边界等于右边界, 子区间就是有序的了, 就不用在分成更小的子区间了,就可以结束递归了. 注意:每个子区间都看做是一个整体,不管递归到产生多少个子区间, 这些子区间都是从小到大的有序的 ,一个子区间大于等于它左边的所有子区间,小于等于它右边的所有子区间. 所以不管哪个子区间先排好序,其他的子区间继续分成两个长度更小的子区间都不影响整体的顺序.  下图的红线是第一次分区 , 蓝线是对子区间的分区  以上就是根据从Y总那里学的以及自己的一点理解. 接下来看代码吧, 我是用c 写的(模仿的y总)

#include <stdio.h>

int n, q[100000];

void quick_sort (int q[], int l, int r)//l 是数组的左边界 , r 是有边界
{
    if (l == r) return ;//递归结束条件,即子区间只有一个元素肯定是有序的
//下面的代码是对数组进行分区 , 并递归调用,对子区间进行分区或者return
    int x = q[l], i = l - 1, j = r + 1; //x是分区的基准,因为y总选择了左边界,我这里也选择了左边界的元素作为基准, i 和 j 分别指向数组的两边, 这就要先移动指针在判断元素的大小,为什么这样做呢?是因为交换数据后一定要先移动指针再判断元素大小,为了防止交换数据时元素等于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;
}