《Unity3D高级编程之进阶主程》第一章,C#要点技术(五) 排序算法

年纪越大,写程序写的越多,时间越长,就越觉得算法的重要性,基础能力决定你到底能走多远。

我们不是写一两年就完事的,从毕业算起,我们可能要写20-30年的程序,这段漫长的长跑路程中,最终比的不是谁熟悉API比较多,也不是谁用插件用的有多熟练,更不是比谁更熟悉某软件,而是比谁的算法能力强,比谁对底层结构更加熟知于心,比谁能够解决的系统复杂度有多高。

===

算法能力非常重要,在程序生涯中,算法是基础能力,很多时候程序的好坏,一方面看的是写程序的经验,另一方面看的是对计算机原理的理解程度,还有一方面看的是对算法的运用到如何程度。

算法能力不仅仅是表面的算法熟知度,更是种精神高度,对所有经过自己手的程序效率负责的精神高度。某一处的算法有可能运用的很好,但如果其他地方都用烂算法,对于整体程序效率来说其实也没什么用,效率依然很烂。

在平时的编程时,做到时刻关注算法的效率是区分中、高水平的一个大的关键点。

其中排序和搜索算法最为常用。毫不夸张的说一个项目中有90%的算法都是排序和搜索算法,如果说我们把这90%的算法提高到一个很高效的程度,那么剩下的10%算法处理起来也没那么压力了。

快速排序算法

快速排序,也叫二分排序,是最最最常用,最最最好用,用的最最最多的排序算法。它的排序方式是:

1.从序列中选一个元素作为基准元素

2.把比基准元素小的元素移到基准元素的左边,把基准元素大的移到右边。

3.对分开来的二个一大一小区块进行递归再筛选,对两个区块同样进行1、2的两个步骤处理。

简单来说就是把一个区域的数字分成两半,一半比另一半大。然后继续对这两半做同样的操作。

由于这是最常用的排序方法,几乎占据50%以上的排序算法编码量,所以我们要着重优化此算法,对大批量使用的算法和程序绝对不能忽视。

优化:

1.随机选择中轴数

如果选中的数字不是中位数,而是一个比较偏左或者比较偏右的数字,那么排序的速度就会降低,比如选中的刚好是最大的或者最小的数字,左边完全没有数字可以排,而所有数字都在它的右边。

我们肯定无法准确的找到中位数,但是我们可以随机一个列表上的元素来作为基准元素。

随机是为了减小选到最大和最小值的概率,但随机也时常会选到坏的基准元素,实际上随机数并没有对排序提供多大的帮助。

2.三数取中

为了让选择的中轴数更加接近中位数,可以先选择头、中点、尾,三个数字先来次排序,把最小的放在头,中间的放在中,最大的放在尾。

每次每个区间的头中尾的排序前都做这个操作,也就是说,每次排序前,中位数都不可能是最小的,起码是区间里第2小的或者第2大的,这样选出来的中轴数靠近中位数就的概率就大了。

虽然可以把三个数扩大到M个数,但过多数字的选择就相当于多出了个一个排序算法,减慢的二分排序的效果。实际效果不如3个数字来的快。

也可以用随机选取3个数字的方式来替代做选择,但实际上随机性并没有多大的帮助,况且伪随机数的计算也是需要消耗cpu的,而常用的头,中,尾的做法是选择接近中位数的比较有效的办法。

3,小区间使用插入排序

插入排序和二分排序一样都依赖于序列的有序性,如果是反序列效率最差,反之如果是有序序列效率最大。

其中,插入排序当序列越长,效率越差,而短序列的排序效果则很好,序列长度在8左右。

在排序中,当切分的区块小于等于8的个数时,就可以采用插入排序来替代二分排序,其他时候任然采用二分切割算法。

4,缩小分割范围,与中轴数相同的合并在一起

与中轴数相同的数可以立即合并到中轴数的位置,使得后面的分割范围变得小,范围越小,排序的速度越快。

具体做法是,在二分比较中,当元素与中轴数相等时就移动到中轴数身边,移动完毕后,划分范围从中轴数变为最边上的相同元素的位置。

快速排序是最常用,使用范围最广的排序算法,铭记于心是有必要的。

其他排序算法简要

其他排序虽然使用频率没有快速排序来的多,但提供了对解决问题的思路很有帮助。

比如,桶排序,把所有的元素按一定大小范围分成N个组,对每个组进行快速排序,最终得到有序的数组,并且得到N个桶的记录,虽然第一次排序的速度不怎么样,但这N个桶的信息记录下来后对于后面的程序逻辑有非常大的帮助。比如我们需要进行模糊排序或模糊搜索,这种桶信息就会有很大帮助。

又比如,堆排序,和快速排序一样用的是二分的方式,是一种近似完全二叉树的结构,速度上虽然没有快速排序来的快,但却能快速定位某元素,排序完成后,形成的有序最大堆或最小堆数据结构在后面程序逻辑需要插入新元素,找某元素时,效率比较高。

再比如,基数排序,是针对元素的特性来实时的‘分配式排序’,利用数字的特性按个位数,十位数,百位数的性质放入0-9的桶中不用排序,几次合并后直接就是有序数组,利用元素特性排序的速度比任何其他排序方式都要快速。这就教会我们,在运用算法时,首先要从元素的特性和环境着手,找到更合适更快的算法。

基本的、常用的几种排序算法是我们需要了解的,当我们面对需要解决的难题时,我们的思路就更为广阔,算法在实际运用中并不是固定的,适合的才是最好的,我们应该随着问题环境的变化而变化,找到最佳的突破口。

感谢您的耐心阅读

Thanks for your reading

  • 版权申明

    本文为博主原创文章,未经允许不得转载:

    《Unity3D高级编程之进阶主程》第一章,C#要点技术(五) 排序算法

    Copyright attention

    Please don't reprint without authorize.

  • 微信公众号