堆排序实例(Java数组实现)

2023-09-20 01:56:05 164

堆排序：利用大根堆

数组全部入堆，再出堆从后向前插入回数组中，数组就从小到大有序了。

publicclassMaxHeap>{
privateT[]data;
privateintsize;
privateintcapacity;

publicMaxHeap(intcapacity){
this.data=(T[])newComparable[capacity+1];
size=0;
this.capacity=capacity;
}

publicintsize(){
returnthis.size;
}

publicbooleanisEmpty(){
returnsize==0;
}

publicintgetCapacity(){
returnthis.capacity;
}

/**
*@return查看最大根(只看不删,与popMax对比)
*/
publicTseekMax(){
returndata[1];
}

publicvoidswap(inti,intj){
if(i!=j){
Ttemp=data[i];
data[i]=data[j];
data[j]=temp;
}
}

publicvoidinsert(Titem){
size++;
data[size]=item;
shiftUp(size);
}

/**
*@return弹出最大根(弹出意味着删除,与seekMax对比)
*/
publicTpopMax(){
swap(1,size--);
shiftDown(1);
returndata[size+1];
}

/**
*@paramchild孩子节点下角标是child，父节点下角表是child/2
*/
publicvoidshiftUp(intchild){
while(child>1&&data[child].compareTo(data[child/2])>0){
swap(child,child/2);
child=child/2;
}
}

/**
*@paramadata数组中某个元素的下角标
*@parambdata数组中某个元素的下角标
*@return哪个元素大就返回哪个的下角标
*/
privateintmax(inta,intb){
if(data[a].compareTo(data[b])<0){//如果data[b]大
returnb;//返回b
}else{//如果data[a]大
returna;//返回a
}
}

/**
*@paramadata数组中某个元素的下角标
*@parambdata数组中某个元素的下角标
*@paramcdata数组中某个元素的下角标
*@return哪个元素大就返回哪个的下角标
*/
privateintmax(inta,intb,intc){
intbiggest=max(a,b);
biggest=max(biggest,c);
returnbiggest;
}


/**
*@paramfather父节点下角标是father,左右两个孩子节点的下角表分别是：father*2和father*2+1
*/
publicvoidshiftDown(intfather){
while(true){
intlchild=father*2;//左孩子
intrchild=father*2+1;//右孩子
intnewFather=father;//newFather即将更新，父、左、右三个结点谁大，newFather就是谁的下角标

if(lchild>size){//如果该father结点既没有左孩子，也没有右孩子
return;
}elseif(rchild>size){//如果该father结点只有左孩子，没有右孩子
newFather=max(father,lchild);
}else{//如果该father结点既有左孩子，又有右孩子
newFather=max(father,lchild,rchild);
}

if(newFather==father){//说明father比两个子结点都要大，表名已经是大根堆，不用继续调整了
return;
}else{//否则，还需要继续调整堆，直到满足大根堆条件为止
swap(father,newFather);//值进行交换
father=newFather;//更新father的值，相当于继续调整shiftDown(newFather)
}
}
}

publicstatic>voidsort(T[]arr){
intlen=arr.length;
//入堆
MaxHeapmaxHeap=newMaxHeap(len);
for(inti=0;i=0;i--){
arr[i]=maxHeap.popMax();
}
}

publicstaticvoidprintArr(Object[]arr){
for(Objecto:arr){
System.out.print(o);
System.out.print("\t");
}
System.out.println();
}

publicstaticvoidmain(Stringargs[]){
Integer[]arr={3,5,1,7,2,9,8,0,4,6};
printArr(arr);//3517298046
sort(arr);
printArr(arr);//0123456789
}
}

堆排序：对数组进行构造堆(最大堆)

publicclassMaxHeap>{
privateT[]data;
privateintsize;
privateintcapacity;

publicMaxHeap(intcapacity){
this.capacity=capacity;
this.size=0;
this.data=(T[])newComparable[capacity+1];
}

publicMaxHeap(T[]arr){//heapify,数组建堆
capacity=arr.length;
data=(T[])newComparable[capacity+1];
System.arraycopy(arr,0,data,1,arr.length);
size=arr.length;
for(inti=size/2;i>=1;i--){
shiftDown(i);
}
}

publicintsize(){
returnthis.size;
}

publicintgetCapacity(){
returnthis.capacity;
}

publicbooleanisEmpty(){
returnsize==0;
}

publicTseekMax(){
returndata[1];
}

publicvoidswap(inti,intj){
if(i!=j){
Ttemp=data[i];
data[i]=data[j];
data[j]=temp;
}
}

publicvoidinsert(Titem){
size++;
data[size]=item;
shiftUp(size);
}

publicTpopMax(){
swap(1,size--);
shiftDown(1);
returndata[size+1];
}

publicvoidshiftUp(intchild){
while(child>1&&data[child].compareTo(data[child/2])>0){
swap(child,child/2);
child/=2;
}
}

/**
*@paramadata数组中某个元素的下角标
*@parambdata数组中某个元素的下角标
*@return哪个元素大就返回哪个的下角标
*/
privateintmax(inta,intb){
if(data[a].compareTo(data[b])<0){//如果data[b]大
returnb;//返回b
}else{//如果data[a]大
returna;//返回a
}
}

/**
*@paramadata数组中某个元素的下角标
*@parambdata数组中某个元素的下角标
*@paramcdata数组中某个元素的下角标
*@return哪个元素大就返回哪个的下角标
*/
privateintmax(inta,intb,intc){
intbiggest=max(a,b);
biggest=max(biggest,c);
returnbiggest;
}

publicvoidshiftDown(intfather){
while(true){
intlchild=father*2;
intrchild=father*2+1;
intnewFather=father;//这里赋不赋值无所谓，如果把下面这个return改成break,那就必须赋值了

if(lchild>size){//如果没有左、右孩子
return;
}elseif(rchild>size){//如果没有右孩子
newFather=max(father,lchild);
}else{//如果有左、右孩子
newFather=max(father,lchild,rchild);
}

if(newFather==father){//如果原父结点就是三者最大，则不用继续整理堆了
return;
}else{//父节点不是最大，则把大的孩子交换上来，然后继续往下堆调整，直到满足大根堆为止
swap(newFather,father);
father=newFather;//相当于继续shiftDown(newFather)。假如newFather原来是father的左孩子，那就相当于shiftDown(2*father)
}
}
}

publicstatic>voidsort(T[]arr){
intlen=arr.length;
MaxHeapmaxHeap=newMaxHeap<>(arr);
for(inti=len-1;i>=0;i--){
arr[i]=maxHeap.popMax();
}
}

publicstaticvoidprintArr(Object[]arr){
for(Objecto:arr){
System.out.print(o);
System.out.print("\t");
}
System.out.println();
}

publicstaticvoidmain(Stringargs[]){
Integer[]arr={3,5,1,7,2,9,8,0,4,6};
printArr(arr);//3517298046
sort(arr);
printArr(arr);//0123456789
}
}

以上这篇堆排序实例(Java数组实现)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

堆排序实例(Java数组实现)

热门推荐

随机推荐