xachetbay

Sắp Xếp Vun Đống

May 28th, 2019
170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.15 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. void nhap(int a[], int n){
  5.     for(int i = 0; i<n; i++){
  6.         cout<<"a["<<i<<"]= ";cin>>a[i];
  7.     }
  8. }
  9. void xuat(int a[], int n){
  10.     for(int i = 0; i<n; i++){
  11.         cout<<a[i]<<"\t";
  12.     }
  13. }
  14. void doicho(int &x, int &y){
  15.     int temp;
  16.     temp = x; x = y; y = temp;
  17. }
  18. void shift(int a[], int l, int r){
  19.     //Ham hieu chinh day a[l] -> a[r] thanh heap
  20.     int x, i, j;
  21.     i = l; j = 2*i+1; x = a[i];
  22.     while(j<=r){
  23.         if(j < r)
  24.         if(a[j] < a[j+1])
  25.         j++;
  26.         if(a[j]<=x) return;
  27.         else{
  28.             a[i] = a[j];
  29.             a[j] = x;
  30.             i = j;
  31.             j = 2*i+1;
  32.             x=a[i];
  33.         }
  34.     }
  35. }
  36. void createHeap(int a[], int n){
  37.     //ham tao heap
  38.     int l;
  39.     l = n/2-1;
  40.     while(l>=0){
  41.         shift(a,l,n-1);
  42.         l=l-1;
  43.     }
  44. }
  45. void heapSort(int a[],int n){
  46.     //Thuat toan heapSort
  47.     int r;
  48.     createHeap(a,n);
  49.     r = n-1;
  50.     while(r>0){
  51.         doicho(a[0], a[r]);
  52.         r--;
  53.         if(r>0) shift(a,0,r);
  54.     }
  55. }
  56. int main(){
  57.     int a[20],n;
  58.     cout<<"Nhap so phan tu n cua day: ";cin>>n;
  59.     cout<<"Nhap gia tri cho tung phan tu cua day: "<<endl; nhap(a, n);
  60.     cout<<"Day vua nhap: "<<endl; xuat(a, n);
  61.     cout<<endl<<endl;
  62.     heapSort(a, n);
  63.     cout<<"Day da xep tang: "<<endl; xuat(a, n);
  64.     return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment