算法设计与分析——快速排序

关于快速排序的思想图解和C++代码实现，请参考我之前的博客https://www.cnblogs.com/wkfvawl/p/9558002.html

 

快速排序是基于分治策略的另一种排序算法，其基本思想是，对于输入的子数组a[p:r]，按照以下3个步骤进行排序。

private static void qSort(int p,int r)
{
    if(p<r)
    {
        int q = partition(p,r);
        qSort(p,q-1);//对左半段排序
        qSort(q+1,r);//对右半段排序
    }
}

 

private static int partition(int p,int r)
{
    int i = p;
    int j = r + 1;
    Comparable x = a[p];
    //将<x的元素交换到左边区域
    //将>x的元素交换到右边区域
    while(true)
    {
        while(a[++i].compareTo(x)<0&&i<r);
        while(a[--j].compareTo(x)>0)；
        if(i>=j) break;
        MyMath.swap(a,i,j);
    }
    a[p]=a[j];
    a[j]=x;
    return j;
}

 

 

private static int randomizedPartition(int p,int r)
{
   int i=random(p,r);
   MyMath.swap(a,i,p);
   return partition(p,r);
}

private static void randomizedQSort(int p,int r)
{
    if(p<r)
    {
        int q = randomizedPartition(p,r);
        randomizedQSort(p,q-1);//对左半段排序
        randomizedQSort(q+1,r);//对右半段排序
    }
}