锐客网

  1. 首页 > 睿知 > it技术 > >

堆排序代码java 堆排序java实现( 九 )

IT技术排序


print(table);
}
}
public static void quickSort(int[] table)//快速排序
{
quickSort(table, 0, table.length-1);
}
private static void quickSort(int[] table, int low, int high) //一趟快速排序 ， 递归算法
{//low、high指定序列的下界和上界
if (lowhigh)//序列有效
{
int i=low, j=high;
int vot=table[i];//第一个值作为基准值
while (i!=j)//一趟排序
{
while (ijvot=table[j])//从后向前寻找较小值
j--;
if (ij)
{
table[i]=table[j];//较小元素向前移动
i++;
}
while (ijtable[i]vot)//从前向后寻找较大值
i++;
if (ij)
{
table[j]=table[i];//较大元素向后移动
j--;
}
}
table[i]=vot;//基准值的最终位置
System.out.print(low+".."+high+",vot="+vot+"");
print(table);
quickSort(table, low, j-1);//前端子序列再排序
quickSort(table, i+1, high);//后端子序列再排序
}
}
public static void selectSort(int[] table)//直接选择排序
{
System.out.println("直接选择排序");
for (int i=0; itable.length-1; i++)//n-1趟排序
{//每趟在从table[i]开始的子序列中寻找最小元素
int min=i;//设第i个数据元素最小
for (int j=i+1; jtable.length; j++)//在子序列中查找最小值
if (table[j]table[min])
min = j;//记住最小元素下标
if (min!=i)//将本趟最小元素交换到前边
{
int temp = table[i];
table[i] = table[min];
table[min] = temp;
}
System.out.print("第"+i+"趟: ");
print(table);
}
}
private static void sift(int[] table, int low, int high) //将以low为根的子树调整成最小堆
{//low、high是序列下界和上界
int i=low;//子树的根
int j=2*i+1;//j为i结点的左孩子
int temp=table[i];//获得第i个元素的值
while (j=high)//沿较小值孩子结点向下筛选
{
if (jhightable[j]table[j+1])//数组元素比较（改成为最大堆）
j++;//j为左右孩子的较小者
if (temptable[j])//若父母结点值较大（改成为最大堆）
{
table[i]=table[j];//孩子结点中的较小值上移
i=j;//i、j向下一层
j=2*i+1;
}
else
j=high+1;//退出循环
}
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中

推荐阅读


上一篇：抖音手机壁纸怎么去除字，苹果手机抖音没有动态壁纸选项

下一篇：canvas游戏开发思维，canvas做游戏