ぎ☆用Java语言实现的各种排序ぎ☆

上一篇 / 下一篇 2006-11-26 20:35:53 / 个人分类：软件工程的专业知识

ぎ☆用Java语言实现的各种排序ぎ☆

用Java语言实现的各种排序，包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等

插入排序法
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class InsertSort implements SortUtil.Sort
{
public void sort(int[] data)
{
int temp;
for(int i=1;i {
for(int j=i;(j>0)&&(data[j] {
SortUtil.swap(data,j,j-1);
}
}
}
}

冒泡排序法
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class BubbleSort implements SortUtil.Sort
{
public void sort(int[] data)
{
int temp;
for(int i=0;i for(int j=i+1;j if(data[i] SortUtil.swap(data,i,j);
}
}
}
}
}

快速排序
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class BubbleSort implements SortUtil.Sort{
public void sort(int[] data) {
int temp;
for(int i=0;i for(int j=data.length-1;j>i;j--){
if(data[j] SortUtil.swap(data,j,j-1);
}
}
}
}
}

改进后的快速排序
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class ImprovedQuickSort implements SortUtil.Sort {
private static int MAX_STACK_SIZE=4096;
private static int THRESHOLD=10;
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);
l=i-1;
r=j;
do{
while(data[++l] while((r!=0)&&(data[--r]>pivot));
SortUtil.swap(data,l,r);
}
while(l 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;
}
}
insertSort(data);
}
private void insertSort(int[] data) {
int temp;
for(int i=1;i for(int j=i;(j>0)&&(data[j] SortUtil.swap(data,j,j-1);
}
}
}
}

导入论坛引用链接收藏分享给好友管理举报

TAG: 软件工程的专业知识