Сортировать кучу реализации в Java

Пирамидальная сортировка является одним из лучших на общие цели алгоритмов сортировки, своего рода сравнение и часть семьи рода отбор. Хотя несколько медленнее, на практике в большинстве машин, чем хорошая осуществление сортировки, она имеет преимущества в худшем случае-O (N журнал N) Runtime и быть на месте алгоритма. Пирамидальная сортировка не является стабильной рода.

Следующий код показывает, как реализовать кучу сортировки в Java.



    /**


     * Standard heapsort.


     * @param a an array of Comparable items.


     */


    public static void heapsort( Comparable [ ] a )


    {


        for( int i = a.length / 2; i >= 0; i-- )  /* buildHeap */


            percDown( a, i, a.length );


        for( int i = a.length - 1; i > 0; i-- )


        {


            swapReferences( a, 0, i );            /* deleteMax */


            percDown( a, 0, i );


        }


    }





    /**


     * Internal method for heapsort.


     * @param i the index of an item in the heap.


     * @return the index of the left child.


     */


    private static int leftChild( int i )


    {


        return 2 * i + 1;


    }





    /**


     * Internal method for heapsort that is used in


     * deleteMax and buildHeap.


     * @param a an array of Comparable items.


     * @index i the position from which to percolate down.


     * @int n the logical size of the binary heap.


     */


    private static void percDown( Comparable [ ] a, int i, int n )


    {


        int child;


        Comparable tmp;





        for( tmp = a[ i ]; leftChild( i ) < n; i = child )


        {


            child = leftChild( i );


            if( child != n - 1 && a[ child ].compareTo( a[ child + 1 ] ) < 0 )


                child++;


            if( tmp.compareTo( a[ child ] ) < 0 )


                a[ i ] = a[ child ];


            else


                break;


        }


        a[ i ] = tmp;


    }


    


    


    /**


     * Method to swap to elements in an array.


     * @param a an array of objects.


     * @param index1 the index of the first object.


     * @param index2 the index of the second object.


     */


    public static final void swapReferences( Object [ ] a, int index1, int index2 )


    {


        Object tmp = a[ index1 ];


        a[ index1 ] = a[ index2 ];


        a[ index2 ] = tmp;


    }

Javist

Добавить комментарий Отменить ответ