插入排序:
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.sortutil.sort#sort(int[])
*/
public void sort(int[] data) {
int temp;
for(int i=1;i<data.length;i++){
for(int j=i;(j>0)&&(data[j]<data[j-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 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<data.length;i++){
for(int j=data.length-1;j>i;j--){
if(data[j]<data[j-1]){
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 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 < data.length; i++) {
int lowindex = i;
for (int j = data.length - 1; j > i; j--) {
if (data[j] < data[lowindex]) {
lowindex = j;
}
}
sortutil.swap(data,i,lowindex);
}
}
}
shell排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.sortutil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class shellsort implements sortutil.sort{
/* (non-javadoc)
* @see org.rut.util.algorithm.sortutil.sort#sort(int[])
*/
public void sort(int[] data) {
for(int i=data.length/2;i>2;i/=2){
for(int j=0;j<i;j++){
insertsort(data,j,i);
}
}
insertsort(data,0,1);
}
/**
* @param data
* @param j
* @param i
*/
private void insertsort(int[] data, int start, int inc) {
int temp;
for(int i=start+inc;i<data.length;i+=inc){
for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
sortutil.swap(data,j,j-inc);
}
}
}
}
快速排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.sortutil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class quicksort implements sortutil.sort{
/* (non-javadoc)
* @see org.rut.util.algorithm.sortutil.sort#sort(int[])
*/
public void sort(int[] data) {
quicksort(data,0,data.length-1);
}
private void quicksort(int[] data,int i,int j){
int pivotindex=(i+j)/2;
//swap
sortutil.swap(data,pivotindex,j);
int k=partition(data,i-1,j,data[j]);
sortutil.swap(data,k,j);
if((k-i)>1) 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(data[++l]<pivot);
while((r!=0)&&data[--r]>pivot);
sortutil.swap(data,l,r);
}
while(l<r);
sortutil.swap(data,l,r);
return l;
}
}
改进后的快速排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.sortutil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class improvedquicksort implements sortutil.sort {
private static int max_stack_size=4096;
private static int threshold=10;
/* (non-javadoc)
* @see org.rut.util.algorithm.sortutil.sort#sort(int[])
*/
public void sort(int[] data) {
int[] stack=new int[max_stack_size];
int top=-1;
int pivot;
int pivotindex,l,r;
stack[++top]=0;
stack[++top]=data.length-1;
while(top>0){
int j=stack[top--];
int i=stack[top--];
pivotindex=(i+j)/2;
pivot=data[pivotindex];
sortutil.swap(data,pivotindex,j);
//partition
l=i-1;
r=j;
do{
while(data[++l]<pivot);
while((r!=0)&&(data[--r]>pivot));
sortutil.swap(data,l,r);
}
while(l<r);
sortutil.swap(data,l,r);
sortutil.swap(data,l,j);
if((l-i)>threshold){
stack[++top]=i;
stack[++top]=l-1;
}
if((j-l)>threshold){
stack[++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;i<data.length;i++){
for(int j=i;(j>0)&&(data[j]<data[j-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 mergesort implements sortutil.sort{
/* (non-javadoc)
* @see org.rut.util.algorithm.sortutil.sort#sort(int[])
*/
public void sort(int[] data) {
int[] temp=new int[data.length];
mergesort(data,temp,0,data.length-1);
}
private void 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[i]=data[i];
}
int i1=l;
int i2=mid+1;
for(int cur=l;cur<=r;cur++){
if(i1==mid+1)
data[cur]=temp[i2++];
else if(i2>r)
data[cur]=temp[i1++];
else if(temp[i1]<temp[i2])
data[cur]=temp[i1++];
else
data[cur]=temp[i2++];
}
}
}
改进后的归并排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.sortutil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class improvedmergesort implements sortutil.sort {
private static final int threshold = 10;
/*
* (non-javadoc)
*
* @see org.rut.util.algorithm.sortutil.sort#sort(int[])
*/
public void sort(int[] data) {
int[] temp=new int[data.length];
mergesort(data,temp,0,data.length-1);
}
private void mergesort(int[] data, int[] temp, int l, int r) {
int i, j, k;
int mid = (l + r) / 2;
if (l == r)
return;
if ((mid - l) >= 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[i] = data[i];
}
for (j = 1; j <= r - mid; j++) {
temp[r - j + 1] = data[j + mid];
}
int a = temp[l];
int b = temp[r];
for (i = l, j = r, k = l; k <= r; k++) {
if (a < b) {
data[k] = temp[i++];
a = temp[i];
} else {
data[k] = temp[j--];
b = temp[j];
}
}
}
/**
* @param data
* @param l
* @param i
*/
private void insertsort(int[] data, int start, int len) {
for(int i=start+1;i<start+len;i++){
for(int j=i;(j>start) && data[j]<data[j-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 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;i<data.length;i++)
h.remove();
system.arraycopy(h.queue,1,data,0,data.length);
}
private static class maxheap{
void init(int[] data){
this.queue=new int[data.length+1];
for(int i=0;i<data.length;i++){
queue[++size]=data[i];
fixup(size);
}
}
private int size=0;
private int[] queue;
public int get() {
return queue[1];
}
public void remove() {
sortutil.swap(queue,1,size--);
fixdown(1);
}
//fixdown
private void fixdown(int k) {
int j;
while ((j = k << 1) <= size) {
if (j < size && queue[j]<queue[j+1])
j++;
if (queue[k]>queue[j]) //不用交换
break;
sortutil.swap(queue,j,k);
k = j;
}
}
private void fixup(int k) {
while (k > 1) {
int j = k >> 1;
if (queue[j]>queue[k])
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
*/
public class sortutil {
public final static int insert = 1;
public final static int bubble = 2;
public final static int selection = 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 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(),
new heapsort()
};
public static string tostring(int algorithm){
return name[algorithm-1];
}
public static void sort(int[] data, int algorithm) {
impl[algorithm-1].sort(data);
}
public static interface sort {
public void sort(int[] data);
}
public static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
