浏览 8352 次
锁定老帖子 主题:用JAVA实现的9种排序算法(二)
精华帖 (0) :: 良好帖 (4) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2009-11-09
最后修改:2009-11-09
5.Shell排序 package com.javasort.shellsorter; /** * Shell排序可以理解为插入排序的变种,它充分利用了插入排序的两个特点: 1)当数据规模小的时候非常高效 2)当给定数据已经有序时的时间代价为O(N) 所以,Shell排序每次把数据分成若个小块,来使用插入排序,而且之后在这若个小块排好序的情况下把它们合成大一点的小块,继续使用插入排序,不停的合并小块,知道最后成一个块,并使用插入排序。 这里每次分成若干小块是通过“增量” 来控制的,开始时增量交大,接近N/2,从而使得分割出来接近N/2个小块,逐渐的减小“增量“最终到减小到1。 一直较好的增量序列是2^k-1,2^(k-1)-1,.....7,3,1,这样可使Shell排序时间复杂度达到O(N^1.5) 所以我在实现Shell排序的时候采用该增量序列 */ import com.javasort.Sorter; /** * * @author Daniel Cheng * * @param <E> */ public class ShellSorter<E extends Comparable<E>> extends Sorter<E> { @Override public void sort(E[] array, int from, int len) { //1.calculate(计算) first delta value int value=1; while((value+1)*2<len){ value=(value+1)*2-1; } //2.小块是通过“增量” 来控制的,开始时增量较大,接近N/2,从而使得分割出来接近N/2个小块,逐渐的减小“增量“最终到减小到1。 for(int delta=value;delta>=1;delta=(delta+1)/2-1){ for(int i=0;i<delta;i++){ modify_insert_sort(array,from+i,len-i,delta); } } } private final void modify_insert_sort(E[] array, int from, int len, int delta) { if(len<=1) return; E tmp=null; for(int i=from+delta;i<from+len;i+=delta){ tmp=array[i]; int j=i; for(;j>from;j-=delta){ if(tmp.compareTo(array[j-delta])<0){ array[j]=array[j-delta]; } else break; } array[j]=tmp; } } } package com.javasort.shellsorter; import com.javasort.Sorter; public class ShellSorterTest { public static void main(String[] args) { Comparable[] array={5,1,13,2,17,9,7,4,0}; Sorter shellSorter=new ShellSorter(); shellSorter.sort(array); shellSorter.printResult(array); } } 6.堆排序 package com.javasort.heapsorter; /** * 堆排序:堆是一种完全二叉树,一般使用数组来实现。 * 堆主要有两种核心操作, * 1)从指定节点向上调整(shiftUp) * 2)从指定节点向下调整(shiftDown) * 建堆,以及删除堆定节点使用shiftDwon,而在插入节点时一般结合两种操作一起使用。 * 堆排序借助最大值堆来实现,第i次从堆顶移除最大值放到数组的倒数第i个位置, * 然后shiftDown到倒数第i+1个位置,一共执行N次调整,即完成排序。 * 显然,堆排序也是一种选择性的排序,每次选择第i大的元素。 */ import com.javasort.Sorter; /** * * @author Daniel Cheng * */ public class HeapSorter<E extends Comparable<E>> extends Sorter<E> { @Override public void sort(E[] array, int from, int len) { build_heap(array,from,len); for(int i=0;i<len;i++){ //第i次从堆顶移除最大值放到数组的倒数第i个位置, swap(array, from, from+len-1-i); //一直shiftDown(从0开始)到倒数第i+1个位置,一共执行N次调整 shift_down(array, from, len-1-i, 0); } } private final void build_heap(E[] array, int from, int len) { //我们从(len- 1)/ 2开始,因为分支节点+1=叶子节点,而所有的叶子节点已经是一个堆 int pos=(len-1)/2; for(int i=pos;i>=0;i--){ shift_down(array,from,len,i); } } private final void shift_down(E[] array, int from, int len, int pos) { E tmp=array[from+pos]; int index=pos*2+1;//用左孩子结点 while(index<len)//直到没有孩子结点 { if(index+1<len&&array[from+index].compareTo(array[from+index+1])<0)//右孩子结点是较大的 { index+=1;//切换到右孩子结点 } if(tmp.compareTo(array[from+index])<0){ array[from+pos]=array[from+index]; pos=index; index=pos*2+1; } else{ break; } } array[from+pos]=tmp; } } /** * */ package com.javasort.heapsorter; import com.javasort.Sorter; /** * @author Daniel Cheng * */ public class HeapSorterTest { public static void main(String[] args) { Comparable[] array = { 5, 1, 13, 2, 17, 9, 7, 4, 0 }; Sorter heapSorter=new HeapSorter(); heapSorter.sort(array); heapSorter.printResult(array); } } 7.桶式排序 /** * 桶式排序: * 桶式排序不再是基于比较的了,它和基数排序同属于分配类的排序, * 这类排序的特点是事先要知道待排 序列的一些特征。 * 桶式排序事先要知道待排 序列在一个范围内,而且这个范围应该不是很大的。 * 比如知道待排序列在[0,M)内,那么可以分配M个桶,第I个桶记录I的出现情况, * 最后根据每个桶收到的位置信息把数据输出成有序的形式。 * 这里我们用两个临时性数组,一个用于记录位置信息,一个用于方便输出数据成有序方式, * 另外我们假设数据落在0到MAX,如果所给数据不是从0开始,你可以把每个数减去最小的数。 * */ package com.javasort.bucketsorter; /** * @author Daniel Cheng * */ public class BucketSorter { public void sort(int[] keys,int from,int len,int max) { int[] temp=new int[len]; int[] count=new int[max]; for(int i=0;i<len;i++) { count[keys[from+i]]++; } //calculate position info for(int i=1;i<max;i++) { count[i]=count[i]+count[i-1];//这意味着有多少数目小于或等于i,因此它也是position+ 1 } System.arraycopy(keys, from, temp, 0, len); for(int k=len-1;k>=0;k--)//从最末到开头保持稳定性 { keys[--count[temp[k]]]=temp[k];// position +1 =count } } /** * @param args */ public static void main(String[] args) { int[] a={1,4,8,3,2,9,5,0,7,6,9,10,9,13,14,15,11,12,17,16}; BucketSorter bucketSorter=new BucketSorter(); bucketSorter.sort(a,0,a.length,20);//actually is 18, but 20 will also work for(int i=0;i<a.length;i++) { System.out.print(a[i]+","); } } } 8.基数排序 /** * 基数排序:基数排序可以说是扩展了的桶式排序, * 比如当待排序列在一个很大的范围内,比如0到999999内,那么用桶式排序是很浪费空间的。 * 而基数排序把每个排序码拆成由d个排序码,比如任何一个6位数(不满六位前面补0)拆成6个排序码, * 分别是个位的,十位的,百位的。。。。 * 排序时,分6次完成,每次按第i个排序码来排。 * 一般有两种方式: * 1) 高位优先(MSD): 从高位到低位依次对序列排序 * 2) 低位优先(LSD): 从低位到高位依次对序列排序 * 计算机一般采用低位优先法(人类一般使用高位优先),但是采用低位优先时要确保排序算法的稳定性。 * 基数排序借助桶式排序,每次按第N位排序时,采用桶式排序。 * 对于如何安排每次落入同一个桶中的数据有两种安排方法: * 1)顺序存储:每次使用桶式排序,放入r个桶中,相同时增加计数。 * 2)链式存储:每个桶通过一个静态队列来跟踪。 */ package com.javasort.radixsorter; import java.util.Arrays; /** * @author Daniel Cheng * */ public class RadixSorter { public static boolean USE_LINK=true; /** * * @param keys * @param from * @param len * @param radix key's radix * @param d how many sub keys should one key divide to */ public void sort(int[] keys,int from ,int len,int radix, int d) { if(USE_LINK) { link_radix_sort(keys,from,len,radix,d); } else { array_radix_sort(keys,from,len,radix,d); } } private final void array_radix_sort(int[] keys, int from, int len, int radix, int d) { int[] temporary=new int[len]; int[] count=new int[radix]; int R=1; for(int i=0;i<d;i++) { System.arraycopy(keys, from, temporary, 0, len); Arrays.fill(count, 0); for(int k=0;k<len;k++) { int subkey=(temporary[k]/R)%radix; count[subkey]++; } for(int j=1;j<radix;j++) { count[j]=count[j]+count[j-1]; } for(int m=len-1;m>=0;m--) { int subkey=(temporary[m]/R)%radix; --count[subkey]; keys[from+count[subkey]]=temporary[m]; } R*=radix; } } private static class LinkQueue { int head=-1; int tail=-1; } private final void link_radix_sort(int[] keys, int from, int len, int radix, int d) { int[] nexts=new int[len]; LinkQueue[] queues=new LinkQueue[radix]; for(int i=0;i<radix;i++) { queues[i]=new LinkQueue(); } for(int i=0;i<len-1;i++) { nexts[i]=i+1; } nexts[len-1]=-1; int first=0; for(int i=0;i<d;i++) { link_radix_sort_distribute(keys,from,len,radix,i,nexts,queues,first); first=link_radix_sort_collect(keys,from,len,radix,i,nexts,queues); } int[] tmps=new int[len]; int k=0; while(first!=-1) { tmps[k++]=keys[from+first]; first=nexts[first]; } System.arraycopy(tmps, 0, keys, from, len); } private final void link_radix_sort_distribute(int[] keys, int from, int len, int radix, int d, int[] nexts, LinkQueue[] queues,int first) { for(int i=0;i<radix;i++)queues[i].head=queues[i].tail=-1; while(first!=-1) { int val=keys[from+first]; for(int j=0;j<d;j++)val/=radix; val=val%radix; if(queues[val].head==-1) { queues[val].head=first; } else { nexts[queues[val].tail]=first; } queues[val].tail=first; first=nexts[first]; } } private int link_radix_sort_collect(int[] keys, int from, int len, int radix, int d, int[] nexts, LinkQueue[] queues) { int first=0; int last=0; int fromQueue=0; for(;(fromQueue<radix-1)&&(queues[fromQueue].head==-1);fromQueue++); first=queues[fromQueue].head; last=queues[fromQueue].tail; while(fromQueue<radix-1&&queues[fromQueue].head!=-1) { fromQueue+=1; for(;(fromQueue<radix-1)&&(queues[fromQueue].head==-1);fromQueue++); nexts[last]=queues[fromQueue].head; last=queues[fromQueue].tail; } if(last!=-1)nexts[last]=-1; return first; } public static void main(String[] args) { int[] a={1,4,8,3,2,9,5,0,7,6,9,10,9,135,14,15,11,33,999999999,222222222,1111111111,12,17,45,16}; USE_LINK=true; RadixSorter sorter=new RadixSorter(); sorter.sort(a,0,a.length,10,10); for(int i=0;i<a.length;i++) { System.out.print(a[i]+","); } } } 9.归并排序 package com.javasort.mergesorter; /** * 归并排序:思想是每次把待排的序列分成两部分,分别对这两部分递归地用归并排序, * 完成后把这两个子部分合并成一个序列。归并排序借助一个全局性临时数组来方便 * 对子序列的归并,该算法核心在于归并。 */ import java.lang.reflect.Array; import com.javasort.Sorter; /** * * @author Daniel Cheng * * @param <E> */ public class MergeSorter<E extends Comparable<E>> extends Sorter<E> { @SuppressWarnings("unchecked") @Override public void sort(E[] array, int from, int len) { if (len <= 1) return; E[] temporary = (E[]) Array.newInstance(array[0].getClass(), len); merge_sort(array, from, from + len - 1, temporary); } private final void merge_sort(E[] array, int from, int to, E[] temporary) { if (to <= from) { return; } int middle = (from + to) / 2; merge_sort(array, from, middle, temporary); merge_sort(array, middle + 1, to, temporary); merge(array, from, to, middle, temporary); } private final void merge(E[] array, int from, int to, int middle, E[] temporary) { int k = 0, leftIndex = 0, rightIndex = to - from; System.arraycopy(array, from, temporary, 0, middle - from + 1); for (int i = 0; i < to - middle; i++) { temporary[to - from - i] = array[middle + i + 1]; } while (k < to - from + 1) { if (temporary[leftIndex].compareTo(temporary[rightIndex]) < 0) { array[k + from] = temporary[leftIndex++]; } else { array[k + from] = temporary[rightIndex--]; } k++; } } } /** * */ package com.javasort.mergesorter; import com.javasort.Sorter; /** * @author Daniel Cheng * */ public class MergeSorterTest { public static void main(String[] args) { Comparable[] array = { 5, 1, 13, 2, 17, 9, 7, 4, 0 }; Sorter mergeSorter = new MergeSorter(); mergeSorter.sort(array); mergeSorter.printResult(array); } }
声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2009-11-23
不错,要是能把各个性能情况说明下就更完美了
|
|
返回顶楼 | |