今天水了一道排序题。学会了快排的方法。快排并不仅仅是分治,还要有随机。因为考虑到一些特殊的case可能会影响复杂度。先讲一下快排的分治思想吧。。。
在一个给定的数列中,从第一个数开始,依次往后,每当小于数列最后一个数(此数最好是由随机数产生)时,便记录下来,最后将最后一个数与刚才最后一个的后一个数进行exchange。那么一次下来。就变成了三部分,两个数列和一个数,前一部分虽是乱序,但均比某个数小。。。而后一部分则均比某一个数大。。。那么由此,就可以想到。不断的递归下去。不断的划分。到最后,就可以将原来的数列分成许多小部分。每一个部分由3个数组成。“小,中,大”,并依次排序。。。即完成了排序。。。。。
那么讨论这个快排的复杂度,因为分治的方法是多线程的。自然会比暴力解法单线程的快得多。那么在多线程的情况下,怎么达到最优呢。这里就要对应到前面提到的产生随机数。因为并不知道会得到怎么样的一个数列,如果是正序的一个庞大数列,那么如果每次都取最后一个数,则会退化到跟暴力解相同的复杂度。为防止算法退化,我们这里使用(rand() % (a-b+1))+b来得到[a,b]之间的随机数。则会尽可能的接近中间数。那么复杂度将会大大减少,。
例如,
int RAND(int A[], int p, int r)
{
int i = (rand() % (r - p)) + p;
int temp = A[i];
A[i] = A[r];
A[r] = temp;
return partition(A, p, r);
}
然后在quicksort中调用RAND而不是直接partition
另外,数列中经常会有很多重复的数,要防止这种情况下的退化,可以在判断不相等之后再进行quicksort调用,例如
while (s>0)
{
if(A[s-1]!=A[s])
{
quick(A, p, s-1);
break;
}
else s--;
}
while (q<r)
{
if(A[q+1]!=A[q])
{
quick(A, q+1, r);
break;
}
else q++;
对于测试时间
clock_t start,end;
start=clock();
end=clock();
printf("%d\n",end-start);
自己也是用这个测试过用文件读入的10W个正序数列的运行的时间。在使用随机数的情况下很快就能得出结果。但没有使用的时候等上半天甚至没有结果。所以说快排应该是=随机取数+分治思想
分享到:
相关推荐
ERP\erp浅谈ERP\erp浅谈ERP\erp浅谈ERP\erp浅谈ERP\erp浅谈ERP\erp浅谈ERP\erp浅谈
浅谈计算机病毒浅谈计算机病毒浅谈计算机病毒浅谈计算机病毒浅谈计算机病毒浅谈计算机病毒浅谈计算机病毒
Android框架浅谈
浅谈输电线路防雷接地浅谈输电线路防雷接地浅谈输电线路防雷接地浅谈输电线路防雷接地浅谈输电线路防雷接地浅谈输电线路防雷接地浅谈输电线路防雷接地浅谈输电线路防雷接地浅谈输电线路防雷接地浅谈输电线路防雷接地...
注意力机制浅谈注意力机制及其作用浅谈注意力机制及其作用浅谈注意力机制及其作用浅谈注意力机制及其作用浅谈注意力机制及其作用浅谈注意力机制及其作用浅谈注意力机制及其作用浅谈注意力机制及其作用浅谈注意力机制...
本书用浅谈的手法写深奥的知识,深入浅出地解说了快 速傅立叶变换的原理与算法,并对其具体应用作了介绍,对 推厂‘这种计算方法的应用,将起到积极的推动作用。 邓贤照先生年逾八旬,在困苦的生活条件下,夜以继....
浅谈汽车SOA架构开发和实施过程中的微服务化.pdf浅谈汽车SOA架构开发和实施过程中的微服务化.pdf浅谈汽车SOA架构开发和实施过程中的微服务化.pdf浅谈汽车SOA架构开发和实施过程中的微服务化.pdf浅谈汽车SOA架构开发...
浅谈驾驶员的健康心理知识论文.doc
浅谈数据仓库建设中的数据建模方法浅谈数据仓库建设中的数据建模方法所谓水无定势兵无常法。不同的行业有不同行业的特点因此从业务角度看其相应的数据模型是千差万别的。目前业界较为主流的是数据仓库厂商主要是IB
智能运维:浅谈持续集成( CI)、持续交付(CD) 和软件测试.pdf智能运维:浅谈持续集成( CI)、持续交付(CD) 和软件测试.pdf智能运维:浅谈持续集成( CI)、持续交付(CD) 和软件测试.pdf智能运维:浅谈持续集成( CI)、...
浅谈Java优势,关于java优势......
浅谈中职《计算机组装与维护》课程教学改革
浅谈Java中Mysql数据库的连接与操作.pdf
快捷支付浅谈:快捷支付便捷性和安全性分析
HTML+css PPT浅谈.rar
浅谈记忆化搜索.pdf
主要讲解x86架构下的cache的怎么工作原理和怎么实现等,说的很详细,水平很高的,但是要有相应的知识才能看明白,作者是王齐,
浅谈人工智能关键技术研究与应用.pdf
浅谈微信小程序.pdf浅谈微信小程序.pdf浅谈微信小程序.pdf浅谈微信小程序.pdf浅谈微信小程序.pdf浅谈微信小程序.pdf浅谈微信小程序.pdf浅谈微信小程序.pdf
浅谈文字编码和Unicode 不错,值得大家学习