快速排序Quick_Sort

时间:2024-01-20 22:50:24

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

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

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

快速排序Quick_Sort

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

快速排序Quick_Sort

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

快速排序Quick_Sort

再次交换方向,发现1<6,数组变成:

快速排序Quick_Sort

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

快速排序Quick_Sort

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

快速排序Quick_Sort

此时,支点左边都是小于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}进行快排