【数据结构】大量数据(20万)的快速排序的递归与非递归算法、三数取中思想

前端之家收集整理的这篇文章主要介绍了【数据结构】大量数据(20万)的快速排序的递归与非递归算法、三数取中思想前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

快速排序的挖坑法与prev、cur法,我们在上一篇博客的第6个排序中讲的非常详细,http://www.jb51.cc/article/p-bmmuzqrp-bkg.html【数据结构】常用排序算法(包括:选择排序,堆排序,冒泡排序,选择排序,快速排序,归并排序)

有兴趣的话,相信聪明的你,一看就会秒懂快速排序的思想。


下面,我们将快速排序优化:

1、三数取中来优化快速排序


优化原因:


快速排序的擦差不多每次将序列一分为二,时间复杂度是O(n*lgn).

wKiom1c-ku6jIeVzAAAhXifwo6A279.png

我们思考,快速排序的时间复杂度是O(n*lgn),在序列乱序时,它的效率很高。但是,当序列有序或者接近有序时,效率就没有那么高了。

如果一个序列是这样的:

{10,5,1,4,5,9,6,1}

我们针对上述序列,如果要排成升序的话,我们要找一个数满足挖坑法里面的挪数据条件,或者说prev、cur法中的交换数据条件时,可能一直将序列从头遍历,找到结束或者快要结束才找到或者还没有找到,这时候相当于效率就变成了o(n^2)了。


优化方法

因此,我们想到了三数取中的思想。即序列的三个位置最左边left,最右边right,中间mid,三个数取出中间大小的数,用这个数做key.


三数取中的代码如下:


intmid(int*a,intleft,intright)
{
intmid=left-(left-right)/2;
if(a[left]<a[right])
{
if(a[left]>a[mid])
{
returna[left];
}
else
{
if(a[right]<a[mid])
{
returna[right];
}
else
{
returna[mid];
}
}
}
else
{
if(a[right]>a[mid])
{
returna[right];
}
else
{
if(a[left]<a[mid])
{
returna[left];
}
else
{
returna[mid];
}
}
}
}



2.非递归的实现


优化原因:

当一个序列较小时,每次将序列再成两半,递归处理两半的序列。

但是,当要给20万、30万这样的序列排序时,每次递归的话,无疑每次调用函数建立栈帧会很很大的系统开销,甚至会耗尽系统的空间。


优化方法:用栈stack模拟实现栈帧,每次压栈出栈---》即递归写法。


递归代码如下:


intPartSort(int*a,intright)
{
assert(a);
intcur=left;
intprev=cur-1;
intkey=mid(a,left,right);
swap(key,a[right]);

while(cur<right)
{
if(a[cur]<=a[right])
{
swap(a[++prev],a[cur]);
}
cur++;
}
swap(a[++prev],a[right]);

returnprev;
}


voidQuickSort(int*a,intright)
{
intprev=PartSort(a,right);

if(prev-1>left)
{
QuickSort(a,prev-1);
}

if(prev+1<right)
{
QuickSort(a,prev+1,right);
}

}



非递归代码如下(推荐):


//prev、cur法,也可以采用挖坑法等其他办法
intPartSort(int*a,a[right]);//将三数取中得到的数据与a[right]处交换。

while(cur<right)
{
if(a[cur]<=a[right])
{
swap(a[++prev],a[right]);

returnprev;
}


voidQuickSort_NonR(int*a,intright)
{
stack<int>s;
//左右区间压入栈中,或者此时也可以定义一个结构体,里面有左右区间,一次把左右区间都压进去
s.push(left);
s.push(right);
while(!s.empty())
{
//[left,right]
intcurRight=s.top();//压栈先压的是左区间,先进后出,取数据先取右区间
s.pop();
intcurLeft=s.top();
s.pop();
intprev=PartSort(a,curLeft,curRight);//将这个区间进行一次快速排序
if(prev-1>curLeft)
{
s.push(curLeft);//压入新分的左端序列
s.push(prev-1);
}
if(prev+1<curRight)
{
s.push(prev+1);//压入新分的右段区间
s.push(curRight);
}
}
}

猜你在找的数据结构相关文章