熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> Java編程 >> Java核心技術 >> 正文

java的各種排序算法

2013-11-23 18:48:05  來源: Java核心技術 

  Java代碼

  插入排序:

  

  package orgrututilalgorithmsupport;

  import orgrututilalgorithmSortUtil;

  public class InsertSort implements SortUtilSort{

      /* (nonJavadoc)

       * @see orgrututilalgorithmSortUtilSort#sort(int[])

       */

      public void sort(int[] data) {

          int temp;

          for(int i=;i<datalength;i++){

              for(int j=i;(j>)&&(data[j]<data[j]);j){

                  SortUtilswap(datajj);

              }

          }

      }

  }

  冒泡排序:

  

  package orgrututilalgorithmsupport;

  import orgrututilalgorithmSortUtil;

  public class BubbleSort implements SortUtilSort{

      /* (nonJavadoc)

       * @see orgrututilalgorithmSortUtilSort#sort(int[])

       */

      public void sort(int[] data) {

          int temp;

          for(int i=;i<datalength;i++){

              for(int j=datalength;j>i;j){

                  if(data[j]<data[j]){

                      SortUtilswap(datajj);

                  }

              }

          }

      }

  }

  選擇排序:

  package orgrututilalgorithmsupport;

  import orgrututilalgorithmSortUtil;

  public class SelectionSort implements SortUtilSort {

      /*

       * (nonJavadoc)

       *

       * @see orgrututilalgorithmSortUtilSort#sort(int[])

       */

      public void sort(int[] data) {

          int temp;

          for (int i = ; i < datalength; i++) {

              int lowIndex = i;

              for (int j = datalength ; j > i; j) {

                  if (data[j] < data[lowIndex]) {

                      lowIndex = j;

                  }

              }

              SortUtilswap(datailowIndex);

          }

      }

  }

  Shell排序:

  package orgrututilalgorithmsupport;

  import orgrututilalgorithmSortUtil;

  public class ShellSort implements SortUtilSort{

      /* (nonJavadoc)

       * @see orgrututilalgorithmSortUtilSort#sort(int[])

       */

      public void sort(int[] data) {

          for(int i=datalength/;i>;i/=){

              for(int j=;j<i;j++){

                  insertSort(dataji);

              }

          }

          insertSort(data);

      }

      /**

       * @param data

       * @param j

       * @param i

       */

      private void insertSort(int[] data int start int inc) {

          int temp;

          for(int i=start+inc;i<datalength;i+=inc){

              for(int j=i;(j>=inc)&&(data[j]<data[jinc]);j=inc){

                  SortUtilswap(datajjinc);

              }

          }

      }

  }

  快速排序:

  package orgrututilalgorithmsupport;

  import orgrututilalgorithmSortUtil;

  public class QuickSort implements SortUtilSort{

      /* (nonJavadoc)

       * @see orgrututilalgorithmSortUtilSort#sort(int[])

       */

      public void sort(int[] data) {

          quickSort(datadatalength);

      }

      private void quickSort(int[] dataint iint j){

          int pivotIndex=(i+j)/;

          //swap         SortUtilswap(datapivotIndexj);

  

          int k=partition(dataijdata[j]);

          SortUtilswap(datakj);

          if((ki)>) quickSort(dataik);

          if((jk)>) quickSort(datak+j);

  

      }

      /**

       * @param data

       * @param i

       * @param j

       * @return

       */

      private int partition(int[] data int l int rint pivot) {

          do{

             while(data[++l]<pivot);

             while((r!=)&&data[r]>pivot);

             SortUtilswap(datalr);

          }

          while(l<r);

          SortUtilswap(datalr);

          return l;

      }

  }

  改進後的快速排序:

  package orgrututilalgorithmsupport;

  import orgrututilalgorithmSortUtil;

  public class ImprovedQuickSort implements SortUtilSort {

      private static int MAX_STACK_SIZE=;

      private static int THRESHOLD=;

      /* (nonJavadoc)

       * @see orgrututilalgorithmSortUtilSort#sort(int[])

       */

      public void sort(int[] data) {

          int[] stack=new int[MAX_STACK_SIZE];

  

          int top=;

          int pivot;

          int pivotIndexlr;

  

          stack[++top]=;

          stack[++top]=datalength;

  

          while(top>){

              int j=stack[top];

              int i=stack[top];

  

              pivotIndex=(i+j)/;

              pivot=data[pivotIndex];

  

              SortUtilswap(datapivotIndexj);

  

              //partition             l=i;

              r=j;

              do{

                  while(data[++l]<pivot);

                  while((r!=)&&(data[r]>pivot));

                  SortUtilswap(datalr);

              }

              while(l<r);

              SortUtilswap(datalr);

              SortUtilswap(datalj);

  

              if((li)>THRESHOLD){

                  stack[++top]=i;

                  stack[++top]=l;

              }

              if((jl)>THRESHOLD){

                  stack[++top]=l+;

                  stack[++top]=j;

              }

  

          }

          //new InsertSort()sort(data);         insertSort(data);

      }

      /**

       * @param data

       */

      private void insertSort(int[] data) {

          int temp;

          for(int i=;i<datalength;i++){

              for(int j=i;(j>)&&(data[j]<data[j]);j){

                  SortUtilswap(datajj);

              }

          }

      }

  }

  歸並排序:

  package orgrututilalgorithmsupport;

  import orgrututilalgorithmSortUtil;

  public class MergeSort implements SortUtilSort{

      /* (nonJavadoc)

       * @see orgrututilalgorithmSortUtilSort#sort(int[])

       */

      public void sort(int[] data) {

          int[] temp=new int[datalength];

          mergeSort(datatempdatalength);

      }

  

      private void mergeSort(int[] dataint[] tempint lint r){

          int mid=(l+r)/;

          if(l==r) return ;

          mergeSort(datatemplmid);

          mergeSort(datatempmid+r);

          for(int i=l;i<=r;i++){

              temp[i]=data[i];

          }

          int i=l;

          int i=mid+;

          for(int cur=l;cur<=r;cur++){

              if(i==mid+)

                  data[cur]=temp[i++];

              else if(i>r)

                  data[cur]=temp[i++];

              else if(temp[i]<temp[i])

                  data[cur]=temp[i++];

              else

                  data[cur]=temp[i++];

          }

      }

  }

  改進後的歸並排序:

  

  package orgrututilalgorithmsupport;

  import orgrututilalgorithmSortUtil;

  public class ImprovedMergeSort implements SortUtilSort {

      private static final int THRESHOLD = ;

      /*

       * (nonJavadoc)

       *

       * @see orgrututilalgorithmSortUtilSort#sort(int[])

       */

      public void sort(int[] data) {

          int[] temp=new int[datalength];

          mergeSort(datatempdatalength);

      }

      private void mergeSort(int[] data int[] temp int l int r) {

          int i j k;

          int mid = (l + r) / ;

          if (l == r)

              return;

          if ((mid l) >= THRESHOLD)

              mergeSort(data temp l mid);

          else

              insertSort(data l mid l + );

          if ((r mid) > THRESHOLD)

              mergeSort(data temp mid + r);

          else

              insertSort(data mid + r mid);

          for (i = l; i <= mid; i++) {

              temp[i] = data[i];

          }

          for (j = ; j <= r mid; j++) {

              temp[r j + ] = data[j + mid];

          }

          int a = temp[l];

          int b = temp[r];

          for (i = l j = r k = l; k <= r; k++) {

              if (a < b) {

                  data[k] = temp[i++];

                  a = temp[i];

              } else {

                  data[k] = temp[j];

                  b = temp[j];

              }

          }

      }

      /**

       * @param data

       * @param l

       * @param i

       */

      private void insertSort(int[] data int start int len) {

          for(int i=start+;i<start+len;i++){

              for(int j=i;(j>start) && data[j]<data[j];j){

                  SortUtilswap(datajj);

              }

          }

      }

  }

  堆排序:

  package orgrututilalgorithmsupport;

  import orgrututilalgorithmSortUtil;

  public class HeapSort implements SortUtilSort{

      /* (nonJavadoc)

       * @see orgrututilalgorithmSortUtilSort#sort(int[])

       */

      public void sort(int[] data) {

          MaxHeap h=new MaxHeap();

          hinit(data);

          for(int i=;i<datalength;i++)

              hremove();

          Systemarraycopy(hqueuedatadatalength);

      }

       private static class MaxHeap{

  

  

          void init(int[] data){

              thisqueue=new int[datalength+];

              for(int i=;i<datalength;i++){

                  queue[++size]=data[i];

                  fixUp(size);

              }

          }

  

          private int size=;

          private int[] queue;

  

          public int get() {

              return queue[];

          }

          public void remove() {

              SortUtilswap(queuesize);

              fixDown();

          }

          //fixdown         private void fixDown(int k) {

              int j;

              while ((j = k << ) <= size) {

                  if (j < size && queue[j]<queue[j+])

                      j++;

                  if (queue[k]>queue[j]) //不用交換                     break;

                  SortUtilswap(queuejk);

                  k = j;

              }

          }

          private void fixUp(int k) {

              while (k > ) {

                  int j = k >> ;

                  if (queue[j]>queue[k])

                      break;

                  SortUtilswap(queuejk);

                  k = j;

              }

          }

      }

  }

  SortUtil:

  package orgrututilalgorithm;

  import orgrututilalgorithmsupportBubbleSort;

  import orgrututilalgorithmsupportHeapSort;

  import orgrututilalgorithmsupportImprovedMergeSort;

  import orgrututilalgorithmsupportImprovedQuickSort;

  import orgrututilalgorithmsupportInsertSort;

  import orgrututilalgorithmsupportMergeSort;

  import orgrututilalgorithmsupportQuickSort;

  import orgrututilalgorithmsupportSelectionSort;

  import orgrututilalgorithmsupportShellSort;

  public class SortUtil {

      public final static int INSERT = ;

      public final static int BUBBLE = ;

      public final static int SELECTION = ;

      public final static int SHELL = ;

      public final static int QUICK = ;

      public final static int IMPROVED_QUICK = ;

      public final static int MERGE = ;

      public final static int IMPROVED_MERGE = ;

      public final static int HEAP = ;

      public static void sort(int[] data) {

          sort(data IMPROVED_QUICK);

      }

      private static String[] name={

              insertbubbleselectionshellquickimproved_quickmergeimproved_mergeheap

      };

  

      private static Sort[] impl=new Sort[]{

              new InsertSort()

              new BubbleSort()

              new SelectionSort()

              new ShellSort()

              new QuickSort()

              new ImprovedQuickSort()

              new MergeSort()

              new ImprovedMergeSort()

              new HeapSort()

      };

      public static String toString(int algorithm){

          return name[algorithm];

      }

  

      public static void sort(int[] data int algorithm) {

          impl[algorithm]sort(data);

      }

      public static interface Sort {

          public void sort(int[] data);

      }

      public static void swap(int[] data int i int j) {

          int temp = data[i];

          data[i] = data[j];

          data[j] = temp;

      }

  }


From:http://tw.wingwit.com/Article/program/Java/hx/201311/25756.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.