[有错误]堆排序的实现 java

#include<iostream>

using namespace std;

//大根堆，从小到达排序

int a[];

void swap(int &a,int &b)

{

  a=a^b;

  b=a^b;

  a=a^b;

}

void adjust(int *a,int root,int len)

{

    int max=root;

    int left=*root;

    int right=*root+;

    if(left<=len&&a[max]<a[left])

    {

        max=left;

    }

    if(right<=len&&a[max]<a[right])

    {

        max=right;

    }

    if(max!=root)

    {

        swap(a[max],a[root]);

      adjust(a,max,len);

    }

}

void bulidHeap(int *a,int len)

{

    for(int i=len/;i>=;i--)

    {

        adjust(a,i,len);

    }

}

void heapSort(int *a,int len)

{

    if(len>)

    {

        swap(a[],a[len]);

        adjust(a,,len-);//调整为堆

        heapSort(a,len-);

    }

}

void output(int *a,int len)

{

    for(int i=;i<=len;i++)

    {

        cout<<a[i]<<" ";

    }

    cout<<endl;

}

int main()

{

    while(!cin.eof())

    {

        int len;

        cin>>len;

        for(int i=;i<=len;i++)

        {

          cin>>a[i];

        }

        bulidHeap(a,len);

        heapSort(a,len);

        output(a,len);

    }

    return ;

}

 //一个大根堆的例子

 //author:张小二

 public class HeapSort {

     public static void swap(int a[],int i,int j)

     {

         int temp=a[i];

         a[i]=a[j];

         a[j]=temp;

     }

     //最重要的自上而下调整的方法。，最多的代码在此处，建队和堆排序都是靠他。

     public static void adjust(int a[],int i,int len)//调整以i为根

     {

         while(true)

         {

             int largest=i;//寻找 i,2i+1,2i+2中的最大值

             int r=2*i;

             int l=2*i+1;

             if(r<len&&a[r]>a[largest]) largest=r;

             if(l<len&&a[l]>a[largest]) largest=l;

             if(largest==i) break;

             swap(a,i,largest);

             i=largest;

         }

     }

     //建立堆，从最后一个非叶子开始

     public static  void bulid(int a[],int len)

     {

         display(a);

         len=len-1;

         for(int i=len/2;i>=0;i--)

         {

             adjust(a,i,len);

         }

     }

     //堆排序

     public static void heapSort(int a[])

     {

         bulid(a,a.length);

         int len=a.length-1;

         while(len<1)

         {

             swap(a,0,len);

             adjust(a,0,len);

             len--;

         }

         //after

         display(a);

     }

     public static void display(int a[])

     {

         for(int i=0;i<a.length;i++)

         {

             System.out.print(a[i]+" ");

         }

         System.out.println();

     }

     /**

      * @param args

      */

     public static void main(String[] args) {

         // TODO Auto-generated method stub

         int a[]={3,-3,5,6,-7,9,45};

         heapSort(a);

     }

 }

巴特西

[有错误]堆排序的实现 java

最新文章

热门文章