Java常见排序算法.doc

《Java常见排序算法.doc》由会员分享，可在线阅读，更多相关《Java常见排序算法.doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Java各种排序Java各种排序：插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。 插入排序：package org.rut.util.algorithm.support;import org.rut.util.algorithm.SortUtil;/* * author treeroot * since 2006-2-2 * version 1.0 */public class InsertSort implements SortUtil.Sort /* (non-Javadoc) * see org.rut.util.algorithm.Sor

2、tUtil.Sort#sort(int) */ public void 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;/* * author treeroot * since 2006-2-2 * version 1.0 */public class BubbleSort implements Sort

3、Util.Sort /* (non-Javadoc) * see org.rut.util.algorithm.SortUtil.Sort#sort(int) */ public void 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;/* * author treeroot * since 2006

4、-2-2 * version 1.0 */public class SelectionSort implements SortUtil.Sort /* * (non-Javadoc) * * see org.rut.util.algorithm.SortUtil.Sort#sort(int) */ public void 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); /* * pa

5、ram data * param j * param i */ private void 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); /* * param data * param i * param j * return */ private int partition(int data, int l, int r,int pivot) do while

6、(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

7、+top=l+1; stack+top=j; /new InsertSort().sort(data); insertSort(data); /* * param data */ private void 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;/* * author treeroot

8、 * since 2006-2-2 * version 1.0 */public class MergeSort implements SortUtil.Sort /* (non-Javadoc) * see org.rut.util.algorithm.SortUtil.Sort#sort(int) */ public void sort(int data) int temp=new intdata.length; mergeSort(data,temp,0,data.length-1); private void mergeSort(int data,int temp,int l,int

9、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+) tempi=datai; int i1=l; int i2=mid+1; for(int cur=l;curr) datacur=tempi1+; else if(tempi1= THRESHOLD) mergeSort(data, temp, l, mid); else insertSort(data, l, mid - l + 1); if (r - mid) T

10、HRESHOLD) mergeSort(data, temp, mid + 1, r); else insertSort(data, mid + 1, r - mid); for (i = l; i = mid; i+) tempi = datai; 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 = tempi; else datak =

11、tempj-; b = tempj; /* * param data * param l * param i */ private void 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;/* * author treeroot * since 2006

12、-2-2 * version 1.0 */public class HeapSort implements SortUtil.Sort /* (non-Javadoc) * see org.rut.util.algorithm.SortUtil.Sort#sort(int) */ public void 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); priv

13、ate static class MaxHeap void init(int data) this.queue=new intdata.length+1; for(int i=0;idata.length;i+) queue+size=datai; fixUp(size); private int size=0; private int queue; public int get() return queue1; public void remove() SortUtil.swap(queue,1,size-); fixDown(1); /fixdown private void fixDow

14、n(int k) int j; while (j = k 1) = size) if (j size & queuejqueuej) /不用交换 break; SortUtil.swap(queue,j,k); k = j; private void 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.suppor

15、t.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.s

16、upport.QuickSort;import org.rut.util.algorithm.support.SelectionSort;import org.rut.util.algorithm.support.ShellSort;/* * author treeroot * since 2006-2-2 * version 1.0 */public class SortUtil public final static int INSERT = 1; public final static int BUBBLE = 2; public final static int SELECTION =

17、 3; public final static int SHELL = 4; public final static int QUICK = 5; public final static int IMPROVED_QUICK = 6; public final static int MERGE = 7; public final static int IMPROVED_MERGE = 8; public final static int HEAP = 9; public static void sort(int data) sort(data, IMPROVED_QUICK); private

18、 static String name= insert, bubble, selection, shell, quick, improved_quick, merge, improved_merge, heap ; private static Sort impl=new Sort new InsertSort(), new BubbleSort(), new SelectionSort(), new ShellSort(), new QuickSort(), new ImprovedQuickSort(), new MergeSort(), new ImprovedMergeSort(),

19、new HeapSort() ; public static String toString(int algorithm) return namealgorithm-1; public static void sort(int data, int algorithm) implalgorithm-1.sort(data); public static interface Sort public void sort(int data); public static void swap(int data, int i, int j) int temp = datai; datai = dataj; dataj = temp;