[转帖]用Java实现几种常见的排序算法
<p> <font size="5"> </font><a href="http://www.hzguigu.com/bbs"><font size="5">www.hzguigu.com/bbs</font></a><font size="5"> </font></p><p> <font size="3"> 用Java语言实现的各种排序，包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。</font></p><p><font size="3"> 插入排序：</font></p><p><font size="3"> package org.rut.util.algorithm.support;<br/> import org.rut.util.algorithm.SortUtil;<br/> /**<br/> * @author treeroot<br/> * @since 2006-2-2<br/> * @version 1.0<br/> */<br/> public class InsertSort implements SortUtil.Sort<br/> {<br/> /* (non-Javadoc)<br/> * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])<br/> */<br/> public void sort(int[] data) <br/> {<br/> int temp;<br/> for(int i=1;i for(int j=i;(j>0)&&(data SortUtil.swap(data,j,j-1);<br/> }<br/> } </font></p><p><font size="3"> 冒泡排序：</font></p><p><font size="3"> package org.rut.util.algorithm.support;<br/> import org.rut.util.algorithm.SortUtil;<br/> /**<br/> * @author treeroot<br/> * @since 2006-2-2<br/> * @version 1.0<br/> */<br/> public class BubbleSort implements SortUtil.Sort<br/> {<br/> /* (non-Javadoc)<br/> * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])<br/> */<br/> public void sort(int[] data) <br/> {<br/> int temp;<br/> for(int i=0;i for(int j=data.length-1;j>i;j--)<br/> {<br/> if(data SortUtil.swap(data,j,j-1);<br/> }<br/> }<br/> }</font></p><p><font size="3"> 选择排序：</font></p><p><font size="3"> package org.rut.util.algorithm.support;<br/> import org.rut.util.algorithm.SortUtil;<br/> /**<br/> * @author treeroot<br/> * @since 2006-2-2<br/> * @version 1.0<br/> */<br/> public class SelectionSort implements SortUtil.Sort <br/> {<br/> /*<br/> * (non-Javadoc)<br/> * <br/> * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])<br/> */<br/> public void sort(int[] data) <br/> {<br/> int temp;<br/> for (int i = 0; i < data.length; i++) <br/> {<br/> int lowIndex = i;<br/> for (int j = data.length - 1; j >i; j--) <br/> {<br/> if (data < data) <br/> {<br/> lowIndex = j;<br/> }<br/> }<br/> SortUtil.swap(data,i,lowIndex);<br/> }<br/> }<br/> }<br/> Shell排序：</font></p><p><font size="3"> package org.rut.util.algorithm.support;<br/> import org.rut.util.algorithm.SortUtil;<br/> /**<br/> * @author treeroot<br/> * @since 2006-2-2<br/> * @version 1.0<br/> */<br/> public class ShellSort implements SortUtil.Sort<br/> {<br/> /* (non-Javadoc)<br/> * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])<br/> */<br/> public void sort(int[] data) <br/> {<br/> for(int i=data.length/2;i>2;i/=2)<br/> {<br/> for(int j=0;j insertSort(data,j,i);<br/> }<br/> }<br/> insertSort(data,0,1);<br/> }</font></p><p><font size="3"> /**<br/> * @param data<br/> * @param j<br/> * @param i<br/> */<br/> private void insertSort(int[] data, int start, int inc) <br/> {<br/> int temp;<br/> for(int i=start+inc;i for(int j=i;(j>=inc)&&(data SortUtil.swap(data,j,j-inc);<br/> }</font></p><p><font size="3"> 快速排序：</font></p><p><font size="3"> package org.rut.util.algorithm.support;<br/> import org.rut.util.algorithm.SortUtil;<br/> /**<br/> * @author treeroot<br/> * @since 2006-2-2<br/> * @version 1.0<br/> */<br/> public class QuickSort implements SortUtil.Sort<br/> {<br/> /* (non-Javadoc)<br/> * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])<br/> */<br/> public void sort(int[] data) <br/> {<br/> quickSort(data,0,data.length-1); <br/> }<br/> private void quickSort(int[] data,int i,int j)<br/> {<br/> int pivotIndex=(i+j)/2;<br/> //swap<br/> SortUtil.swap(data,pivotIndex,j);<br/> int k=partition(data,i-1,j,data);<br/> SortUtil.swap(data,k,j);<br/> if((k-i)>1) quickSort(data,i,k-1);<br/> if((j-k)>1) quickSort(data,k+1,j);<br/> }<br/> /**<br/> * @param data<br/> * @param i<br/> * @param j<br/> * @return<br/> */<br/> private int partition(int[] data, int l, int r,int pivot) <br/> {<br/> do<br/> {<br/> while(data[++l] while((r!=0)&&data[--r]>pivot);<br/> SortUtil.swap(data,l,r);<br/> }<br/> while(l SortUtil.swap(data,l,r); <br/> return l;<br/> }<br/> }</font></p><p><font size="3"> <br/>归并排序：</font></p><p><font size="3"> package org.rut.util.algorithm.support;<br/> import org.rut.util.algorithm.SortUtil;<br/> /**<br/> * @author treeroot<br/> * @since 2006-2-2<br/> * @version 1.0<br/> */<br/> public class MergeSort implements SortUtil.Sort<br/> {<br/> /* (non-Javadoc)<br/> * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])<br/> */<br/> public void sort(int[] data) <br/> {<br/> int[] temp=new int;<br/> mergeSort(data,temp,0,data.length-1);<br/> }<br/> private void mergeSort(int[] data,int[] temp,int l,int r)<br/> {<br/> int mid=(l+r)/2;<br/> if(l==r) return ;<br/> mergeSort(data,temp,l,mid);<br/> mergeSort(data,temp,mid+1,r);<br/> for(int i=l;i<=r;i++){<br/> temp=data;<br/> }<br/> int i1=l;<br/> int i2=mid+1;<br/> for(int cur=l;cur<=r;cur++)<br/> {<br/> if(i1==mid+1)<br/> data=temp;<br/> else if(i2>r)<br/> data=temp;<br/> else if(temp data=temp;<br/> else<br/> data=temp; <br/> }<br/> }</font></p>
页:
[1]