//java排序算法封装类
import java.util.Random; public class PaiXu { /** * 通过数组下标交换数组元素的方法 */ public void swap(int[] arr,int begin,int end){ int t; t= arr[begin]; arr[begin]=arr[end]; arr[end]=t; } //快速排序 public void quickSort(int[] arr,int begin,int end){ if(begin>end) return; int mid = getMid(arr,begin,end); quickSort(arr,mid+1,end); quickSort(arr,begin,mid-1); } //快速排序（找出中位数） public int getMid(int[] arr,int begin,int end){ int mid = begin; while(begin<end){ while(begin<end&&arr[end]>=arr[mid]) end--; while(begin<end&&arr[begin]<=arr[mid]) begin++; if(begin<end){ swap(arr,begin,end); } } if(begin!=mid){ swap(arr,begin,mid); } return begin; } //冒泡 public void bubbleSort(int[] arr){ for(int i=0;i<arr.length-1;i++){ for(int j=0;j<arr.length-i-1;j++){ if(arr[j]>arr[j+1]) swap(arr,j,j+1); } } } //选择排序 public void chooseSort(int[] arr){ int inMax,inMaxValue; for(int i=0;i<arr.length-1;i++){ inMax=0; inMaxValue=arr.length-i-1; for(int j=1;j<=inMaxValue;j++){ if(arr[inMax]<arr[j]) inMax=j; } if(inMax!=inMaxValue) swap(arr,inMax,inMaxValue); } } //插入排序 public void insertSort(int[] arr){ for(int i=1,t,j;i<arr.length;i++) { if(arr[i]>arr[i-1]) continue; t=arr[i]; for( j=i-1;j>=0&&arr[j]>t;j--) arr[j+1]=arr[j]; arr[j+1]=t; } } //希尔排序 public void hillSort(int[] arr) { int step =arr.length,t; while ((step=step/2)>=2) { for (int i = 0; i+step < arr.length; i++) { if (arr[i]>arr[i+step]){ swap(arr,i,i+step); } } } insertSort(arr); } //桶排序 public void bucketSort(int[] arr){ final int U =10; int[][] bucket=new int[U][arr.length]; int[] ixs = new int[U]; for (int i =1,count,t;;i*=10){ count=0; for (int j = 0; j < arr.length; j++) { count=(t=arr[j]/i)>=1?++count:count; bucket[t%=U][ixs[t]++]=arr[j];} if (count==0)break; for (int j = 0,ix=0; j < bucket.length; j++) { for (int k = 0; k <ixs[j] ; k++) { arr[ix++]=bucket[j][k]; } } for (int j = 0; j <ixs.length ; j++) { ixs[j]=0; } } } }