Java排序

403483118 贡献于2011-05-28

作者 雨林木风  创建于2009-09-12 14:11:00   修改者雨林木风  修改于2009-09-14 01:47:00字数10233

文档摘要:一 插入排序 <br> 该算法在数据规模小的时候十分高效,该算法每次插入第K+1到前K个有序数组中一个合适位置,K从0开始到N-1,从而完成排序: <br> 二 冒泡排序 <br> 这可能是最简单的排序算法了,算法思想是每次从数组末端开始比较相邻两元素,把第i小的冒泡到数组的第i个位置。i从0一直到N-1从而完成排序。(当然也可以从数组开始端开始比较相邻两元素,把第i大的冒泡到数组的第N-i个位置。i从0一直到N-1从而完成排序。) <br> 三,选择排序 <br> 选择排序相对于冒泡来说,它不是每次发现逆序都交换,而是在找到全局第i小的时候记下该元素位置,最后跟第i个元素交换,从而保证数组最终的有序。相对与插入排序来说,选择排序每次选出的都是全局第i小的,不会调整前i个元素了。 四 Shell排序 <br>
关键词:

窗体顶端 博客登录 用户名: 密 码: 窗体底端 /* 为了便于管理,先引入个基础类: */ package algorithms; /** * @author yovn * */ 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,从而完成排序: */ // /** * @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从而完成排序。) */ /** * @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);                                 }                         }                 }         }                  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个元素了。 */ /** * @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)根据枢纽元素最后确定的位置,把数组分成三部分,左边的,右边的,枢纽元素自己,对左边的,右边的分别递归调用快速排序算法即可。 快速排序的核心在于分割算法,也可以说是最有技巧的部分。 */ /** * @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 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档