waysun一路陽(yáng)光

          不輕易服輸,不輕言放棄.--心是夢(mèng)的舞臺(tái),心有多大,舞臺(tái)有多大。踏踏實(shí)實(shí)做事,認(rèn)認(rèn)真真做人。

            BlogJava :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 ::  :: 管理 ::
            167 隨筆 :: 1 文章 :: 64 評(píng)論 :: 0 Trackbacks
          轉(zhuǎn)自:http://www.aygfsteel.com/javacap/archive/2007/12/14/167618.html
          六 歸并排序
          算法思想是每次把待排序列分成兩部分,分別對(duì)這兩部分遞歸地用歸并排序,完成后把這兩個(gè)子部分合并成一個(gè)
          序列。
          歸并排序借助一個(gè)全局性臨時(shí)數(shù)組來(lái)方便對(duì)子序列的歸并,該算法核心在于歸并。
          package algorithms;

          import java.lang.reflect.Array;

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

              
          /* (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<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
          ++;
                  }
                  
              }

          }
          七 堆排序
          堆是一種完全二叉樹(shù),一般使用數(shù)組來(lái)實(shí)現(xiàn)。
          堆主要有兩種核心操作,
          1)從指定節(jié)點(diǎn)向上調(diào)整(shiftUp)
          2)從指定節(jié)點(diǎn)向下調(diào)整(shiftDown)
          建堆,以及刪除堆定節(jié)點(diǎn)使用shiftDwon,而在插入節(jié)點(diǎn)時(shí)一般結(jié)合兩種操作一起使用。
          堆排序借助最大值堆來(lái)實(shí)現(xiàn),第i次從堆頂移除最大值放到數(shù)組的倒數(shù)第i個(gè)位置,然后shiftDown到倒數(shù)第i+1個(gè)位置,一共執(zhí)行N此調(diào)整,即完成排序。
          顯然,堆排序也是一種選擇性的排序,每次選擇第i大的元素。
          package algorithms;

          /**
           * 
          @author yovn
           *
           
          */
          public class HeapSorter<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) {
                  build_heap(array,from,len);

                  
          for(int i=0;i<len;i++)
                  {
                      
          //swap max value to the (len-i)-th position
                      swap(array,from,from+len-1-i);
                      shift_down(array,from,len
          -1-i,0);//always shiftDown from 0
                  }
              }

              
          private final void build_heap(E[] array, int from, int len) {
                  
          int pos=(len-1)/2;//we start from (len-1)/2, because branch's node +1=leaf's node, and all leaf node is already a heap
                  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;//use left child
                  while(index<len)//until no child
                  {
                      
          if(index+1<len&&array[from+index].compareTo(array[from+index+1])<0)//right child is bigger
                      {
                          index
          +=1;//switch to right child
                      }
                      
          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;
                      
              }

              
          }

          八 桶式排序
          桶式排序不再是基于比較的了,它和基數(shù)排序同屬于分配類的排序,這類排序的特點(diǎn)是事先要知道待排序列的一些特征。
          桶式排序事先要知道待排序列在一個(gè)范圍內(nèi),而且這個(gè)范圍應(yīng)該不是很大的。
          比如知道待排序列在[0,M)內(nèi),那么可以分配M個(gè)桶,第I個(gè)桶記錄I的出現(xiàn)情況,最后根據(jù)每個(gè)桶收到的位置信息把數(shù)據(jù)輸出成有序的形式。
          這里我們用兩個(gè)臨時(shí)性數(shù)組,一個(gè)用于記錄位置信息,一個(gè)用于方便輸出數(shù)據(jù)成有序方式,另外我們假設(shè)數(shù)據(jù)落在0到MAX,如果所給數(shù)據(jù)不是從0開(kāi)始,你可以把每個(gè)數(shù)減去最小的數(shù)。
          package algorithms;

          /**
           * 
          @author yovn
           *
           
          */
          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];//this means how many number which is less or equals than i,thus it is also position + 1 
                  }
                  
                  System.arraycopy(keys, from, temp, 
          0, len);
                  
          for(int k=len-1;k>=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<a.length;i++)
                  {
                      System.out.print(a[i]
          +",");
                  }

              }

          }

          九 基數(shù)排序
          基數(shù)排序可以說(shuō)是擴(kuò)展了的桶式排序,比如當(dāng)待排序列在一個(gè)很大的范圍內(nèi),比如0到999999內(nèi),那么用桶式排序是很浪費(fèi)空間的。而基數(shù)排序把每個(gè)排序碼拆成由d個(gè)排序碼,比如任何一個(gè)6位數(shù)(不滿六位前面補(bǔ)0)拆成6個(gè)排序碼,分別是個(gè)位的,十位的,百位的。。。。
          排序時(shí),分6次完成,每次按第i個(gè)排序碼來(lái)排。
          一般有兩種方式:
          1) 高位優(yōu)先(MSD): 從高位到低位依次對(duì)序列排序
          2)低位優(yōu)先(LSD): 從低位到高位依次對(duì)序列排序
          計(jì)算機(jī)一般采用低位優(yōu)先法(人類一般使用高位優(yōu)先),但是采用低位優(yōu)先時(shí)要確保排序算法的穩(wěn)定性。
          基數(shù)排序借助桶式排序,每次按第N位排序時(shí),采用桶式排序。對(duì)于如何安排每次落入同一個(gè)桶中的數(shù)據(jù)有兩種安排方法:
          1)順序存儲(chǔ):每次使用桶式排序,放入r個(gè)桶中,,相同時(shí)增加計(jì)數(shù)。
          2)鏈?zhǔn)酱鎯?chǔ):每個(gè)桶通過(guò)一個(gè)靜態(tài)隊(duì)列來(lái)跟蹤。

          package algorithms;

          import java.util.Arrays;


          /**
           * 
          @author yovn
           *
           
          */
          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;
              }
              
              
          /**
               * 
          @param args
               
          */
              
          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,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]
          +",");
                  }


              }

          }
          posted on 2009-04-15 22:13 weesun一米陽(yáng)光 閱讀(284) 評(píng)論(0)  編輯  收藏 所屬分類: JAVA源碼總結(jié)備用
          主站蜘蛛池模板: 平顶山市| 贵南县| 天柱县| 洛川县| 丹寨县| 平塘县| 台安县| 怀安县| 西乌珠穆沁旗| 遂昌县| 启东市| 民勤县| 囊谦县| 汉川市| 阿拉善盟| 焉耆| 东山县| 阜新市| 祁东县| 乌拉特后旗| 安达市| 绥江县| 商丘市| 吴忠市| 永丰县| 弥勒县| 永年县| 永康市| 武穴市| 彭山县| 江城| 清河县| 三都| 苏尼特右旗| 政和县| 济源市| 台前县| 乌拉特后旗| 安西县| 北海市| 曲阜市|