#include <stdio.h> #include <iostream> using namespace std; int heapsize=4;//数组长度,数组下标从1开始记,否则计算下标为0的孩子结点的下标麻烦 int j=0; void maxHeapify(int a[],int i){ //使以a[i]为根的子树成为最大堆 //假设以a[left]和a[right]为根的2棵二叉树都是最大堆 int left=i<<1; //i的左孩子下标 //printf("i=%d",i); int right=left+1;//i的右孩子下标**原先写成right=i<<1+1 int largest=i; //记录最大值的下标 if(i<=heapsize/2){ //可以不加 如果i是叶节点就不用进行调整 if(left<=heapsize&&(a[left]>a[i])){ largest=left; } if(right<=heapsize&&(a[right]>a[i])) largest=right; if(largest!=i){ int temp=a[i]; a[i]=a[largest]; a[largest]=temp; maxHeapify(a,largest); } } } void buildMaxHeap(int a[]){ for(int i=heapsize/2;i>0;i--) maxHeapify(a,i); } void heap_sort(int a[]){ int len=heapsize; buildMaxHeap(a); for(int i=len;i>1;i--){ printf("%d ",a[1]);//从大到小输出 int temp=a[1];//b[j]=temp;j++; a[1]=a[i]; a[i]=temp; heapsize--;//最终出bug在这儿,写成了len--,可以每次把heapsize传入函数 maxHeapify(a,1); } printf("%d\n",a[1]); } int main(){ int a[]={0,2,4,1,3};//a[0]不算 heap_sort(a); for(int i=1;i<=4;i++){ printf("%d ",a[i]); } printf("\n"); return 0; }
public class HeapSort { public static int heapsize=4; public static void main(String[] args) { int a[]={0,2,4,1,3};//a[0]不算 heap_sort(a); for(int i=1;i<=4;i++){ System.out.printf("%d ",a[i]); } System.out.println(); } public static void heap_sort(int[] a) { int len=heapsize; buildMaxHeap(a); for(int i=len;i>1;i--){ System.out.print(a[1]+" "); int temp=a[1]; a[1]=a[i]; a[i]=temp; heapsize--; maxHeapify(a,1); } System.out.println(a[1]); } public static void maxHeapify(int[] a, int i) { int left=i<<1; int right=left+1; int largest=i; if(i<=heapsize/2){ //可以不加 如果i是叶节点就不用进行调整 if(left<=heapsize&&(a[left]>a[i])){ largest=left; } if(right<=heapsize&&(a[right]>a[i])) largest=right; if(largest!=i){ int temp=a[i]; a[i]=a[largest]; a[largest]=temp; maxHeapify(a,largest); } } } public static void buildMaxHeap(int[] a) { for(int i=heapsize/2;i>0;i--){ maxHeapify(a,i); } } }class heap(object): heapsize=4 def heapsort(self,a): #global heapsize len=s.heapsize s.buildMaxHeap(a) for i in range(len,1,-1): print("%d" %a[1],end=" ") temp=a[1] a[1]=a[i] a[i]=temp s.heapsize-=1 s.maxHeapify(a,1) print("%d\n" %a[1]) def buildMaxHeap(self,a): for i in range(s.heapsize//2,0,-1): s.maxHeapify(a,i) def maxHeapify(self,a,i): left=i<<1 right=left+1 largest=i if i<=s.heapsize//2: if left<=s.heapsize and (a[left]>a[i]): largest=left if right<=s.heapsize and a[right]>a[i]: largest=right if largest!=i: temp=a[i] a[i]=a[largest] a[largest]=temp s.maxHeapify(a,largest) if __name__=="__main__": array=[0,4,2,1,3] s=heap() s.heapsort(array) for i in range(1,5): print("%d " %array[i], end="") print("\n")**注意 除法取整为双除“//”
**Python作用域: