各位码友身为软件开发工程师,算法中的排序可谓是重重之重,那么今天小码哥就给大家带来两种交换排序,简单算法中的冒泡排序,和号称排序算法中的王者快速排序,是不是很期待呀大笑大笑,话不多说,码代码啦!!!
先给大家介绍一下什么是冒泡排序?
冒泡排序 (Bubble Sort)是一种交换排序。
它的基本思想是 : 两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。
说了这么多,还是不太懂是什么? 那么重点来啦–》
以上就是小码哥实现的冒泡排序,不得不说,这代码小码哥都不好意思交给漂亮的HR小姐姐,因为HR小姐姐要效率高的排序,很显然上述排序不能满足。那就再来个优化版的吧。
冒泡排序改好了,拿给HR小姐姐看,小姐姐说还不错,就是处理大数据是还是不够,时间复杂度为O(N2),根本不能满足,那怎么办呢,小码哥只能拿出自己的看家本领了,请出算法中的王者,快速排序,希望能讨小姐姐的欢心。
我把快排写好了,拿给HR小姐姐,小姐姐非常开心,问我还能优化吗?万一我取的枢轴是最大值或最小值呢,那这个算法不就连冒泡排序都不如了吗?为了小姐姐能更开心,快排的优化版本来啦–》
以上便是快排优化代码
快排优化思想:
1,三数取中法 : 取三个关键字先进行排序,将中间数作为枢轴,一般取左端,右端,中间三个数。
2,九数去中法 它先从这三个中数中分三次取样,每次取三个数,三个样品各取出中数,然后从这三个中数当中再取一个中数作为枢轴,这个有兴趣的码友可以自己实现哦。
3,优化不必要的交换。