算法导论笔记:快速排序的随机化与Hoare划分

随机化快速排序:(顺便提一下,快速排序还有三数取中的优化方法,以后再填坑)

void ramdom_qsort(int *base,int x,int y) //x y数组下标
{
    if(x>=y)
        return;
    int ramdom_num=x+rand()%(y-x+1);
    int data=base[ramdom_num];
    base[ramdom_num]=base[x];
    base[x]=data;
    int i=x,j=y;
    int temp=base[x]; //temp储存基准数
    while(i<j)
    {
        while(base[j]>=temp&&i<j)
            j--;
        while(base[i]<=temp&&i<j)
            i++;
        if(i<j)
        {
            int exc=base[i];
            base[i]=base[j];
            base[j]=exc;
        }
    }
    base[x]=base[i];
    base[i]=temp;
    ramdom_qsort(base,x,i-1);
    ramdom_qsort(base,i+1,y);
}

Hoare划分:
快速排序的划分过程最早由C.R.Hoare设计,伪代码如下:

HOARE-PARTITION(A,p,r)
x=A[p]
i=p-1
j=r+1
while TRUE
    repeat
        j=j-1
    until A[j]<=x
    repeat
        i=i+1
    until A[i]>=x
    if i < j
        exchange A[i] with A[j]
    else
        return j

只把数组划分为两部分

发表评论

This site uses Akismet to reduce spam. Learn how your comment data is processed.