`
like_812345
  • 浏览: 10894 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
文章分类
社区版块
存档分类
最新评论

各种排序算法java实现

算法JavaJ# 
阅读更多

  1. package org.rut.util.algorithm.support;
  2. import org.rut.util.algorithm.SortUtil;
  3.  
  4. public class InsertSort implements SortUtil.Sort{
  5.     /* (non-Javadoc)
  6.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  7.      */
  8.     public void sort(int[] data) {
  9.         int temp;
  10.         for(int i=1;i<data.length;i++){
  11.             for(int j=i;(j>0)&amp;&amp;(data[j]<data[j-1]);j–){
  12.                 SortUtil.swap(data,j,j-1);
  13.             }
  14.         }        
  15.     }
  16. }
  17. <span id="more-798"></span>

冒泡排序:
 

  1.  
  2. package org.rut.util.algorithm.support;
  3. import org.rut.util.algorithm.SortUtil;
  4.  
  5. public class BubbleSort implements SortUtil.Sort{
  6.     /* (non-Javadoc)
  7.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  8.      */
  9.     public void sort(int[] data) {
  10.         int temp;
  11.         for(int i=0;i<data.length;i++){
  12.             for(int j=data.length-1;j>i;j–){
  13.                 if(data[j]<data[j-1]){
  14.                     SortUtil.swap(data,j,j-1);
  15.                 }
  16.             }
  17.         }
  18.     }
  19. }
  20.  

选择排序:

  1.  
  2. package org.rut.util.algorithm.support;
  3. import org.rut.util.algorithm.SortUtil;
  4.  
  5. public class SelectionSort implements SortUtil.Sort {
  6.     /*
  7.      * (non-Javadoc)
  8.      * 
  9.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  10.      */
  11.     public void sort(int[] data) {
  12.         int temp;
  13.         for (int i = 0; i < data.length; i++) {
  14.             int lowIndex = i;
  15.             for (int j = data.length – 1; j > i; j–) {
  16.                 if (data[j] < data[lowIndex]) {
  17.                     lowIndex = j;
  18.                 }
  19.             }
  20.             SortUtil.swap(data,i,lowIndex);
  21.         }
  22.     }
  23. }
  24.  

Shell排序:

  1.  
  2. package org.rut.util.algorithm.support;
  3. import org.rut.util.algorithm.SortUtil;
  4.  
  5. public class ShellSort implements SortUtil.Sort{
  6.     /* (non-Javadoc)
  7.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  8.      */
  9.     public void sort(int[] data) {
  10.         for(int i=data.length/2;i>2;i/=2){
  11.             for(int j=0;j<i;j++){
  12.                 insertSort(data,j,i);
  13.             }
  14.         }
  15.         insertSort(data,0,1);
  16.     }
  17.     /**
  18.      * @param data
  19.      * @param j
  20.      * @param i
  21.      */
  22.     private void insertSort(int[] data, int start, int inc) {
  23.         int temp;
  24.         for(int i=start+inc;i<data.length;i+=inc){
  25.             for(int j=i;(j>=inc)&amp;&amp;(data[j]<data[j-inc]);j-=inc){
  26.                 SortUtil.swap(data,j,j-inc);
  27.             }
  28.         }
  29.     }
  30. }

快速排序:

  1.  
  2. package org.rut.util.algorithm.support;
  3. import org.rut.util.algorithm.SortUtil;
  4.  
  5. public class QuickSort implements SortUtil.Sort{
  6.     /* (non-Javadoc)
  7.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  8.      */
  9.     public void sort(int[] data) {
  10.         quickSort(data,0,data.length-1);        
  11.     }
  12.     private void quickSort(int[] data,int i,int j){
  13.         int pivotIndex=(i+j)/2;
  14.         //swap
  15.         SortUtil.swap(data,pivotIndex,j);
  16.         
  17.         int k=partition(data,i-1,j,data[j]);
  18.         SortUtil.swap(data,k,j);
  19.         if((k-i)>1) quickSort(data,i,k-1);
  20.         if((j-k)>1) quickSort(data,k+1,j);
  21.         
  22.     }
  23.     /**
  24.      * @param data
  25.      * @param i
  26.      * @param j
  27.      * @return
  28.      */
  29.     private int partition(int[] data, int l, int r,int pivot) {
  30.         do{
  31.            while(data[++l]<pivot);
  32.            while((r!=0)&amp;&amp;data[–r]>pivot);
  33.            SortUtil.swap(data,l,r);
  34.         }
  35.         while(l<r);
  36.         SortUtil.swap(data,l,r);        
  37.         return l;
  38.     }
  39. }

改进后的快速排序:

  1.  
  2. package org.rut.util.algorithm.support;
  3. import org.rut.util.algorithm.SortUtil;
  4.  
  5. public class ImprovedQuickSort implements SortUtil.Sort {
  6.     private static int MAX_STACK_SIZE=4096;
  7.     private static int THRESHOLD=10;
  8.     /* (non-Javadoc)
  9.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  10.      */
  11.     public void sort(int[] data) {
  12.         int[] stack=new int[MAX_STACK_SIZE];
  13.         
  14.         int top=-1;
  15.         int pivot;
  16.         int pivotIndex,l,r;
  17.         
  18.         stack[++top]=0;
  19.         stack[++top]=data.length-1;
  20.         
  21.         while(top>0){
  22.             int j=stack[top–];
  23.             int i=stack[top–];
  24.             
  25.             pivotIndex=(i+j)/2;
  26.             pivot=data[pivotIndex];
  27.             
  28.             SortUtil.swap(data,pivotIndex,j);
  29.             
  30.             //partition
  31.             l=i-1;
  32.             r=j;
  33.             do{
  34.                 while(data[++l]<pivot);
  35.                 while((r!=0)&amp;&amp;(data[–r]>pivot));
  36.                 SortUtil.swap(data,l,r);
  37.             }
  38.             while(l<r);
  39.             SortUtil.swap(data,l,r);
  40.             SortUtil.swap(data,l,j);
  41.             
  42.             if((l-i)>THRESHOLD){
  43.                 stack[++top]=i;
  44.                 stack[++top]=l-1;
  45.             }
  46.             if((j-l)>THRESHOLD){
  47.                 stack[++top]=l+1;
  48.                 stack[++top]=j;
  49.             }
  50.             
  51.         }
  52.         //new InsertSort().sort(data);
  53.         insertSort(data);
  54.     }
  55.     /**
  56.      * @param data
  57.      */
  58.     private void insertSort(int[] data) {
  59.         int temp;
  60.         for(int i=1;i<data.length;i++){
  61.             for(int j=i;(j>0)&amp;&amp;(data[j]<data[j-1]);j–){
  62.                 SortUtil.swap(data,j,j-1);
  63.             }
  64.         }       
  65.     }
  66. }

归并排序:

  1.  
  2. package org.rut.util.algorithm.support;
  3. import org.rut.util.algorithm.SortUtil;
  4.  
  5. padding
    分享到：
    | linux mysql 操作命令
    评论
    发表评论

    您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics