二进制HeapSort与三元HeapSort实现

Question

这是我对大学作业的二进制和三元堆排序实现的看法。代码可以工作，但我想知道是否有任何错误或事情需要改进。

class HeapSorter {

    static int[] array;
    static int heapSize;

    //=============================BINARY HEAPSORT=============================//

    static void maxHeapify(int i){

        int leftChild = left(i);
        int rightChild = right(i);
        int largest;

        largest = leftChild <= heapSize && array[leftChild] > array[i] ? leftChild : i ;

        if(rightChild <= heapSize && array[rightChild] > array[largest])
            largest = rightChild;


        if(largest != i){
            swap(i, largest);

            //Recursively heapify the subtree
            maxHeapify(largest);
        }


    }

    static void binaryHeapSort(int[] toSort){
        array = toSort;
        buildMaxHeap();

        //testing i >= 0 will be executed for i= array.length - 1, array.length - 2,......0,-1. So array.length + 1 times (n + 1)
        //i-- will be executed array.length times (n)
        for(int i = array.length - 1; i >= 0; i--){

            //swap executed n times (n)
            swap(0,i); 

            // heapSize - 1 executed n times (n)
            // assignment executed n times (n)
            heapSize = heapSize - 1; 

            //maxHeapify executed n times (n)
            maxHeapify(0); 
        }

    }

    static void buildMaxHeap(){
        heapSize = array.length - 1;
        for(int i = (array.length - 1) / 2; i >= 0; i--)
            maxHeapify(i);

    }

    static int left(int i){
        return i << 1;
    }

    static int right(int i){
        return (i << 1) + 1;
    }

    //==========================================================================//

    //=============================TERNARY HEAPSORT=============================//

    static void buildMaxHeapT(){
        heapSize = array.length - 1 ;
        for(int i =array.length - 1  / 3; i >= 0; i--)
            maxHeapifyT(i);

    }

    static void maxHeapifyT(int i){

        int leftChild = leftT(i);
        int rightChild = rightT(i);
        int middleChild = middleT(i);
        int largest;

        largest = leftChild <= heapSize && array[leftChild] > array[i] ? leftChild : i;

        if(rightChild <= heapSize && array[rightChild] > array[largest])
            largest = rightChild;

        if(middleChild <= heapSize && array[middleChild] > array[largest])
            largest = middleChild;


        if(largest != i){
            swap(i, largest);
            maxHeapifyT(largest);
        }
    }

    static void ternaryHeapSort(int[] toSort){
        array = toSort;
        buildMaxHeapT();

        for(int i = array.length - 1; i >= 0; i--){
            swap(0,i); //add last element on array, i.e heap root

            heapSize = heapSize - 1; //shrink heap by 1
            maxHeapifyT(0);
        }

    }

    static int leftT(int i){
        return 3 * i + 1;
    }

    static int middleT(int i){
        return 3 * i + 2;
    }

    static int rightT(int i){
        return 3 * i + 3;
    }

    //==========================================================================//



    static void swap(int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }




    static int[] start (int[] toSort, boolean binaryHeap) {
        if (binaryHeap) {
            binaryHeapSort(toSort);
        } else { 
            ternaryHeapSort(toSort);
        }

        return toSort;
    }
}

另外，我是否应该使用这样的位移位：

static int leftT(int i){
    return (i << 1) + i + 1;
 }

而不是

static int leftT(int i){
    return 3 * i + 1;
}

Answer 1

还不错。我很懒，所以只有两条评论：

static int[] array;

除常量外，任何静力学都不应使用。请始终创建一个对象，理想情况下分配构造函数中的所有内容，并让它处理其数据。

它只需增加几行，就可以使您的类更加可用。静力学是一种全局变量，这意味着不好。你这么做的方式，起作用了.但是尝试启动更多的线程并并发调用start。

另外，我是否应该使用这样的位移位：

不，除了在机器人上。让JVM完成它的工作。它可能比您知道更多的技巧(例如，在没有除法指令的情况下执行x / 10，即可能比您快3倍)。