自创的分段排序算法-链表排序算法排序算法

首先说明,这个并不是常用的排序算法,也不是经典的排序算法,只不过这几天看数据结构,突然想自己实现一个排序算法,这里记录下我自创的排序算法-链表排序算法,需要说明的是自创的排序算法的性能及空间优势比起大家津津乐道的快速排序,选择排序没法比.我说过了,这里只是记录下这种思想.还是有很大的优化空间的.
算法思想:
1.首先找出待排序元素中的最大值与最小值,确定排序元素的下限与上限,然后根据这个差值以及排序元素个数,进行合适的分段比较,遍历元素将元素放到合适的区间段中.
2.在每个区间段中再次比较找出最小值与最大值,,在按步骤1分段,一次次的缩小比较区间段,最后区间段的长度小于等于3(区间段元素为3时就没必要再比了,最小值,中间值,最大值)
3.在首次分段比较时,每段除了找出最小值与最大值,还要与每段中的元素进行比较找出相等值,找出相等时就用捅来保存在一起(你可以理解为链表)
4.最后将每小段串联起来就成了有序的链表了
总结下:
(1).段分的细,元素比较的次数就少了,而且随着越分越细,比较的次数也会越来越少
(2).第一次分段内部比较时,会将相等的元素组成一个链表,这个链表就代表这个实体,后面就不需要在比较相等元素,这样会移除同值元素的比较问题
【自创的分段排序算法-链表排序算法】总得来说,这个比较算法的思想就是筛斗筛豆子,最上面的豆子先进行个大概的筛选,下面的豆子在进行细筛,筛到最后在串联起来就变得有序,算法的实现肯定要用到递归这是跑不了的.
具体的实现代码,以下是这种排序算法的实现代码:

public class LinkSortTest {public static void main(String[] args) { int[] arr = { 643, 222, 714, 190, 929, 541, 51, 21, 527, 458, 305, 96, 436, 123, 734, 889, 848, 640, 976, 707, 462, 834, 177, 276, 921, 221, 684, 293, 147, 875, 363, 712, 536, 198, 526, 989, 746, 313, 405, 625, 6, 403, 815, 211, 243, 50, 571, 884, 115, 240, 171, 211, 657, 996, 41, 594, 746, 16, 402, 432, 17, 251, 87, 716, 827, 282, 346, 659, 817, 463, 269, 462, 419, 494, 6, 187, 833, 16, 462, 141, 29, 350, 817, 955, 412, 532, 201, 203, 284, 551, 579, 745, 40, 612, 955, 712, 614, 439, 290, 579 }; print(linkedSort(arr)); }public static IntEle linkedSort(int[] arr) { Link link = new Link(); for (int i = 0; i < arr.length; i++) link.add(new IntEle(arr[i])); /* * 思路: * 1.第一轮去重 * 1.第二轮只找最小值和最大值 */ linkedSort(link, true); link.getMin().left = null; return link.getMin(); }public static void linkedSort(Link groupLink, boolean isRepeat) { int length = groupLink.getLength(); if (length <= 3) return; // 去重 int[] groups = group(groupLink); int groupSize = groups == null ? 1 : groups.length + 1; Link[] linkArr = new Link[groupSize]; for (int i = 0; i < groupSize; i++) linkArr[i] = new Link(); int size = length - 2; IntEle next = groupLink.getMin(); next = next.lastEle == null ? next.right : next.lastEle.right; sign: while (size > 0) { IntEle ele = next; size--; if (size > 0) next = next.lastEle == null ? next.right : next.lastEle.right; ele.clear(); if (groupSize == 1) { if (isRepeat) linkArr[0].addRepeat(ele); else linkArr[0].add(ele); continue; } // 多条件 for (int i = 0; i < groups.length; i++) { if (ele.value < groups[i]) { if (isRepeat) linkArr[i].addRepeat(ele); else linkArr[i].add(ele); continue sign; } } if (isRepeat) linkArr[groups.length].addRepeat(ele); else linkArr[groups.length].add(ele); } // 链表串联起来 IntEle finishEle = groupLink.getMin(); for (int i = 0; i < linkArr.length; i++) { if (linkArr[i].getLength() == 0) continue; linkedSort(linkArr[i], false); finishEle.append(linkArr[i].getMin()); finishEle = linkArr[i].getMax(); } finishEle.append(groupLink.getMax()); }/** * 分组筛选 * * @author 立子 * @version 日期:2020年3月5日 * @param min * @param max * @param length * @return 只有一组时返回null */ public static int[] group(Link groupLink) { int min = groupLink.getMin().value; int max = groupLink.getMax().value; int length = groupLink.getLength(); int c = max - min - 1; /* * 总差值c = max - min - 1 * (1).总差值C = 分组数 * 每组差值 * (1).比较元素总个数length = 分组数 * 每组个数 * (1).每组差值 >= 3(找出最大值,最小值,总差值是3,能不有序吗) * (1).每组个数 >= 3(这个也不用说了,最大值,最小值,中间值,这也肯定有序) * 每组差值 = 每组个数 * c / length >= 3 * 每组差值 >= 3c/length * 每组个数 >= 3*length/c * * 可以得到一个范围值,分组g有以下关系式 * 1 =< g <= Math.min(C/3,S/3) * g = (1 + Math.min(C,S) / 3) / 2 */ int groups = (1 + Math.min(c, length) / 3) / 2; if (groups <= 1) return null; int[] groupArr = new int[groups - 1]; int step = c / groups; groupArr[0] = min + 1 + step; for (int i = 1; i < groups - 1; i++) groupArr[i] = groupArr[i - 1] + step; return groupArr; }/** * 输出链表 * * @author 立子 * @version 日期:2020年3月5日 * @param start */ public static void print(IntEle start) { if (start == null) return; IntEle next = start; while (next != null) { if (next.left == null) System.out.print("[" + next.value); else System.out.print(", " + next.value); next = next.right; } System.out.print("]"); System.out.println(); }}class Link {private IntEle min; private IntEle max; private int length; public Link() { length = 0; }public void add(IntEle ele) { if (min == null) { min = ele; max = ele; length++; return; } if (min.value =https://www.it610.com/article/= ele.value) { ele.insertFirstRightAfter(min); return; } if (max.value == ele.value) { ele.insertFirstRightAfter(max); return; } length++; if (ele.value < min.value) { ele.append(min); min = ele; return; } else if (ele.value> max.value) { max.append(ele); max = ele; return; } ele.insertBefore(max); return; }public void addRepeat(IntEle ele) { if (min == null) { min = ele; max = ele; length++; return; } if (min.value =https://www.it610.com/article/= ele.value) { ele.insertFirstRightAfter(min); return; } if (max.value == ele.value) { ele.insertFirstRightAfter(max); return; } if (ele.value < min.value) { ele.append(min); min = ele; length++; return; } else if (ele.value> max.value) { max.append(ele); max = ele; length++; return; } if (length < 3) { ele.insertBefore(max); length++; return; } int value = https://www.it610.com/article/ele.value; int size = length - 2; IntEle next = min; do { next = next.lastEle == null ? next.right : next.lastEle.right; if (value == next.value) { ele.insertFirstRightAfter(next); return; } size--; } while (size> 0); ele.insertBefore(max); length++; }public IntEle getMin() { return min; }public IntEle getMax() { return max; }public int getLength() { return length; }}class IntEle {public int value; public IntEle left; public IntEle right; // lastEle == null 长度为1, 不为null长度 > 1 public IntEle lastEle; public IntEle(int value) { this.value = https://www.it610.com/article/value; }/** * 插入到ele之前 * * @author 立子 * @version 日期:2020年3月5日 * @param ele */ public void insertBefore(IntEle ele) { IntEle rightOpt = lastEle == null ? this : lastEle; left = ele.left; rightOpt.right = ele; ele.left = rightOpt; if (left != null) left.right = this; }/** * 插入到ele的lastRight之后 * * @author 立子 * @version 日期:2020年3月5日 * @param ele */ public void insertAfter(IntEle ele) { IntEle eleRightOpt = ele.lastEle == null ? ele : ele.lastEle; IntEle rightOpt = lastEle == null ? this : lastEle; left = eleRightOpt; rightOpt.right = eleRightOpt.right; eleRightOpt.right = this; if (rightOpt.right != null) rightOpt.right.left = rightOpt; }/** * 插入到ele的firstRight之后 * * @author 立子 * @version 日期:2020年3月5日 * @param ele */ public void insertFirstRightAfter(IntEle ele) { left = ele; IntEle rightOpt = lastEle == null ? this : lastEle; rightOpt.right = ele.right; ele.right = this; if (rightOpt.right != null) rightOpt.right.left = this; if (ele.lastEle == null) ele.lastEle = rightOpt; }/** * 附加到当前元素之后 * * @author 立子 * @version 日期:2020年3月5日 * @param ele */ public void append(IntEle ele) { IntEle rightOpt = lastEle == null ? this : lastEle; rightOpt.right = ele; ele.left = rightOpt; }/** * 移除元素链接 * * @author 立子 * @version 日期:2020年3月5日 */ public void remove() { IntEle rightOpt = lastEle == null ? this : lastEle; if (left != null) left.right = rightOpt.right; if (rightOpt.right != null) rightOpt.right.left = left; left = null; rightOpt.right = null; }public void clear() { IntEle rightOpt = lastEle == null ? this : lastEle; left = null; rightOpt.right = null; }}

下面是这种实现算法的结构图

文章图片

这样可直接将多个相等元素当成一个来用,缩短比较元素个数,在加上分段比较,理论上比较次数将大大减小,元素比较个数少了,比较差值也会缩小,但缩小貌似该分组仍然是要分的,因为相等元素在第一轮分组中就已经完成了,后面就是不重复的值.
这里再说下组分段的范围: 1<= 分组数 <= Math.min(C,S) / 3,其中C是当前段最大值与最小值的差值 - 1,即max - min - 1,为什么要减1呢,因为最大值不在参与比较.S是当前段的水平表的元素个数,就像上面结构图所示,相等元素按一个算.
这个范围是怎么来的呢,上面贴出的代码里面实际上已经写了注释,这里复述下:
(1). 总差值 = 分组数 x 每组差值
(2).元素长度 = 分组数 x 每组个数
(3).每组个数 >= 3 (这个说过了,当比较元素个数为3时,找出最大值和最小值,中间的必定介于其中,即比较元素个数为3时这一轮比较必定有序)
(4).每组差值 >= 3 (总差值为3时,这三个数必定是连续的值,最大值最小值一出来,必定有序)
利用上面给出的4个条件,可以得到 g <= Math.min(C,S) / 3,再加上分组至少一组,就得出这么个范围,在算法实现上假设元素是均匀分布的,那么取个中间值: (1 + Math,min(C,S)/3 ) / 2
这是这个算法的思想和实现原理,尽管实测与快速排序的算法没法比,甚至都比不上冒泡排序,但重在思想上,而且在实现上我是先实现而未优化.这个算法的实现绝对是有优化空间的.实现这个算法是挺费脑子的,主要是链表的代码实现,真的是很头痛,一不小心就死循环了,链的不对,输出的时候来回链回到以前的元素,就死循环了,问题很不容易找,这里贴出来,留着以后有时间在找吧.
其实在实现这个算法的时候就知道肯定没法与经典的排序算法比,虽然理论上比较的次数应该比经典算法要少很多,但是链表元素的操作也是问题,而且内部又有那么多的判断,所以性能上真的没法和经典算法相比.因此在思想上这应该是最优的,但实现上又需要这个筛框,精力都搞到这个筛框上了.所以写这篇博客想着有没有优化筛框的可能性.
最后在说个小插曲,在刚实现这个算法的时候与那些经典算法比较性能,大概是1千万的元素进行比较,由于粗心,比较元素有1千万个,但实际有999万9千元素都是0,用这个算法测的时候是新乐观最优的,快速排序都崩溃掉了,我记得是21毫秒,真的是老激动了,仔细想想是不对的,即便性能不错,TM的1千万的元素比较怎么也不可能是21毫秒呀,仔细检查发现复制了999万9千个0,实际上比较了1001个元素,不过这也说明在包含相同值的比较上,这个算法的优势非常大.下面贴一下实际的测试截图