java 排序算法代码大全
时间：2025-04-06
java 排序算法代码大全
2012-04-17 14:58:02| 分类： JAVA 知识积累 |字号订阅
/**
* 插入排序:直接插入排序、折半插入排序和系尔排序
* 交换排序:冒泡排序和快速排序
* 选择排序:简单选择排序和堆排序
* 归并排序:归并排序
*
* 基本思想
* 插入排序:将第N个记录插入到前面(N-1)个有序的记录当中。
* 交换排序:按照某种顺序比较两个记录的关键字大小，然后根据需要交换两个记录的位置。 * 选择排序:根据某种方法选择一个关键字最大的记录或者关键字最小的记录，放到适当的位置。
*
* 排序方法比较
* 排序方法平均时间最坏时间辅助存储
* 直接插入排序 O(N2) O(N2) O(1)
* 起泡排序 O(N2) O(N2) O(1)
* 快速排序 O(Nlog2N) O(N2) O(Nlog2N)
* 简单选择排序 O(N2) O(N2) O(1)
* 堆排序 O(Nlog2N) O(Nlog2N) O(1)
* 归并排序 O(Nlog2N) O(Nlog2N) O(n)
* 基数排序 O(d(n+radix)) O(d(n+radix)) O(radix)
*
*
*
* @author Administrator
*
*/
public class SortTest {
public static void main(String[] args)throws Exception {
//测试排序是否正确
//String[] testErr=new String[]{"冒泡排序","简单选择排序","直接插入排序","折半插入排序","系尔排序","堆排序","归并排序","快速排序"};
//new SortTest().testErr(testErr);
//排序1（全部）
String[] strs=new String[]{"冒泡排序","简单选择排序","直接插入排序","折半插入排序","希尔排序","堆排序","归并排序","快速排序"};
new SortTest().test(strs,10000,50000,5000);
//排序2（加强）
String[] strs2=new String[]{"希尔排序","堆排序","归并排序","快速排序"}; new SortTest().test(strs2,100000,1900000,100000);
}
private void testErr(String[] strings) throws Exception{
//System.out.println(Arrays.toString(old));
System.out.println(Arrays.toString(strings));
Number[] old=getRundom(50);
Integer[]
oo={1,2,3,3,2,21,5,6,7,78,5,65,8,7,6,6,6,6,6,9,56544,354,32,4,456,8,89,-9,0,3,243,-321,321,-3,-2,21};
old=oo;
for(String s:strings){
Number[] testNum=Arrays.copyOf(old, old.length);
long begin=System.currentTimeMillis();
SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum);
long end=System.currentTimeMillis();
System.out.println(s+":"+(end-begin)+"\t");
System.out.println(Arrays.toString(testNum));
}
System.out.println();
}
private void test(String[] strings,long begin,long end,long step) throws Exception{ System.out.print("数量\t");
for(String str:strings){
System.out.print(str+"\t");
}
System.out.println();
for(long i=begin;i<end;i=i+step){
System.out.print(i+"个\t");
Number[] old=getRundom(i);
for(String s:strings){
Number[] testNum=Arrays.copyOf(old, old.length);
long beginTime=System.currentTimeMillis();
SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum);
long endTime=System.currentTimeMillis();
System.out.print((endTime-beginTime)+"\t");
//System.out.println(Arrays.toString(testNum));
}
System.out.println();
}
}
private static Integer[] getRundom(long num) {
List<Integer> list=new ArrayList<Integer>();
for(long i=0;i<num;i++){
int k;
if(Math.random()>0.5){
k=(int)(Math.random()*Integer.MAX_VALUE);
}else{
k=(int)(Math.random()*Integer.MIN_VALUE);
}
list.add(k);
}
return list.toArray(new Integer[list.size()]);
}
/**
* 插入排序————直接插入排序
* @param data
*/
public static void 直接插入排序(Number[] data)
{
Number tmp=null ;
for(int i=1;i<data.length;i++){
tmp = data[i];
int j=i-1;
while(j>=0 && tmp.doubleValue()<data[j].doubleValue()){
data[j+1]=data[j];
j--;
}
data[j+1]=tmp;
}
}
/**
* 插入排序————折半插入排序
* @param data
*/
public static void 折半插入排序(Number[] data)
{
Number tmp=null ;
for(int i=1;i<data.length;i++){
tmp = data[i];
int smallpoint=0;
int bigpoint=i-1;
while(bigpoint>=smallpoint){
int mid=(smallpoint+bigpoint)/2;
if(tmp.doubleValue()>data[mid].doubleValue()){
smallpoint=mid+1;
}else{
bigpoint=mid-1;
}
}
for(int j=i;j>smallpoint;j--){
data[j]=data[j-1];
}
data[bigpoint+1]=tmp;
}
}
/**
* 插入排序————希尔排序
* @param data
*/
public static void 希尔排序(Number[] data)
{
int span=data.length/7;
if(span==0)span=1;
while(span>=1){
for(int i=0;i<span;i++){
for(int j=i;j<data.length;j=j+span){
//组内直接插入排序
int p = j-span;
Number temp = data[j];
while( p >=0 && data[p].doubleValue() > temp.doubleValue()){ data[p+span] = data[p];
p -=span;
}
data[p + span] = temp;
…… 此处隐藏：4753字，全部文档内容请下载后查看。喜欢就下载吧 ……
java 排序算法代码大全.doc
将本文的Word文档下载到电脑
