SkyHawk

Heap Sort

Jul 6th, 2011
395
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void down(int* p,int k,int n)
  2. {
  3.     int l = k;
  4.     int k1 = ((k+1)<<1) - 1;
  5.     if(k1<n && p[k1]>p[l])
  6.         l = k1;
  7.     k1++;
  8.     if(k1<n && p[k1]>p[l])
  9.         l = k1;
  10.     if(l!=k)
  11.     {
  12.         int t = p[l];p[l] = p[k];p[k] = t;
  13.         down(p,l,n);
  14.     }
  15. }
  16.  
  17. void heapSort(int* p,int l)
  18. {
  19.     for(int i = (l<<2)-1;i>=0;--i)
  20.         down(p,i,l);
  21.     for(int i = l-1;i>0;--i)
  22.     {
  23.         int t = p[i];p[i] = p[0];p[0] = t;
  24.         down(p,0,--l);
  25.     }
  26. }
RAW Paste Data