一头扎进算法导论-快速排序（挖坑填数策略）

系统管理员 2022-07-14 23:29 212阅读 0赞

**定义：**它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

**过程：**  
![这里写图片描述][20161025115649020]

**用自己的话：** 以前大学的时候听说牛逼的程序员是能裸写快排，导致自己学习快速排序的时候带有一点点压力，也有点难以理解，不过当我看到这篇 [快速排序白话文][Link 1]的时候，在纸上面演示了几下，便豁然开朗，coding了一下，对作者的“挖坑填数”思想更加了解深刻，判断过程如下：

![这里写图片描述][20161025115708295]

以一个数组作为示例，取区间第一个数57为基准数，也就是第一张动图的基准线。
    初始时，i = 0;  j = 9;   X = a[i] = 57
    由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
    从j开始向前找一个比X小或等于X的数。当j=9，符合条件，将a[9]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++;  这样一个坑a[0]就被搞定了，但又形成了一个新坑a[9]，这怎么办了？简单，再找数字来填a[9]这个坑。这次从i开始向后找一个大于X的数，当i=1，符合条件，将a[1]挖出再填到上一个坑中a[9]=a[1]; j--。这样就进行了一次遍历。
    
    第二次开始i = 1;   j = 8;   X=57
    再重复上面的步骤，先从后向前找，再从前向后找。
    ....
    
    从i开始向后找，当i=5时，由于i==j退出。
    
    此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。
    
    可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

对挖坑填数进行总结  
\- 1．i =L; j = R; 将基准数挖出形成第一个坑a\[i\]。  
\- 2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a\[i\]中。  
\- 3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a\[j\]中。  
\- 4．再重复执行2，3二步，直到i==j，将基准数填入a\[i\]中。

**代码：**

public int[] quickSort(int[] a, int l, int r) {
            if (l < r) {
                int i = l, j = r, v = a[l];//i:左边开始活动坐标，j:右边开始活动坐标，v：基数，用于对比的值，一般取第一个
                while (i < j) {
       //只要左边游标和游标不重叠的话那么就继续遍历
                    //每一轮遍历的时候只进行一轮，把右边的一个比基数小的数移动到左边，把左边比基数大的数移动到右边
                    while (i < j && a[j] > v) 
                        // 找出右边比左边小的坐标
                        j--;
                    if (i < j)
                        a[i++] = a[j];//进行移动，左边坐标移动一个数
                    while (i < j && a[i] < v)
                        // 找出左边比右边大的左边
                        i++;
                    if (i < j)
                        a[j--] = a[i];//进行移动，右边坐标移动一个数
                }
                a[i] = v;//当游标重叠时填入基数
                this.quickSort(a, l, i - 1);
                this.quickSort(a, i + 1, r);
                return a;
            }
            return a;
        }

**算法复杂度：**  
![这里写图片描述][20161025142456361]

[20161025115649020]: /images/20220715/d5de53d1c5bc4d57b88c268e70eadc12.png
[Link 1]: http://blog.csdn.net/morewindows/article/details/6684558
[20161025115708295]: /images/20220715/48bbaea9db294cc3bd5e99b99694e5a4.png
[20161025142456361]: /images/20220715/294701c047bd440fb4a788d85b358a5f.png