Блог

Я закодировал алгоритм быстрой сортировки в общих методах с параметрами:

• Метод разделения: ( T[] array, int low, int high )
• Метод сортировки: ( T[] array, int low, int high )

Однако, когда я пытаюсь выполнить рекурсию в теле метода сортировки для параметра массива, я получаю эту ошибку:

Неправильный 1-й тип аргумента. Найдено: ‘T[]’, требуется: ‘T[]’

Это код в методе сортировки:

  if (low < high)
        { int pi = partition(array, low, high);
            Quicksort(array, low, pi-1);
            Quicksort(array, pi 1, high);
        }
  

Вот код в методе разделения:

 T pivot = array[high];
        int i = (low-1); // index of smaller element
        for (int j=low; j<high; j  )
        {
            if (array[j].compareTo(pivot) <=0)
            {
                i  ;
                // swap array[i] and array[j]
                T temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        // swap array[i 1] and array[high] (or pivot)
        T temp = array[i 1];
        array[i 1] = array[high];
        array[high] = temp;

        return i 1;
  

Я не понимаю, как я могу попытаться исправить ошибку компилятора. Я попытался использовать его как, но он говорит то же самое. (T)array На мой взгляд, ему нужен параметр как в array[index] форме, но это делает мой метод неэффективным.

Есть ли какие-либо предложения, как я могу исправить эту ошибку?

Вот мой полный код:

 public class DD_ObjectBinarySearcher<T> {
    //comparison count for Binary search
    static int binarycount = 0;
    //comparison count for Sequential search
    static int seqcount = 0;
    //comparison totals for calculating averages
    static int stotal; static int btotal;

    /**
     *
     * @return total counts of Sequential Search
     */
    public static int getStotal() {
        return stotal;
    }

    /**
     *
     * @return total counts of Binary Search
     */
    public static int getBtotal() {
        return btotal;
    }

    /**
     * @param array array to be sorted
     * @param low starting index
     * @param high ending index
     * @return partition for quick sort
     */
    static  <T extends Comparable<T>> int partition(T[] array, int low, int high)
    {
        T pivot = array[high];
        int i = (low-1); // index of smaller element
        for (int j=low; j<high; j  )
        {
            if (array[j].compareTo(pivot) <=0)
            {
                i  ;
                // swap array[i] and array[j]
                T temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        // swap array[i 1] and array[high] (or pivot)
        T temp = array[i 1];
        array[i 1] = array[high];
        array[high] = temp;

        return i 1;
    }

    /**
     * @param array array to be sorted
     * @param low starting index
     * @param high ending index
     */
    static <T> void Quicksort(T[] array, int low, int high)
    {
        if (low < high)
        { int pi = partition(array, low, high);
            Quicksort(array, low, pi-1);
            Quicksort(array, pi 1, high);
        }
    }

    /**
     * @param a array
     * @param b compared integer
     * @return flag
     */
    static <T extends Comparable<T>> boolean sequentialSearch(T[] a, T b){
        for (T i : a) {
            if (i==b){
                System.out.println("The number of comparisons for unsorted array: "   seqcount);
                stotal =seqcount;
                return true;
            }
            seqcount  ;
        }
        return false;
    }

    /**
     * @param a array
     * @param b compared integer
     * @return flag
     */
    static <T extends Comparable<T>> boolean binarySearch(T[] a, T b) {
        if (a.length == 0) return false;
        int low = 0;
        int high = a.length-1;

        while(low <= high ) {
            int middle = (low high) /2;
            if (b.compareTo((T) a[middle]) > 0){
                low = middle  1;
            } else if (b.compareTo((T) a[middle]) < 0){
                high = middle -1;
            } else { // the element has been found
                System.out.println("The number of comparisons for sorted array: "   binarycount);
                btotal =binarycount; //totals are used to calculate average in the main
                return true;
            }
            binarycount  ;
        }
        return false;
    }

    /**
     *
     * @param array that will be printed
     */
    static void printArray(int[] array)
    {
        for (int value : array) System.out.print(value   " ");
        System.out.println();
    }

}
  

Каждый из 2 различных общих методов, задействованных здесь, определил параметр типа T . У T in Quicksort нет никаких границ, поэтому его вообще не должно быть Comparable . Однако T in partition должен иметь верхнюю границу Comparable<T> . Ошибка компилятора не указывает всю причину, но ошибка появляется, потому T что границы не совпадают.

Сделайте свою T привязку в Quicksort той же привязке.

 static <T extends Comparable<T>> void Quicksort(T[] array, int low, int high)
  

Обычно для гибкости мы продвигаем эту идею на один шаг дальше, потому что потребитель Супер (от PECS):

 static <T extends Comparable<? super T>> void Quicksort(T[] array, int low, int high)
  

который вы должны добавить ко всем своим T границам, включая ту, для partition которой требуется привязка, и любые другие, для которых требуется привязка.

Поскольку все ваши методы static , T определенные в классе, даже не используются. Вы можете безопасно удалить его.

 class DD_ObjectBinarySearcher {