C++/Java版推排序

用c++/ java编写一段程序:用堆排序(HeapSort)对一系列数进行排序,按从大到下输出:
堆排序的时间复杂度是:0(nlogn)
这里分别用C++和java编写:用面向对象的方法:将堆排序作为类中的一个方法,
(1)C++版:代码如下:

#include<iostream.h>

#include <stdlib.h>

#define N 100

class HeapSort //堆排序的类

{

public:

       void sift(int R[],int i, int m)

       {

   // 在数组R中将下标从im的元素序列调整为堆,即将以R[i]为根的子树调整为堆

   //初次调整的是以序号m/2的结点为根的子树;

              int j;

              j=2*i; 

              while (j<=m)   //j<=mR[2*i]R[i]的左孩子

              {

                     if(j<m &&R[j]>R[j+1])

                            j++; // 比较左右孩子的大小,使j为较小的孩子的下标

                     if(R[i]>R[j])

                     {

                            int temp;

                            temp=R[i];

                            R[i]=R[j];

                            R[j]=temp;

                            i=j;

                            j=2*i;

          // 上述交换可能使以该孩子结点为根的子树不再为堆,则需重新调整   

                     }

                     else break;

              }

       }

       void swap(int R[],int first,int last)//交换两个数

       {

              int temp;

              temp=R[first];

              R[first]=R[last];

              R[last]=temp;

       }

       void heapSort(int array[], int n)

       {    

              for (int index=n/2; index>=0;index--)

                     sift(array,index,n-1);

              swap(array,0,n-1);

              for (int last=n-2; last>0;last--)

              {

                     sift(array,0,last);

                     swap(array,0,last);

              }    

       }

};

void main()

{ 

       int n;

       int a[N];

       cout<<"输入要排序的数的个数:";

       cin>>n;

       cout<<"输入这"<<n<<"个数:";

       for(int i=0;i<n;i++)

              cin>>a[i];

       HeapSort h;

       h.heapSort(a,n);

       cout<<"排序后的数:";

       for(i=0;i<n;i++)

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

       cout<<endl;

}

(2) java版代码:如下:

public class HeapSort{

       public void heapSort(int[] array, int n){

              // create first heap 

              for (int index=n/2; index>=0;index--)

              sift(array,index,n-1);

              swap(array,0,n-1);

              for (int last=n-2; last>0;last--)

              {

                     sift(array,0,last);

                     swap(array,0,last);

              } // end for

             

       }

       public void sift(int R[],int i,int m){

              // 在数组R中将下标从im的元素序列调整为堆,即将以R[i]为根的子树调整为堆

              //初次调整的是以序号m/2的结点为根的子树;

 

              int j;

              j=2*i; 

        while (j<=m)   //j<=mR[2*i]R[i]的左孩子

        {

               if(j<m &&R[j]>R[j+1])

               j++; // 比较左右孩子的大小,使j为较小的孩子的下标

               if(R[i]>R[j])

            {

                   int temp;

                   temp=R[i];

                   R[i]=R[j];

                   R[j]=temp;

                   //R[i] <> R[j];  //+ 将较小的孩子与根交换

                   i=j;

                   j=2*i; // 上述交换可能使以该孩子结点为根的子树不再为堆,则需重新调整   

            }

            else break;

        }

       }

       public void swap(int R[],int first,int last)

       {

              int temp;

              temp=R[first];

              R[first]=R[last];

              R[last]=temp;

       }

       public void reverse(int R[])

       {

              for(int i=0,j=R.length-1;i<j;i++,j--)

              {

                     int temp=R[i];

                     R[i]=R[j];

                     R[j]=temp;

              }

              for(int k=0;k<R.length;k++)

              System.out.print(R[k]+"\t");

       }

       public static void main(String[] args){

              int[] a={0,49,38,65,97,76,13,27,49};

              HeapSort heap=new HeapSort();

              heap.heapSort(a,a.length);

              heap.reverse(a);

       }

}

留言

Your email address will not be published. Required fields are marked *