史上最详尽的快速排序描述【图】

古城微笑少年丶 2022-10-08 00:47 144阅读 0赞

快速排序的核心是要有一个**基准数据**temp，一般取数组的第一个位置元素。然后需要有两个指针left和right，分别指向数组的第一个和最后一个元素。

首先从right开始，比较right位置元素和基准数据。如果大于等于，则将right指针左移，比较下一位元素；如果小于，就将right指针处数据赋给left指针处（此时left指针处数据已保存进temp中），left指针+1，之后开始比较left指针处数据。

拿left位置元素和基准数据进行比较。如果小于等于，则将left指针右移，比较下一位元素；而如果大于就将left指针处数据赋给right指针处，right指针-1，之后开始比较right指针处数据…重复这个过程。

直到left和right指针相等时，说明这一次比较过程完成。此时将先前存放进temp中的基准数据赋值给当前left和right指针共同指向的位置处，即可完成这一次排序操作。

之后**递归**排序基础数据的左半部分和右半部分，递归的过程和上面讲述的过程是一样的，只不过数组范围不再是原来的全部数组了，而是现在的左半部分或右半部分。当全部的递归过程结束后，最终结果即为排好序的结果。

快速排序执行示意图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1bmxvbmc3NTA_size_16_color_FFFFFF_t_70][]

/*
     * 快速排序
     *
     * 参数说明：
     *     a -- 待排序的数组
     *     l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
     *     r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
     */
    void quick_sort(int a[], int l, int r)
    {
        if (l < r)
        {
            int i,j,x;
    
            i = l;
            j = r;
            x = a[i];
            while (i < j)
            {
                while(i < j && a[j] > x)
                    j--; // 从右向左找第一个小于x的数
                if(i < j)
                    a[i++] = a[j];
                while(i < j && a[i] < x)
                    i++; // 从左向右找第一个大于x的数
                if(i < j)
                    a[j--] = a[i];
            }
            a[i] = x;
            quick_sort(a, l, i-1); /* 递归调用，排序锚点左边部分 */
            quick_sort(a, i+1, r); /* 递归调用，排序锚点右边部分*/
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1bmxvbmc3NTA_size_16_color_FFFFFF_t_70]: /images/20221005/a9771df2abef4f36aec6af94b962ac28.png