锐客网

  1. 首页 > 生活百科 > it技术 > >

堆排序最优java代码 堆排序程序( 七 )

IT技术排序


}
table[i]=temp;//当前子树的原根值调整后的位置
System.out.print("sift"+low+".."+high+"");
print(table);
}
public static void heapSort(int[] table)
{
System.out.println("堆排序");
int n=table.length;
for (int j=n/2-1; j=0; j--)//创建最小堆
sift(table, j, n-1);
//System.out.println("最小堆？ "+isMinHeap(table));
for (int j=n-1; j0; j--)//每趟将最小值交换到后面，再调整成堆
{
int temp = table[0];
table[0] = table[j];
table[j] = temp;
sift(table, 0, j-1);
}
}
public static void mergeSort(int[] X)//归并排序
{
System.out.println("归并排序");
int n=1;//已排序的子序列长度，初值为1
int[] Y = new int[X.length];//Y数组长度同X数组
do
{
mergepass(X, Y, n);//一趟归并，将X数组中各子序列归并到Y中
print(Y);
n*=2;//子序列长度加倍
if (nX.length)
{
mergepass(Y, X, n);//将Y数组中各子序列再归并到X中
print(X);
n*=2;
}
} while (nX.length);
}
private static void mergepass(int[] X, int[] Y, int n) //一趟归并
{
System.out.print("子序列长度n="+n+"");
int i=0;
while (iX.length-2*n+1)
{
merge(X,Y,i,i+n,n);
i += 2*n;
}
if (i+nX.length)
merge(X,Y,i,i+n,n);//再一次归并
else
for (int j=i; jX.length; j++)//将X剩余元素复制到Y中
Y[j]=X[j];
}
private static void merge(int[] X, int[] Y, int m, int r, int n)//一次归并
{
int i=m, j=r, k=m;
while (irjr+njX.length)//将X中两个相邻子序列归并到Y中
if (X[i]X[j])//较小值复制到Y中
Y[k++]=X[i++];
else
Y[k++]=X[j++];
while (ir)//将前一个子序列剩余元素复制到Y中
Y[k++]=X[i++];
while (jr+njX.length)//将后一个子序列剩余元素复制到Y中
Y[k++]=X[j++];
}
public static void main(String[] args)
{
//int[] table = {52,26,97,19,66,8,49};//Array.random(9);{49,65,13,81,76,97,38,49};////{85,12,36,24,47,30,53,91,76};//;//{4,5,8,1,2,7,3,6};// {32,26,87,72,26,17};//
int[] table = {13,27,38,49,97,76,49,81};//最小堆
System.out.print("关键字序列: ");
Array.print(table);
//Array.insertSort(table);
//Array.shellSort(table);
//Array.bubbleSort(table);
//Array.quickSort(table);
//Array.selectSort(table);
//Array.heapSort(table);
//Array.mergeSort(table);
System.out.println("最小堆序列? "+Array.isMinHeap(table));
}
//第9章习题
public static boolean isMinHeap(int[] table)//判断一个数据序列是否为最小堆
{
if (table==null)
return false;
int i = table.length/2 -1;//最深一棵子树的根结点
while (i=0)
{
int j=2*i+1;//左孩子
if (jtable.length)
if (table[i]table[j])
return false;
else
if (j+1table.lengthtable[i]table[j+1])//右孩子
return false;
i--;
}
return true;
}
}
/*
程序运行结果如下：
关键字序列:32 26 87 72 26 17 8 40
直接插入排序
第1趟排序:26 32 87 72 26 17 8 40
第2趟排序:26 32 87 72 26 17 8 40
第3趟排序:26 32 72 87 26 17 8 40
第4趟排序:26 26 32 72 87 17 8 40//排序算法稳定
第5趟排序:17 26 26 32 72 87 8 40
第6趟排序:8 17 26 26 32 72 87 40
第7趟排序:8 17 26 26 32 40 72 87
关键字序列:42 1 74 25 45 29 87 53
直接插入排序
第1趟排序:1 42 74 25 45 29 87 53
第2趟排序:1 42 74 25 45 29 87 53
第3趟排序:1 25 42 74 45 29 87 53
第4趟排序:1 25 42 45 74 29 87 53
第5趟排序:1 25 29 42 45 74 87 53
第6趟排序:1 25 29 42 45 74 87 53
第7趟排序:1 25 29 42 45 53 74 87

推荐阅读


上一篇：怎么用绳索连接队友手机，怎么用绳索连接队友手机游戏

下一篇：消防现在直播素材下载，消防直播视频