waysun一路陽光

          不輕易服輸,不輕言放棄.--心是夢的舞臺,心有多大,舞臺有多大。踏踏實實做事,認認真真做人。

            BlogJava :: 首頁 :: 新隨筆 :: 聯系 ::  :: 管理 ::
            167 隨筆 :: 1 文章 :: 64 評論 :: 0 Trackbacks

          轉自:http://www.aygfsteel.com/javacap/archive/2007/12/13/167364.html
          為了便于管理,先引入個基礎類:

          package algorithms;

          /**
           * 
          @author yovn
           *
           
          */
          public abstract class Sorter<extends Comparable<E>> {
              
              
          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 Comparable<E>> extends Sorter<E> {

              
          /* (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;i<from+len;i++)
                    {
                        tmp
          =array[i];
                        
          int j=i;
                        
          for(;j>from;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 Comparable<E>> extends Sorter<E> {

              
          private static  boolean DWON=true;
              
              
          public final void bubble_down(E[] array, int from, int len)
              {
                  
          for(int i=from;i<from+len;i++)
                  {
                      
          for(int j=from+len-1;j>i;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;j<i;j++)
                      {
                          
          if(array[j].compareTo(array[j+1])>0)
                          {
                              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 Comparable<E>> extends Sorter<E> {

              
          /* (non-Javadoc)
               * @see algorithms.Sorter#sort(E[], int, int)
               
          */
              @Override
              
          public void sort(E[] array, int from, int len) {
                  
          for(int i=0;i<len;i++)
                  {
                      
          int smallest=i;
                      
          int j=i+from;
                      
          for(;j<from+len;j++)
                      {
                          
          if(array[j].compareTo(array[smallest])<0)
                          {
                              smallest
          =j;
                          }
                      }
                      swap(array,i,smallest);
                             
                  }

              }
            
          }

          四 Shell排序
          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排序的時候采用該增量序列

          package algorithms;

          /**
           * 
          @author yovn
           
          */
          public class ShellSorter<extends Comparable<E>> extends Sorter<E>  {

              
          /* (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<len)
                  {
                      value
          =(value+1)*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;
                    }

              }
          }


          五 快速排序
          快速排序是目前使用可能最廣泛的排序算法了。
          一般分如下步驟:
          1)選擇一個樞紐元素(有很對選法,我的實現里采用去中間元素的簡單方法)
          2)使用該樞紐元素分割數組,使得比該元素小的元素在它的左邊,比它大的在右邊。并把樞紐元素放在合適的位置。
          3)根據樞紐元素最后確定的位置,把數組分成三部分,左邊的,右邊的,樞紐元素自己,對左邊的,右邊的分別遞歸調用快速排序算法即可。
          快速排序的核心在于分割算法,也可以說是最有技巧的部分。

          package algorithms;

          /**
           * 
          @author yovn
           *
           
          */
          public class QuickSorter<extends Comparable<E>> extends Sorter<E> {

              
          /* (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<to&&array[from].compareTo(tmp)<=0)from++;
                      
          if(from<to)
                      {
                          array[to]
          =array[from];//now from's position is available
                          to--;
                      }
                      
          while(from<to&&array[to].compareTo(tmp)>=0)to--;
                      
          if(from<to)
                      {
                          array[from]
          =array[to];//now to's position is available now 
                          from++;
                      }
                  }
                  array[from]
          =tmp;
                  
          return from;
              }


              
          private int selectPivot(E[] array, int from, int to) {
              
                  
          return (from+to)/2;
              }

          }


          還有歸并排序,堆排序,桶式排序,基數排序,下次在歸納。

          posted on 2009-04-15 22:18 weesun一米陽光 閱讀(291) 評論(0)  編輯  收藏 所屬分類: JAVA源碼總結備用
          主站蜘蛛池模板: 双城市| 阳东县| 定西市| 吴忠市| 台前县| 电白县| 宜兰县| 司法| 体育| 大港区| 金川县| 莱西市| 合山市| 嫩江县| 都兰县| 赞皇县| 安乡县| 乌兰浩特市| 屏东市| 肥城市| 青冈县| 石狮市| 民丰县| 旌德县| 全州县| 宽城| 新乐市| 四子王旗| 冷水江市| 八宿县| 彰化市| 克什克腾旗| 五华县| 崇信县| 乌拉特后旗| 正定县| 宝兴县| 青岛市| 中西区| 雷州市| 广灵县|