选择排序和快速排序

  • A+

阳光明媚的一天,狄霸哥有点儿想出去走走,毕竟一连7天7夜躲在自己造的豪华大别墅里面。要不是外面的太阳明媚无比,咕咕咕,好吧,要不是肚子饿了,没有存粮了,我才不出去呢?豪华大别墅爽到爆炸啊!

狄霸哥走在街道上,看着街上的美食框框的流口水,他走进了一家豪华的大旅馆,吆喝小二过来,豪气对问小二这里有什么好吃的。小二说:口水鸡,黄金猪蹄,麻婆豆腐.....!狄霸哥:我不知到哪个好吃的,这样吧,简单一点,全部都给我上一份吧!我这人做事就喜欢简单!小二:好嘞!这位客官。

吧唧吧唧,吃得走不动的狄霸哥实在是吃不下了,准备买单的时候,呃,没有带钱。但是狄霸哥一点都不慌,利用程序之力绘制出大量的金币,叫小二过来买单,摔出大量的金币,亮瞎了小二的眼睛。看着小二一脸懵逼,狄霸哥洋洋得意。突然,小二:老板,这里有人用假币。棒棒棒,来了一群人,把狄霸哥围了起来,这下狄霸哥蒙蔽了,恨自己没学到家啊!

善良的老板没有用武力解决问题,而是甩出了一大本记账本,里面有所有客户的消费累计,但是没有排序好,要狄霸哥将这个由低到高的排序一下。仁慈的老板说了也就10W个客户罢了。苦逼的狄霸哥一脸惆怅,突然他想到了选择排序。

 

选择排序

选择排序,通过对比每一个元素来选择一个合适的数据来放置在合适的位置上。一个很简单的排序算法。

在SortChoice函数中,有一个嵌套的循环,其中内层循环是从i+1开始的,i表示的是要对比的元素,i+1开始,表示只对比后面的元素,因为前面的已经比较过了

例如:5 1 3 9,一、首先比较 5 和 1,发现1小,所以交换,变为 1 5 3 9。二、再比较1 和 3,比较1 和 9,都比1大,不用交换,变为:1 5 3 9,此时你可以发现1这个元素已经和所有的元素都对比过了,所以下轮循环就没必要再和前面元素对比了。三、进行对比 5 和 3 ,3小,交换,变为:1 3 5 9。四、继续对比3和9,5和9,好了排序好了

选择排序的层层对比数是递减的,由n-1递减到1,所以执行时间为 (n-1+1)* n/2 = O(n^2)。哒哒哒,狄霸哥等了几十秒了,所有用户的数据才排序好,不耐烦的狄霸哥很是嫌弃,想要更快的解决办法。突然狄霸哥想到了快速排序。

 

快速排序

快速排序是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

主要思想就是每个大块都分成分成3块,直到不能分为止,数组只有一个元素或者没有,其中一块就是中间那块(参考值),把比参考值小的放在左边,大的放在右边,然后继续对左边的也这样做,右边的也这样做,最后分成了n块,直到每一块都是排好序的(只有一个元素或则没有,当然是排好序的了),而且都是通过参考值来排好序的,所以合并起来,就排好了

例如:5 1 3 9,随机参考值为5,分为3块:1 3,5,9。再对左右边执行分块,右边只有一个元素,所以直接返回,左边为:1 3,随机参考数为:1,3比1大所以放在右边,左边为空,此时3块为:null,1,3。再对左右边进行分割,左边为空,右边只有一个,所以直接返回。不能再分割了,进行合并操作,从栈顶开始,null,1,3合并为:1 3。再进行1 3,5,9合并,最总得到:1 3 5 9

快速排序的运行时间为O(nlog(n)),运气不好的话,其实也是O(n^2)。这次狄霸哥很是满意,几百毫秒不到一秒钟就完成排序了。这里采用了集合来管理元素分组,这样也比较明确快速排序的思想。可能是这拖慢了速度,不然其实几十毫秒就能完成。可以去我的笔记那里看不用List的办法。

一般来说,数据库等代码等的排序都是使用的快速排序算法,快速排序算法的优势在数据量越来越大的时候具有更显著的效果,而选择排序只适合在数据量小的情况下使用。

狄霸哥拿着已经排好序的账本,甩到了旅馆老板的脸上。旅馆老板一脸懵逼的看着已经排好序的账本,打呼一声:大神!在众多诧异的眼光下,狄霸哥潇洒的走出了旅馆门口,这样就吃了个霸王餐,真是爽!

  • 我的微信
  • 扫一扫加我微信
  • weinxin
  • 微信我的
  • 我微信扫一扫加
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: