java排序算法大全


java java java java 排 序算 法大 全 为 了便 于管 理, 先引 入个 基础 类: package algorithms; public abstract class Sorter> { public abstract void sort(E[] array,int from ,int len); public final void sort(E[] array) { sort(array,0,array.length); } protected final void swap(E[] array,int from ,int to) { E tmp=array[from]; array[from]=array[to]; array[to]=tmp; } } 一插 入排 序 该 算法 在数 据规 模小 的时 候十 分高 效, 该算 法每 次插 入第 K+1 到前K个 有序 数组 中一 个合 适 位置 , K从0开 始到 N-1,从 而完 成排 序: package algorithms; /** *@author yovn */ public class InsertSorter> extends Sorter { /*(non-Javadoc) *@see algorithms.Sorter#sort(E[], int, int) */ public void sort(E[] array, int from, int len) { E tmp=null; for(int i=from+1;ifrom;j--) { if(tmp.compareTo(array[j-1])<0) { array[j]=array[j-1]; } else break; } array[j]=tmp; } } } 二冒 泡排 序 这 可能 是最 简单 的排 序算 法了 ,算 法思 想是 每次 从数 组末 端开 始比 较相 邻两 元素 ,把第i小 的 冒泡 到数 组的 第 i个 位置 。 i从0一 直到 N-1 从 而完 成排 序。 (当 然也 可以 从数 组开 始端 开 始比 较相 邻两 元素 ,把 第 i大 的冒 泡到 数组 的第 N-i 个 位置 。 i从0一 直到 N-1 从 而完 成 排 序。 ) package algorithms; /** *@author yovn * */ public class BubbleSorter> extends Sorter { private static boolean DWON=true; public final void bubble_down(E[] array, int from, int len) { for(int i=from;ii;j--) { if(array[j].compareTo(array[j-1])<0) { swap(array,j-1,j); } } } } public final void bubble_up(E[] array, int from, int len) { for(int i=from+len-1;i>=from;i--) { for(int j=from;j0) { swap(array,j,j+1); } } } } @Override public void sort(E[] array, int from, int len) { if(DWON) { bubble_down(array,from,len); } else { bubble_up(array,from,len); } } } 三 ,选 择排 序 选 择排 序相 对于 冒泡 来说 ,它 不是 每次 发现 逆序 都交 换 ,而 是在 找到 全局 第 i小 的时 候记 下 该 元素 位置 ,最 后跟 第 i个 元素 交换 ,从 而保 证数 组最 终的 有序 。 相 对与 插入 排序 来说 ,选 择排 序每 次选 出的 都是 全局 第 i小 的, 不会 调整 前 i个 元素 了。 package algorithms; /** *@author yovn * */ public class SelectSorter> extends Sorter { /*(non-Javadoc) *@see algorithms.Sorter#sort(E[], int, int) */ @Override public void sort(E[] array, int from, int len) { for(int i=0;i> extends Sorter { /*(non-Javadoc) * Our delta value choose 2^k-1,2^(k-1)-1, .7,3,1. * complexity is O(n^1.5) *@see algorithms.Sorter#sort(E[], int, int) */ @Override public void sort(E[] array, int from, int len) { //1.calculate the first delta value; int value=1; while((value+1)*2=1;delta=(delta+1)/2-1) { for(int i=0;ifrom;j-=delta) { if(tmp.compareTo(array[j-delta])<0) { array[j]=array[j-delta]; } else break; } array[j]=tmp; } } } 五快 速排 序 快 速排 序是 目前 使用 可能 最广 泛的 排序 算法 了。 一 般分 如下 步骤 : 1) 选择 一个 枢纽 元素 (有 很对 选法 ,我 的实 现里 采用 去中 间元 素的 简单 方法 ) 2)使 用该 枢纽 元素 分割 数组 ,使 得比 该元 素小 的元 素在 它的 左边 ,比 它大 的在 右边 。并把 枢 纽元 素放 在合 适的 位置 。 3) 根据 枢纽 元素 最后 确定 的位 置, 把数 组分 成三 部分 ,左 边的 ,右 边的 ,枢 纽元 素自 己 , 对 左边 的, 右边 的分 别递 归调 用快 速排 序算 法即 可。 快 速排 序的 核心 在于 分割 算法 ,也 可以 说是 最有 技巧 的部 分。 package algorithms; /** *@author yovn * */ public class QuickSorter> extends Sorter { /*(non-Javadoc) *@see algorithms.Sorter#sort(E[], int, int) */ @Override public void sort(E[] array, int from, int len) { q_sort(array,from,from+len-1); } private final void q_sort(E[] array, int from, int to) { if(to-from<1)return; int pivot=selectPivot(array,from,to); pivot=partion(array,from,to,pivot); q_sort(array,from,pivot-1); q_sort(array,pivot+1,to); } private int partion(E[] array, int from, int to, int pivot) { E tmp=array[pivot]; array[pivot]=array[to];//now to's position is available while(from!=to) { while(from=0)to--; if(from> extends Sorter { /*(non-Javadoc) *@see algorithms.Sorter#sort(E[], int, int) */ @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> extends Sorter { /*(non-Javadoc) *@see algorithms.Sorter#sort(E[], int, int) */ @Override public void sort(E[] array, int from, int len) { build_heap(array,from,len); for(int i=0;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;//use left child while(index=0;k--)//from the ending to beginning can keep the stability { 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 sorter=new BucketSorter(); sorter.sort(a,0,a.length,20);//actually is 18, but 20 will also work for(int i=0;i=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
还剩15页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 15 金币 [ 分享pdf获得金币 ] 3 人已下载

下载pdf

pdf贡献者

blues_leaf

贡献于2010-11-07

下载需要 15 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf