堆排序

小顶堆#include<algorithm> #include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> #include<string.h> using namespace std; #define maxn 200000 int H,a[maxn]; void maxHeapify(int i) { int l,r,largest; l=2*i; r=2*i+1; if(l<=H&&a[l]>a[i]) largest=l; else largest=i; if(r<=H&&a[r]>a[largest]) largest=r; if(largest!=i) { swap(a[i],a[largest]); maxHeapify(largest); } } int main() { cin>>H; for(int i=1;i<=H;i++) { scanf("%d",&a[i]); } for(int i=H/2;i>=1;i--) maxHeapify(i); for(int i=1;i<=H;i++) { cout<<a[i]<<" "; } cout<<endl; return 0; } //10 //4 1 3 2 16 9 10 14 8 7

　　

大顶堆

 

#include<algorithm> #include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> #include<string.h> using namespace std; #define maxn 200000 void AdjustDown(int arr[], int i, int n) { int j = i * 2 + 1;//子节点 while (j<n) { if (j+1<n && arr[j] > arr[j + 1])//子节点中找较小的 { j++; } if (arr[i] < arr[j]) { break; } swap(arr[i],arr[j]); i = j; j = i * 2 + 1; } } void MakeHeap(int arr[], int n)//建堆 { int i = 0; for (i = n / 2 - 1; i >= 0; i--)//((n-1)*2)+1 =n/2-1 { AdjustDown(arr, i, n); } } void HeapSort(int arr[],int len) { int i = 0; MakeHeap(arr, len); for (i = len - 1; i >= 0; i--) { swap(arr[i], arr[0]); AdjustDown(arr, 0, i); } } int main() { int H,a[1000]; cin>>H; for(int i=0;i<H;i++) { scanf("%d",&a[i]); } HeapSort(a,H); for(int i=0;i<H;i++) { cout<<a[i]<<" "; } cout<<endl; return 0; }