大数据排序算法

欧阳浮乐、技术文档 超大数据排序算法

随着大数据时代的来临，计算机需要处理的数据以爆炸式的方式增长，最常见的数据排序的性能问题显得突出起来， 以目前公认的最快的快速排序法也显得不太够用, 更不用说常规的排序算法了。

一般排序算法性能消耗主要体现在 1. 遍历数据

不管哪种算法，都逃脱不了无序的反复的遍历和比较的问题， 而这个也是最占用CPU资源的原因之一

2. 移动数据或递归

比较数据后还要移动数据，会引出新的遍历问题， 虽然快速排序不需要过多移动数据，但是递归过多（快速排序，每找到一个节点，都要进行两次递归），也是性能消耗的一大主要原因。

因此，想要提高排序算法的速度， 需要从以上两方面着手，

首先减少没有必要的数据遍历、其次降低数据移动频率、再者减少匹配次数、最后是减少递归

通过以上的综合考虑，下面将使用插入排序+数据结构+二分查找的算法设计一个全新的综合排序算法。

首先，我们需要用到一个数据结构(用 javascript 语言来描述) Var node = {value: ‘’, child: null} 那么长法如下：

假设输入数组为: dataList[n]

欧阳浮乐、技术文档

1. 先创建节点sortList = {list: [], L: 0, H: 0} 2. 从dataList中拿出数据 3. 先定义 i = 0

4. 定义 val = dataList[i]， 如果i > dataList.length跳到第10步 5. 创建节点 cnode = {value: val, child: null }

6. 判断如果 cnode >= sortList.list[sortList.H]，则 sortList.list[sortList.H + 1] = cnode

7. 判断如果 cnode < sortList.list[sortList.L], 则 sortList.list[sortList.L - 1] = cnode

8. 否则 使用二分查找定位到 cnode插入的位置i，然后 fnode = sortList.list[i]

9. 如果 fnode.child == null 则 fnode.child = {list: [], L: 0, H: 0} 10. 设置 sortList = fnode.child, 然后跳转到6 11. 然后i++ 回到第4步

12. 最后，把生成的树结构进行中序遍历，把数据按顺序放回dataList中。 算法分析： 本算法最大的优点就是尽可能的减少遍历和匹配次数， 通过用二叉查找算法，把匹配次数降到最低， 一万条数据也就大约13次匹配即可， 其次去掉了在匹配过程中产生的数据位置移动的问题， 最后一次的遍历可以用推栈的遍历算法，大大提高性能， 就算使用递归遍历算法也比快速排序的递归次数少。

源码如下：

欧阳浮乐、技术文档

/** * 大数据排序对象. */ function bigSortArray() { this.compareTimes = 0 }

bigSortArray.prototype = {

/** * 大于. */ bigger: function(a, b) { },

this.compareTimes ++; if(a.value >= b.value) {

return true

} else { }

return false

/** * 小于. */ 欧阳浮乐、技术文档

smaller: function(a, b) { },

this.compareTimes++ if(a.value <= b.value) {

return true

} else { }

return false

/** * 查找位置. * @param {Object} val * @param {Object} dataList */ dvFind: function(val, dataList, L, H) { var C = parseInt((L + H)/2, 10) while(L < H - 2) { var cval = dataList[C] if(this.smaller(val, cval)) { H = C - 1 } else { L = C + 1 }