QuickSort 算法未通过测试工具

Question

我和一个小组一起制作了一个 QuickSort 算法，用于在 class 之外练习我们的 java 编码（不是家庭作业问题）。我的代码似乎符合大多数 QuickSort 实现的代码，但是当运行一个测试工具时，它有 5/7 次测试失败。我的实施有什么明显的错误吗？

public class QuickSort implements SortInterface {

    public void swap(Note[] Note, int i, int j) {
        Note temp = Note[i];
        Note[i] = Note[j];
        Note[j] = temp;
    }


    // TODO Auto-generated method stub pseudo here
    public void quicksort(Note[] Note, long m, long l){

        if(m<l){
            //choose a pivot, median of three
            long pivot_index = pivotMaker(Note, m, l);
            //partition the array about the pivot, return index of pivot, where swaps happen
            pivot_index = partition(Note, pivot_index);

            quicksort(Note, m, pivot_index-1 ); // breaks up lesser than pivot side
            quicksort(Note, pivot_index+1, l); // breaks up higher than pivot side
        } // end if
    }

    public long pivotMaker(Note [] Note, long m, long l) // physically creates a median of three pivot
    {

            int center = (int)((m + l) / 2);
            // order left & center
            if (Note[(int)(m)].getID() > Note[center].getID())
              swap(Note,(int)m, center);
            // order left & right
            if (Note[(int)(m)].getID() > Note[(int)l].getID())
              swap(Note,(int)m, (int)l);
            // order center & right
            if (Note[center].getID() > Note[(int)l].getID())
              swap(Note,center, (int)l);

            swap(Note,center, (int)l - 1); // put pivot on right
            return Note[(int)(l-1)].getID(); // return median value
          }
        //median of 3

        // end pivot maker

    public int partition(Note[] Note, long pivot_index){ // will place the pivot in its final index         
        return(0);
    }

    public Note[] sort(Note[] s) {
         quicksort(s, 0, s.length-1);
         return s;
    }
    public static void main(String[] args) {
        // make an array of notes
        Note q = new Note(" ", " ");
        Note n = new Note("CSCI 230 Project Plan", 
                "Each person will number their top 5 choices.\n" +
                "By next week, Dr. Hill will assign which piece\n" +
                "everyone will work on.\n");
        n.tag("CSCI 230");
        n.tag("final project");

        Note[] Note = {q,n, new Note(" ", " "), new Note(" ", " "), new Note(" ", " "), new Note(" ", " "), new Note(" ", " ")};
        //print out not id's
        //call QuickSort
        System.out.println(Note);
        //print out note_id's
    }

}

Answer 1

如果包含成功和失败的测试，会更容易。但是很明显分区还没有实现：

`public int partition(Note[] Note, long pivot_index)` always returns `0`.

此外，您正在使用索引 l-1，我认为您打算使用 l:

swap(Note,center, (int)l - 1);

QuickSort 算法未通过测试工具

QuickSort Algorithm not passing a test harness

java

sorting

algorithm

quicksort