DNA排序算法--图文版

DNA排序算法，简单来说就是通过DNA工作原理实现排序功能的算法。本篇文章从整合排序算法的角度切入这个算法。
首先，收集现有的经典排序算法，它们分别有：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等。
然后，通过某种方式对它们进行归类，从搜索的结果来看，可将它们分成基于比较的排序算法和基于分配的排序算法两大类，分类如下：

再就是找到一个视角，描绘这些算法的共同之处，为下一步的整合铺路。这个视角如同动画的关键帧，起到以点带面的作用。在这里，它就是反映算法分类的关键性符号，基于比较的排序算法为"<"或“>” ，基于分配的排序算法为“=”，图示如下：

最后通过DNA这个构件将这两大类算法整合在一起，产生一个新的算法。这个新的算法（DNA排序算法），运用了比较，也运用了分配，集大成者，在均衡排序效率和消耗资源上更加游刃有余。
那么，具体如何整合的呢？
首先，要弄明白排序是什么。对它的理解方式决定了算法的实现原理，在这里，排序就是将数据连接的能力从无数可能性降为唯一性的过程，图示如下：

然后，依照DNA的结构，给出一个整体的排序思路。这个思路就是将数据限定在两条数组（两条链）上，按照某种规则不停地上窜下跳，当它最终停止跳动的时候，数据成为一个有序数列。

再就是深入了解DNA运作的每一个细节，从中挖掘出与排序相关的DNA运作细节，找到实现排序的方法。从基于比较的排序算法来看，数据就是不断被基准点分隔，使数据可连接性变差，最终变成唯一性，从而实现排序;从基于分配的排序算法来看，数据不断地被分组，经过多轮分组，最终无组可分，从而实现排序。这两类排序算法，本质还是通过隔断数据的连通性来实现排序，不同之处在于它们的关注点，一个关注分隔点，一个关注数据本体。在排序过程中，一个看到分隔点不断增加，一个看到数据被不断隔断，它们都是对同一个排序过程的描述：

那么，从DNA运作的角度来看，DNA的复制过程就和数据排序过程对应上了：

最后，将数据排序的每一个细节对应上DNA的复制过程就可以得到DNA排序算法啦。
下面就让我详细说说这个对应过程。
1，将数据分成a链和b链，向DNA的双链结构靠拢：

2，数据的处理是基于CPU 或者GPU 的，从CPU的角度来看，排序大概就是对数据分层，然后一层一层历遍的过程：

3，前面两步结合起来看就是一个将数据不断拆分和重组的过程，结合DNA，图示如下：

4，单从数据的角度看，前面的步骤，把数据里的每个数都分成了好几层，而且每一层的每一组都只能拆分出两组，这两点结合起来，正好与二进制数据特点相吻合，这也就说明了这个算法可以直接利用内存里的二进制格式数据，不需要数据转换步骤：

5，通过上面几个步骤，一个排序的流程就形成了，先历遍数据得到某个数据层的”0“”1“状态值，然后将状态值为”0“的数据依次放入a链，状态值为”1“的数据依次放入b链,最后将a链与b链连接得到排序过的数据，重复上面的步骤，历遍所有数据层，数据就排好序了，图示如下：

6，有了流程图，就可以进行编程啦。不过，看到排序流程的第一步就蒙B了，先历遍数据得到某个数据层的”0“”1“状态值，这就需要一个数据长度的内存来存放这些状态值，内存开销太大了。这就需要优化排序流程以适合算法的设计要求。这里优化的方法就是用变量代表状态值，具体优化如下：

7，接下来的步骤，马上就遇到之前欠考虑的问题，a链和b链分成多组之后 ，在下个数据层里，不知道它们的对应关系了，这就是需要在数据链分成a链和b链的时候，把它们的数据坐标信息保存起来，那么，在DNA运作里， “将数据坐标信息保存起来”这个动作代表的是什么呢？ 如果对应不上，那么这个算法也就不能称之为DNA排序算法了，感觉命悬一线，所有努力都要灰飞烟灭了。不过还好，搜索DNA找不到答案，搜索RNA就找到答案了，RNA是DNA的信使，哈~

关于RNA的信息很多，选取我们需要的即可：”RNA是遗传信息的中间载体,携带着三联体密码子“，从编程的角度来翻译这句话，意思就是带有三个属性的对象，也就是说，用三个属性记录一个数据组的坐标信息，让下一个数据层可以继续排序。那么，这三个属性分别就是数据组始点，数据组大小和所要排序的数据层了。有了这三个信息，数据的排序就可以顺利地进行下去了，而且数据的历遍方式发生了很大的变化，之前以数据层为单位，要历遍所有数据才能排序下一个数据层;现在以数据组为单位，历遍一个数据组就可以通过三联体对象中的一个对象从任何一个数据组开始。从工作的角度来看，三联体对象就是一个个的工作任务，而且是没有先后顺序的任务。任务没有先后顺序，分配起来就非常的方便。从编程的角度来说，这个算法就非常适合多线程运行，从而它会有很好的排序效率。

8，经过第7点的调整，DNA排序算法已经可以排序啦，现在就是到处看看哪里还需要调优的，把它调到最优。 第一，数据的数值可能会集中在某个区域，从数据层的角度来看，会有很多全是“0”的层，历遍它是做无用功，调优的方式就是利用比较的方式找出数据的最大值，然后，从这个值的最高层开始历遍数据层。第二，数据可能集中在某个区域，从而有很多是重复的。一遍一遍历遍这些相同的数也是做无用功，所以改进的方法是申请一个变量，在历遍数据层的时候也顺便比较一下这些数是否相同，只要有一个不相同就将变量值设为false,在生成三联体对象就可以根据这个值确定是否生成三联体对象，不过如果数据稀疏，这样做反而适得其反。所以还需要做进一步的改善，改善的方向就是写一个方法，在排序前判断一下当前数据是稀疏还是稠密。第三，当数据组只剩下两个数的时候就再不需要生成三联体对象，直接用比较的方式，将它们排好即可。大概就是这些了吧，这些调整，是否和DNA对应得上，这就不清楚了，不过也无伤大雅就是啦~

经过上面8步，一个完整的DNA排序算法就做出来了。