java中的算法.pdf
插入排序：package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;publicclass InsertSort implements SortUtil.Sort/*(non-Javadoc)*see org.rut.util.algorithm.SortUtil.Sort#sort(int)*/publicvoid sort(int data)int temp;for(int i=1;i0)&(datajdataj-1);j-)SortUtil.swap(data,j,j-1);冒泡排序：package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;publicclass BubbleSort implements SortUtil.Sort/*(non-Javadoc)*see org.rut.util.algorithm.SortUtil.Sort#sort(int)*/publicvoid sort(int data)int temp;for(int i=0;ii;j-)if(datajdataj-1)SortUtil.swap(data,j,j-1);选择排序：package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;publicclass SelectionSort implements SortUtil.Sort publicvoid sort(int data)int temp;for (int i=0;i i;j-)if (dataj 2;i/=2)for(int j=0;ji;j+)insertSort(data,j,i);insertSort(data,0,1);privatevoid insertSort(int data,int start,int inc)int temp;for(int i=start+inc;i=inc)&(dataj1)quickSort(data,i,k-1);if(j-k)1)quickSort(data,k+1,j);privateint partition(int data,int l,int r,int pivot)do while(data+lpivot);SortUtil.swap(data,l,r);while(l0)int j=stacktop-;int i=stacktop-;pivotIndex=(i+j)/2;pivot=datapivotIndex;SortUtil.swap(data,pivotIndex,j);/partition l=i-1;r=j;do while(data+lpivot);SortUtil.swap(data,l,r);while(lTHRESHOLD)stack+top=i;stack+top=l-1;if(j-l)THRESHOLD)stack+top=l+1;stack+top=j;/new InsertSort().sort(data);insertSort(data);privatevoid insertSort(int data)int temp;for(int i=1;i0)&(datajdataj-1);j-)SortUtil.swap(data,j,j-1);归并排序：package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;lass MergeSort implements SortUtil.Sort publicvoid sort(int data)int temp=new int data.length;mergeSort(data,temp,0,data.length-1);privatevoid mergeSort(int data,int temp,int l,int r)int mid=(l+r)/2;if(l=r)return;mergeSort(data,temp,l,mid);mergeSort(data,temp,mid+1,r);for(int i=l;i=r;i+)temp=data;int i1=l;int i2=mid+1;for(int cur=l;curr)datacur=tempi1+;elseif(tempi1=THRESHOLD)mergeSort(data,temp,l,mid);else insertSort(data,l,mid-l+1);if (r-mid)THRESHOLD)mergeSort(data,temp,mid+1,r);else insertSort(data,mid+1,r-mid);for (i=l;i=mid;i+)temp=data;for (j=1;j=r-mid;j+)tempr-j+1=dataj+mid;int a=templ;int b=tempr;for (i=l,j=r,k=l;k=r;k+)if (a b)datak=tempi+;a=temp;else datak=tempj-;b=tempj;privatevoid insertSort(int data,int start,int len)for(int i=start+1;istart)&datajdataj-1;j-)SortUtil.swap(data,j,j-1);堆排序：package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;publicclass HeapSort implements SortUtil.Sort publicvoid sort(int data)MaxHeap h=new MaxHeap();h.init(data);for(int i=0;idata.length;i+)h.remove();System.arraycopy(h.queue,1,data,0,data.length);privatestaticclass MaxHeap void init(int data)this.queue=new int data.length+1;for(int i=0;idata.length;i+)queue+size=data;fixUp(size);privateint size=0;privateint queue;publicint get()return queue1;publicvoid remove()SortUtil.swap(queue,1,size-);fixDown(1);/fixdownprivatevoid fixDown(int k)int j;while (j=k 1)=size)if (j size&queuejqueuej)/不用交换break;SortUtil.swap(queue,j,k);k=j;privatevoid fixUp(int k)while (k 1)int j=k 1;if (queuejqueuek)break;SortUtil.swap(queue,j,k);k=j;SortUtil：package org.rut.util.algorithm;import org.rut.util.algorithm.support.BubbleSort;import org.rut.util.algorithm.support.HeapSort;import org.rut.util.algorithm.support.ImprovedMergeSort;import org.rut.util.algorithm.support.ImprovedQuickSort;import org.rut.util.algorithm.support.InsertSort;import org.rut.util.algorithm.support.MergeSort;import org.rut.util.algorithm.support.QuickSort;import org.rut.util.algorithm.support.SelectionSort;import org.rut.util.algorithm.support.ShellSort;/*author treeroot *since 2006-2-2 *version 1.0 */publicclass SortUtil publicfinalstaticint INSERT=1;publicfinalstaticint BUBBLE=2;publicfinalstaticint SELECTION=3;publicfinalstaticint SHELL=4;publicfinalstaticint QUICK=5;publicfinalstaticint IMPROVED_QUICK=6;publicfinalstaticint MERGE=7;publicfinalstaticint IMPROVED_MERGE=8;publicfinalstaticint HEAP=9;publicstaticvoid sort(int data)sort(data,IMPROVED_QUICK);privatestaticString name=insert,bubble,selection,shell,quick,improved_quick,merge,improved_merge,heap ;privatestatic Sort impl=new Sort new InsertSort(),new BubbleSort(),new SelectionSort(),new ShellSort(),new QuickSort(),new ImprovedQuickSort(),new MergeSort(),new ImprovedMergeSort(),new HeapSort();publicstaticString to String(int algorithm)return namealgorithm-1;publicstaticvoid sort(int data,int algorithm)implalgorithm-1.sort(data);publicstaticinterface Sort publicvoid sort(int data);publicstaticvoid swap(int data,int i,int j)int temp=data;data=dataj;dataj=temp;
