快速排序Quick

快排——排序中的明星算法，也几乎是必须掌握的算法，这次我们来领略以下快排为何魅力如此之大。

快排主要有两种思路，分别是挖坑法和交换法，这里我们以挖坑法为例来进行介绍，交换法可以参考这篇博文。值得一提的是，这篇博文下面有许多批评的声音，质疑为何需要交换，其实是不了解快排具有两种形式，而作者采用了较为不常用的交换法，并无不妥。

挖坑法是指从数组中设定一个支点，将小于该支点的数据移到左边，而大于该支点的数据被移到右边，之后分别对支点左边和右边形成的子数组继续进行快排，采用分治法的思想。以下面的数组为例：

首先选取一个支点，一般都随机选，我们以第一个元素为例。然后设置两个哨兵位置i和j。其中i设置为0，j设置为7【一个是数组的最前面，一个是数组的最后面。】从j开始，如果j位置上的元素大于支点，那么它已经符合我们的要求，即大于支点的元素放置在支点的右边，就无需进行移动，j直接减小一位，继续进行判断。如果小于支点元素，将j位置元素放置在i的位置上。那么7>6，所以j接着会被移至6，2<6，所以将i位置上的元素设置为2。

然后换到i的方向，与j对称，如果i位置上的元素小于支点，i增加一位，反之将i位置上的元素放到j的位置上。2<6，因此i增至1。4仍然小于6，直到8>6。所以将8放置在j的位置上。

再次交换方向，发现1<6，数组变成：

同样的，有9>6和3<6，所以9会被放在位置5，而3被放在位置3。

当i和j已经相等时，将支点放在中心的位置，即

此时，支点左边都是小于6的元素，右边都是大于6的元素。然后对于左边的子数组{2,4,1,3}和右边的子数组{9,8,7}进行同样的操作。根据递归继序进行排序。

时间复杂度:快排几乎是最快的排序算法之一，时间复杂度为O(nlogn)

代码：

    static void quick(int []a, int i, int j)

    {

        int k = i;

        int m = i;

        int l = j;

        int pivot = a[i];

        while (j > i)

        {

            while (a[j] > pivot && j != i) {

                j--;

            }

            if (i != j)

                a[i] = a[j];

            else {

                a[j] = pivot;

                k = j;

                break;

            }

            while(a[i] < pivot && j != i)

                i++;

            if (i != j)

                a[j] = a[i];

            else {

                a[i] = pivot;

                k = i;

            }

        }

　　　　for (int m:a)
　　　　　　System.out.print(m+" ");
　　　　System.out,println();

        if(k >m && k < l) {

            quick(a, m, k - 1);

            quick(a, k + 1, l);

        }

    }

    public static void main(String []args)

    {

       int [] a = {6,4,8,9,3,1,2,7};

        quick(a,0,a.length - 1);

}

结果：

         //第一趟排序后，小于6的元素都在左边，大于6的元素都在右边

         //对{2,4,1,3}快排之后，以2为支点

         //对{1}进行快排，i==j直接结束

         //对{4,3}进行排序，直接交换

         //对{9,8,7}进行快排

巴特西

快速排序Quick_Sort

最新文章

热门文章